Documenting LeetCode solving.
Q1
Hard. Two pointers
How much water the current position i can trap depends on this formula:
water = min(leftMax, rightMax) - height[i].
leftMax: Maximum height on the left.
rightMax: Maximum height on the right.
class Solution:
def trap(self, height: List[int]) -> int:
res = 0
l, r = 0, len(height) - 1
leftMax, rightMax = height[l], height[r]
while l < r:
if leftMax < rightMax:
l += 1
leftMax = max(leftMax, height[l])
res += leftMax - height[l]
else:
r -= 1
rightMax = max(rightMax, height[r])
res += rightMax - height[r]
return res
Q2
121. Best Time to Buy and Sell Stock
Easy. Sliding Window
class Solution:
def maxProfit(self, prices: List[int]) -> int:
l, r = 0, 1
maxProfit = 0
while r < len(prices):
if prices[r] - prices[l] < 0:
l = r # Shift to the lowest price
else:
maxProfit = max(maxProfit, prices[r] - prices[l])
r += 1
return maxProfit
Q3
3. Longest Substring Without Repeating Characters
Medium. Sliding window
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
charSet = set()
longest = 0
l = 0
for r in range(len(s)):
# Check duplicates
while s[r] in charSet:
charSet.remove(s[l])
l += 1
charSet.add(s[r])
longest = max(longest, r - l + 1)
return longest