This is just one problem but it was one that I got from an interview and would love to talk about where I went wrong and how to solve it. Question:
There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).There are n + 1 taps located at points [0, 1, ..., n] in the garden.Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.
This is a greedy algorithm problem that can be solved in log(n) time. I definitely did not go about the problem in this way.
The first thing I tried to do was reduce the number of taps that I am working with. The easiest way to do this is by checking if any of the taps are completely encompassed by another tap.
for i in range(len(ranges)):
for j in range(max(0, i - ranges[i]), min(len(ranges)-1, i - ranges[i])):
if(i != j and ranges[j] != -1 and max(0, i - ranges[i]) <= max(0, j- ranges[j]) and min(len(ranges)-1, i - ranges[i]) >= min(len(ranges)-1, i - ranges[j]):
ranges[j] = -1count = 0
for i in range(len(ranges)):
if(ranges[i] > -1):
count += 1return count
Now yes we can get a solution in some cases that does not mean in all cases. Sometimes you will want to turn on 2 different taps that can encompass the single tap because these 2 other taps may be able to cover other taps that are outside of the range.
Okay well, why not just make a check that sees if 2 other taps can encompass the single tap after you have eliminated all of the encompassed taps.
for i in range(len(ranges)):
for j in range(max(0, i - ranges[i]), min(len(ranges)-1, i - ranges[i])):
if(i != j and ranges[j] != -1 and max(0, i - ranges[i]) <= max(0, j- ranges[j]) and min(len(ranges)-1, i - ranges[i]) >= min(len(ranges)-1, i - ranges[j])):
ranges[j] = -1left = false
right = falsefor i in range(len(ranges)):
for j in range(max(0, i - ranges[i]), min(len(ranges)-1, i - ranges[i])):
if(i != j and ranges[j] != -1 and max(0, i - ranges[i]) <= max(0, j- ranges[j])):
left = true
if(i != j and ranges[j] != -1 and min(len(ranges)-1, i - ranges[i]) >= min(len(ranges)-1, i - ranges[j])):
right = true
if(left and right):
range[i] = -1count = 0
for i in range(len(ranges)):
if(ranges[i] > -1):
count += 1return count
I can see why I did this if 2 different taps cover the area of another tap and these taps are not completely encompassed by another then great. The problem starts with what if most of the taps can be covered by others. Which set do you start with then. You might not cover the entire garden if you turn off the wrong pairing of taps.
Well there is a way but you have to think about the problem in a completely different way. Think about how far one tap can go and then find the next farthest tap after that one.
def minTaps(self, n: int, ranges: List[int]) -> int: new_list = a = [0] * (n + 1) for i in range(n + 1):
left = max(0, i - ranges[i])
right = min(n, i + ranges[i]) new_list[left] = max(new_list[left], right - left) start = end = count = 0 while(end < n):
count += 1
start, end = end, max(i + new_list[i] for i in range(start, end + 1)) if(start == end):
return -1return count
This works because you create a new array that has the distance from the left that that spot can move. Then after that, you are starting at the front and move as far as you can. Then the range that you have increased on the next run and you can then get farther.
