Two pointers
Two pointers is an important strategy to solve problems.
I’d like to put more problems here to make sure that we can fully understand how to solve this kind of problem.
1326. Minimum Number of Taps to Open to Water a Garden
This problem is a slightly modified problem of Twitter OA problem
For each tap, record the maximum left reach point and maximum right reach point.
Based on this, we can
- get a list contains for each left point, what is the maximum right reaching point.
- Then using a greedy algorithm to solve this problem.
Code is here with comments.
class Solution:
def minTaps(self, n: int, A: List[int]) -> int:
if not A: return 0
N = len(A)
# For all location of taps, store the largest right reach point
max_right_end = list(range(N))
for i, a in enumerate(A):
left, right = max(i - a, 0), min(i + a, N-1)
max_right_end[left] = max(max_right_end[left], right) res, l, r = 0, 0, max_right_end[0]
while True:
res += 1
# if r can reach to the end of the whole garden, return res
if r>=N-1:return res
new_r = max(max_right_end[l:r+1])
# if next r is same as current r, it means we can not move forward, return -1
if new_r == r:return -1
l, r = r, new_r
Runtime of above code
Runtime: 140 ms, faster than 89.58% of Python3 online submissions for Minimum Number of Taps to Open to Water a Garden.
Memory Usage: 13 MB, less than 100.00% of Python3 online submissions for Minimum Number of Taps to Open to Water a Garden.A better one
Actually, for max_right_end, we can update it directly without compare with the old value, as we are looking from left to right, the second time that we reach a same left position will always have a wider coverage than the first one. So the code of this part can be writen more concisely.
class Solution:
def minTaps(self, n: int, A: List[int]) -> int:
if not A: return 0
N = len(A)
# For all location of taps, store the largest right reach point
max_right_end = list(range(N))
for i, a in enumerate(A):
# we can update the max right end list directly as it can garuantee the later update will reach a higher value
max_right_end[max(i - a, 0)] = min(i + a, N-1) res, l, r = 0, 0, max_right_end[0]
while True:
res += 1
# if r can reach to the end of the whole garden, return res
if r>=N-1:return res
new_r = max(max_right_end[l:r+1])
# if next r is same as current r, it means we can not move forward, return -1
if new_r == r:return -1
l, r = r, new_r
run time of this updated version
Runtime: 136 ms, faster than 93.01% of Python3 online submissions for Minimum Number of Taps to Open to Water a Garden.
Memory Usage: 13.2 MB, less than 100.00% of Python3 online submissions for Minimum Number of Taps to Open to Water a Garden.Reference
[1] https://leetcode.com/discuss/interview-question/363036/walmart-oa-2019-activate-fountains
