Jul 15, 2024 | monday 3:14 pm
This series will be mainly focused for my own accountability and reference, as well as anyone who wants to follow my journey to becoming a better problem solver. Each week, I will highlight problems that I thought was interesting or difficult. Additionally, other problems that I solved and their solutions are listed below.
MediumTwo-pointers
Try it yourself here!
This problem is the third in the “Two Sum” series. Here, we are asked to find all unique triplets in the array that sum to zero.
Key edge case:
Example: [-1, 0, 1, 2, -1, -4] Finding three numbers that sum to zero is simple. Starting from -1, there are two possible solutions: [-1, 0, 1], and [-1, 2, -1]. Scanning the rest of the array, these two solutions are duplicates with 0, 1, 2, and -1. Thus, an important piece to this solution is handling duplicate solutions.
My approach to solving this problem was to transform the threeSum problem into a twoSum problem. I realized that I could use twoSum to find pairs of numbers that sum to the negative of a third number, resulting in a total sum of zero. Since the input array is unsorted, I decided to sort it first. This allows me to efficiently find negative numbers and apply the twoSum algorithm on the rest of the sorted array. There are two places in the algorithm where duplicate solutions could occur:
To avoid duplicates, I ensure that the current number isn’t equal to the previous one when iterating. In the twoSum part, I chose to check the lower pointer to avoid duplicates, but this check could also be done with the higher pointer. My algorithm is as follows:
Complexity:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
def twoSum(curr, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
sum = curr + nums[lo] + nums[hi]
if sum == 0:
res.append([curr, nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
elif sum > 0:
hi -= 1
else:
lo += 1
for i in range(len(nums)):
if nums[i] > 0:
break
if i == 0 or nums[i] != nums[i - 1]:
twoSum(nums[i], nums[i+1:])
return res
EasyStack
Try it yourself here!
def isValid(self, s: str) -> bool:
stack = []
mapping = {")" : "(", "}" : "{", "]" : "["}
for char in s:
if char in mapping:
if not stack or stack.pop() != mapping[char]:
return False
else:
stack.append(char)
return not stack
Complexity:
MediumStack
Try it yourself here!
class MinStack:
def __init__(self):
self.stk = []
self.minstk = []
def push(self, val: int) -> None:
self.stk.append(val)
if not self.minstk or self.minstk[-1] >= val:
self.minstk.append(val)
def pop(self) -> None:
val = self.stk.pop()
if val == self.minstk[-1]:
self.minstk.pop()
def top(self) -> int:
return self.stk[-1]
def getMin(self) -> int:
return self.minstk[-1]
Complexity:
MediumStack
Try it yourself here!
def evalRPN(self, tokens: List[str]) -> int:
stk = []
operations = {
"+": lambda a, b: a + b,
"-": lambda a, b: a - b,
"/": lambda a, b: int(a / b),
"*": lambda a, b: a * b
}
for t in tokens:
if t in operations:
x = stk.pop()
y = stk.pop()
stk.append(operations[t](y, x))
else:
stk.append(int(t))
return stk.pop()
Complexity:
EasyTwo-pointers
Try it yourself here!
def isPalindrome(self, s: str) -> bool:
i, j = 0, len(s) - 1
while i < j:
while i < j and not s[i].isalnum():
i += 1
while i < j and not s[j].isalnum():
j -= 1
if s[i].lower() != s[j].lower():
return False
i += 1
j -= 1
return True
Complexity:
MediumTwo-pointers
Try it yourself here!
def twoSum(self, numbers: List[int], target: int) -> List[int]:
lo, hi = 0, len(numbers) - 1
while lo <= hi:
sum = numbers[lo] + numbers[hi]
if sum == target:
return [lo + 1, hi + 1]
elif sum > target:
hi -= 1
else:
lo += 1
return [-1, -1]
Complexity:
MediumTwo-pointers
Try it yourself here!
def maxArea(self, height: List[int]) -> int:
# example: [1, 11, 9, 2, 5, 10, 11]
# ans = 11 * 5 = 55
res = 0
l, r = 0, len(height) - 1
while l < r:
area = min(height[l], height[r]) * (r - l)
res = max(area, res)
if height[l] > height[r]:
r -= 1
else:
l += 1
return res
Complexity:
HardTwo-pointers
Try it yourself here!
def trap(self, height: List[int]) -> int:
ans = 0
size = len(height)
left, right = 0, len(height) - 1
leftMax, rightMax = 0,0
while left < right:
if height[left] < height[right]:
leftMax = max(leftMax, height[left])
ans += leftMax - height[left]
left += 1
else:
rightMax = max(rightMax, height[right])
ans += rightMax - height[right]
right -= 1
return ans
Complexity: