02/23/16

# HackerRank ‘Sherlock and Valid String’ Solution

##### Short Problem Definition:

Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he can remove just 1 character at 1 index in the string, and the remaining characters will occur the same number of times. Given a string , determine if it is valid. If so, return YES, otherwise return NO.

Sherlock and Valid String

##### Complexity:

time complexity is O(N)

space complexity is O(1)

##### Execution:

I optimized this solution to the minimal case that passes all tests on HackerRank. It seems that each character occurs 1 or 2 times. I did not pay the Hackos to verify the input :). The logic of the solution is as follows: count the character counts for each character.

• if they are all equal – it means that all characters occur exactly N times and there is no removal needed
• if 2 or more have less or more characters – there is no way to fix the string in just 1 removal
• if exactly 1 char has a different count than all other characters – remove this char completely and S is fixed.
##### Solution:
from collections import Counter

def isValid(S):
char_map = Counter(S)
char_occurence_map = Counter(char_map.values())

if len(char_occurence_map) == 1:
return True

if len(char_occurence_map) == 2:
for v in char_occurence_map.values():
if v == 1:
return True

return False

S = raw_input()
if isValid(S):
print "YES"
else:
print "NO"


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

02/11/16

# HackerRank ‘Poisonous Plants’ Solution

##### Short Problem Definition:

There are NN plants in a garden. Each of these plants has been added with some amount of pesticide. After each day, if any plant has more pesticide than the plant at its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each plant. Print the number of days after which no plant dies, i.e. the time after which there are no plants with more pesticide content than the plant to their left.

Poisonous Plants

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

This challenge was really hard. I could not figure it out for a long time. The part with the stack is pretty obvious, but I missed the fact that older plants can have higher daysAlive values.

##### Solution:
class Plant:
def __init__(self, pesticide, days):
self.pesticide = pesticide
self.days = days

def solvePlants(a):
stack = []
maxDaysAlive = 0

for pesticide in a:
daysAlive = 0
while stack and pesticide <= stack[-1].pesticide:
daysAlive = max(daysAlive, stack.pop().days)

if not stack:
daysAlive = 0
else:
daysAlive += 1

maxDaysAlive = max(maxDaysAlive, daysAlive)

stack.append(Plant(pesticide, daysAlive))

print maxDaysAlive

def main():
N = input()

numbers = map(int, raw_input().split())

solvePlants(numbers)

if __name__ == '__main__':
main()


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

02/10/16

# HackerRank ‘Waiter’ Solution

##### Short Problem Definition:

You are a waiter at a party. There are NN stacked plates. Each plate has a number written on it. You start picking up the plates from the top one by one and check whether the number written on the plate is divisible by a prime….

Waiter

##### Complexity:

time complexity is O(N*Q)

space complexity is O(N)

##### Execution:

First of all, generate primes using Sieve, or copy-paste a list of pre-generated primes. After each iteration the order of the remaining plates is reversed (you put the last on top and once finished you start from the top). That means that the solution has to have a stack, not a queue.

It is not possible to solve this in one pass. I would love to find such a solution.

##### Solution:
generated_primes = [...]

def solveWaiter(N, Q, numbers):
stack = []

for value in numbers:
if value % generated_primes != 0:
stack.append(value)
else:
print value

for prime_idx in xrange(1, Q):
leftover = []

while stack:
value = stack.pop()
if value % generated_primes[prime_idx] != 0:
leftover.append(value)
else:
print value
stack = leftover

for value in stack:
print value

def main():
N, Q = map(int, raw_input().split())

numbers = map(int, raw_input().split())

solveWaiter(N, Q, numbers)

if __name__ == '__main__':
main()



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

02/9/16

# HackerRank ‘Largest Rectangle’ Solution

##### Short Problem Definition:

There are NN buildings in a certain two-dimensional landscape. Each building has a height given by hi,i∈[1,N]hi,i∈[1,N]. If you join KK adjacent buildings, they will form a solid rectangle of area K×min(hi,hi+1,…,hi+k−1)K×min(hi,hi+1,…,hi+k−1).

Given NN buildings, find the greatest such solid area formed by consecutive buildings.

Largest Rectangle

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

Best explained on Geeks for Geeks.

##### Solution:
def computeLargestArea(hist, N):
stack = []

max_area = 0

idx = 0
while (idx < N):
if not stack or hist[stack[-1]] <= hist[idx]:
stack.append(idx)
idx += 1
else:

height_idx = stack.pop()

depth = idx
if stack:
depth = idx - stack[-1] - 1

area = hist[height_idx] * depth
max_area = max(area, max_area)

while stack:
height_idx = stack.pop()

depth = idx
if stack:
depth = idx - stack[-1] - 1

area = hist[height_idx] * depth
max_area = max(area, max_area)

return max_area

def main():
N = int(raw_input())

hist = map(int, raw_input().split())

print computeLargestArea(hist, N)

if __name__ == '__main__':
main()


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