HackerRank ‘Happy Ladybugs’ Solution

Short Problem Definition:


Happy Ladybugs is a board game having the following properties:

  • A ladybug is happy only when it’s left or right adjacent cell (i.e., ) b[i+/-1] is occupied by another ladybug having the same color.
Link

Happy Ladybugs

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

This challenge definition does not require a full sort. It only wants to know whether the array is sortable. Therefore we will assume that if there is at least one free slot, the array is sortable by color.

Further we will assume that each ladybug wants to have at least one neighbor with the same color. If there are two of the same color, the ladybug is happy.

If there is no empty space, the input array needs to be sorted correctly.

Solution:
#!/bin/python

import math
import os
import random
import re
import sys
from collections import Counter

# Complete the happyLadybugs function below.
def happyLadybugs(b):
    counter = Counter(b)
    for key, value in counter.items():
        if key != "_" and value == 1:
            return "NO"
    
    if "_" in b:
        return "YES"

    for idx in xrange(1, len(b)):
        if b[idx] == b[idx-1] or b[idx] == b[idx+1]:
            continue
        else:
            return "NO"
        
    return "YES"
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    g = int(raw_input())

    for g_itr in xrange(g):
        n = int(raw_input())

        b = raw_input()

        result = happyLadybugs(b)

        fptr.write(result + '\n')

    fptr.close()

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin