Solution to LeetCode 76 Minimum Window Substring & LeetCode 209 Minimum Size Subarray Sum & LeetCode 904 Fruit Into Baskets
LeetCode 76
Minimum Window Substring (Hard) [link]
LeetCode 209
Minimum Size Subarray Sum (Medium) [link]
1] Brute Force Solution. (ETL) Time complexity O(n^2). Space complexity O(1).
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
min_res = float('inf')
for i in range(len(nums)):
SUM = 0
for j in range(i,len(nums)):
SUM += nums[j]
if SUM >= target:
min_res = min(min_res, j-i+1)
if min_res == float('inf'):
return 0
else:
return min_res
2] Sliding Window. If we only use one for loop, the index must represent the end point of the sliding window. The end pointer moves only when the sum is smaller than the target. The start pointer moves one step to remove the first value, then the end pointer moves one step to include the next value. This proceeds until we find the shortest valid subarray.
The time reduces because of the idea of changing the start point of the sliding window according to the sum of the subarray. Time complexity O(n). Space complexity O(1).
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
SUM = 0
min_res = float('inf')
slow = 0
for i in range(len(nums)):
SUM += nums[i]
while SUM >= target:
min_res = min(min_res, i-slow+1)
SUM -= nums[slow]
slow += 1
return min_res if min_res != float('inf') else 0
LeetCode 904
Fruit Into Baskets (Medium) [link]
1] Sliding Window. Time complexity O(n). Space complexity O(n). When it requires a specific number of shrinking of sliding window, use dictionary to keep track of the steps.
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
slow = 0
max_res = 0
cnt = collections.defaultdict(int)
for i in range(len(fruits)):
cnt[fruits[i]] += 1
while len(cnt) > 2:
cnt[fruits[slow]] -= 1
if cnt[fruits[slow]] == 0:
del cnt[fruits[slow]]
slow += 1
max_res = max(i-slow+1, max_res)
return max_res
2] Not good to use set here (ETL)
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
slow = 0
max_res = 0
for i in range(len(fruits)):
if len(set(fruits[slow:i+1])) <= 2:
max_res = max(i-slow+1, max_res)
while len(set(fruits[slow:i+1])) > 2:
slow += 1
return max_res
