Leetcode-top150-cheatsheet(be continued)
Note: Only the optimal solu recorded, TC stands for time complexity, SC stands for space complexity.
Array / String
1. Merge Sorted Array
merge two non-decreasing ordered arrays in-place, ensuring the first array has enough space to store all elements.
Three pointers, fill the array backwards by comparing the tails of both arrays and placing the larger element into the next available end slot to avoid overwriting valid data, remember to deal with elements left in nums2, O(m + n) time complexity(TC), O(1) space complexity(SC).
code
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Standard solution: Merge backwards using three pointers
Time: O(m + n)
Space: O(1)
"""
# Three pointers:
p1 = m - 1 # Points to last valid element in nums1
p2 = n - 1 # Points to last element in nums2
p = m + n - 1 # Points to position where we place next element
# Merge from back to front
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
# If there are remaining elements in nums2, copy them
# (No need to handle remaining nums1 elements, they're already in place)
while p2 >= 0:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
2. Remove Element
Remove all elements of val in nums in-place, return the left nums length
Overwrite the target value with the array's last element and decrement the tail pointer, keeping the current pointer stationary to validate the new value, O(n) TC, O(1) SC,
code
class Solution2:
def removeElement(self, nums: List[int], val: int) -> int:
"""
Swap with end approach - Better when val occurrences are rare
Time: O(n), Space: O(1)
"""
left = 0
right = len(nums) - 1
while left <= right:
if nums[left] == val:
# Swap with element from the end
nums[left] = nums[right]
right -= 1
# Do not increment left yet, need to check swapped element
else:
left += 1
return left
3. Remove Duplicates from Sorted Array
remove the duplicates in-place in non-descreasing integer array, keeping the relative order of the elements the same.
Iterate through the list and record the current number to the slow pointer only when it marks the end of a sequence of identical values.
code
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
slow = 0
for fast in range(0, len(nums)):
if fast == len(nums) - 1 or nums[fast] != nums[fast+1]:
nums[slow] = nums[fast]
slow += 1
return slow
4. Remove Duplicates from Sorted Array II
remove the duplicates in-place in non-descreasing integer array such that each unique element appears at most twice, keeping the relative order of the elements the same.
Overwrite the slow pointer with the current element only if it differs from the element two positions back in the constructed valid sequence, effectively allowing at most two duplicates.
code
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
slow = 0
for fast in range(0, len(nums)):
if slow - 2 < 0 or nums[fast] != nums[slow - 2]:
# checking past:
nums[slow] = nums[fast]
slow += 1
return slow
5. Majority Element
Given an array nums of size n, return the majority element.(whose occurance more than [n/2], can assume always exists)
Boyer-Moore Voting, Maintain a candidate and a counter that increments for matches and decrements for mismatches, effectively canceling out distinct pairs until only the majority element remains, O(n) TC, O(1) SC
code
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate = nums[0]
count = 1
for num in nums[1:]:
if candidate == num:
count += 1
elif count > 0:
count -= 1
else:
candidate = num
count = 1
return candidate
6. Rotate Array
Given an integer array nums, rotate the array to the right by k steps in-place, with O(1) SC.
Three-Reversal Algorithm: Reverse the entire array to move the tail segment to the front(AB -> B'A'), then reverse each segment individually to restore their internal element order(B'A' -> BA).
code
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
n = len(nums)
k %= n # avoid out of boundary error
reverse(nums, 0, n - 1)
reverse(nums, 0, k - 1)
reverse(nums, k, n - 1)
7. Best time to buy and sell
given prices,choose a single day to buy and a different day in the future to sell, return maximum profit, or 0 if cannot achieve any profit.
Iterate through prices while dynamically tracking the lowest buying price seen so far and calculating the potential profit if sold today, keeping the maximum result.
code
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = float('inf')
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
cur_profit = price - min_price
max_profit = max(cur_profit, max_profit)
return max_profit
7. Best time to buy and sell II
given prices, can buy and/or sell on each day, but can only hold at most one stock at any time, can sell and buy the stock mutiple times on the same day. return the maximum profit.
Greedy Approach: Iterate through the array, any time the price increases from one day to the next, add that profit to our total.
code
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i-1]
return profit
8. Jump Game
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Greedy Approach: Iterate through the array to greedily update the furthest reachable index, ensuring the current position is within bounds until the target is reached.
code
class Solution:
def canJump(self, nums: List[int]) -> bool:
# (exploiting the continuity) if I try to reach the farthest point each time, store it, so we can do early stop if we go too far (can we skip some step? no)
target_index = len(nums) - 1
if target_index == 0:
return True
furthest_index = 0
for idx, num in enumerate(nums):
if idx > furthest_index:
return False
furthest_index = max(furthest_index, idx + num)
if furthest_index >= target_index:
return True
9. Jump Game II
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return the minimum number of jumps to reach index n - 1, (you can always reach n - 1)
Implicit BFS: Iterate through the array to expand the current reach window, incrementing the jump count only when the boundary of the current level is reached to proceed to the next reachable range.
code
class Solution:
def canJump(self, nums: List[int]) -> bool:
# (exploiting the continuity) if I try to reach the farthest point each time, store it, so we can do early stop if we go too far (can we skip some step? no)
target_index = len(nums) - 1
if target_index == 0:
return True
furthest_index = 0
for idx, num in enumerate(nums):
if idx > furthest_index:
return False
furthest_index = max(furthest_index, idx + num)
if furthest_index >= target_index:
return True
10. H-Index
Given an array citations for each paper, return h-index(the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.)
Counting sort, O(n) TC, We trade space for time by using a frequency array (buckets) to count citations capped at N, then iterate backwards to find the largest index i where the cumulative count of papers is at least i.
code
class Solution:
def hIndex(self, citations: List[int]) -> int:
n = len(citations)
bucket = [0] * (n + 1)
for c in citations:
bucket[min(c, n)] += 1
count = 0
for i in range(n, -1, -1):
count += bucket[i]
if count >= i:
return i
return 0
Reference:
- "Cracking the coding interview"
- Gemini 3 pro