Amazon¶
Table of Contents¶
- 1. Two Sum (Easy)
- 42. Trapping Rain Water (Hard)
- 121. Best Time to Buy and Sell Stock (Easy)
- 3. Longest Substring Without Repeating Characters (Medium)
- 56. Merge Intervals (Medium)
- 49. Group Anagrams (Medium)
- 2. Add Two Numbers (Medium)
- 23. Merge k Sorted Lists (Hard)
- 15. 3Sum (Medium)
- 20. Valid Parentheses (Easy)
- 33. Search in Rotated Sorted Array (Medium)
- 53. Maximum Subarray (Medium)
- 138. Copy List with Random Pointer (Medium)
- 127. Word Ladder (Hard)
- 5. Longest Palindromic Substring (Medium)
- 79. Word Search (Medium)
- 88. Merge Sorted Array (Easy)
- 55. Jump Game (Medium)
- 70. Climbing Stairs (Easy)
- 22. Generate Parentheses (Medium)
- 128. Longest Consecutive Sequence (Medium)
- 14. Longest Common Prefix (Easy)
- 11. Container With Most Water (Medium)
- 140. Word Break II (Hard)
- 26. Remove Duplicates from Sorted Array (Easy)
- 21. Merge Two Sorted Lists (Easy)
- 45. Jump Game II (Medium)
- 54. Spiral Matrix (Medium)
- 34. Find First and Last Position of Element in Sorted Array (Medium)
- 62. Unique Paths (Medium)
1. Two Sum¶
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
"""Hash Map: O(n) time, O(n) space.
Store seen values so each number can find its complement in one pass.
"""
hashmap = {} # val: idx
for idx, val in enumerate(nums):
comp = target - val
if comp in hashmap:
return [hashmap[comp], idx]
hashmap[val] = idx
return []
def test_two_sum():
s = Solution()
assert s.twoSum([2, 7, 11, 15], 9) == [0, 1]
assert s.twoSum([3, 2, 4], 6) == [1, 2]
assert s.twoSum([3, 3], 6) == [0, 1]
assert s.twoSum([1, 2, 3, 4, 5], 10) == []
assert s.twoSum([-1, -2, -3, -4, -5], -8) == [2, 4]
#include <cassert>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (size_t i = 0; i < nums.size(); i++) {
int diff = target - nums[i];
if (map.find(diff) != map.end()) {
return {map[diff], (int)i};
}
map[nums[i]] = (int)i;
}
return {-1, -1};
}
};
int main() {
Solution solution;
vector<int> nums = {2, 7, 11, 15};
int target = 9;
vector<int> result = solution.twoSum(nums, target);
assert((result == vector<int>{0, 1}));
return 0;
}
42. Trapping Rain Water¶
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
"""Two Pointers: O(n) time, O(1) space.
Track max from each side; shorter side determines water level.
"""
left, right = 0, len(height) - 1
max_l = max_r = res = 0
while left < right:
if height[left] < height[right]:
max_l = max(max_l, height[left])
res += max_l - height[left]
left += 1
else:
max_r = max(max_r, height[right])
res += max_r - height[right]
right -= 1
return res
def trapDP(self, height: List[int]) -> int:
"""DP Prefix Max: O(n) time, O(n) space.
Precompute max heights from left and right.
"""
n = len(height)
max_left = [0] * n
max_right = [0] * n
for i in range(1, n):
max_left[i] = max(max_left[i - 1], height[i - 1])
for i in range(n - 2, -1, -1):
max_right[i] = max(max_right[i + 1], height[i + 1])
return sum(max(0, min(max_left[i], max_right[i]) - height[i]) for i in range(n))
def trapStack(self, height: List[int]) -> int:
"""Monotonic Stack: O(n) time, O(n) space.
Pop shorter bars and accumulate trapped water by layer.
"""
stack = []
res = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
top = stack.pop()
if not stack:
break
w = i - stack[-1] - 1
h = min(height[i], height[stack[-1]]) - height[top]
res += w * h
stack.append(i)
return res
def test_trap():
s = Solution()
for fn in (s.trap, s.trapDP, s.trapStack):
assert fn([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert fn([4, 2, 0, 3, 2, 5]) == 9
assert fn([1, 0, 1]) == 1
assert fn([]) == 0
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution
{
public:
int trap(vector<int> &height)
{
if (height.empty())
return 0;
int res = 0;
int left = 0, right = height.size() - 1;
int maxL = height[left], maxR = height[right];
while (left < right)
{
if (maxL < maxR)
{
left++;
maxL = max(maxL, height[left]);
res += maxL - height[left];
}
else
{
right--;
maxR = max(maxR, height[right]);
res += maxR - height[right];
}
}
return res;
}
};
int main()
{
vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Solution solution;
cout << solution.trap(height) << endl;
return 0;
}
121. Best Time to Buy and Sell Stock¶
"""
- Return the maximum profit that can be achieved from buying on one day and selling on another day.
"""
from typing import List
# Brute Force
def maxProfitBF(prices: List[int]) -> int:
max_profit = 0
n = len(prices)
for i in range(n):
for j in range(i + 1, n):
max_profit = max(max_profit, prices[j] - prices[i])
return max_profit
# DP
def maxProfitDP(prices: List[int]) -> int:
dp = [[0] * 2 for _ in range(len(prices))]
dp[0][0] = -prices[0] # buy
dp[0][1] = 0 # sell
for i in range(1, len(prices)):
dp[i][0] = max(dp[i - 1][0], -prices[i]) # the lowest price to buy
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
return dp[-1][1]
# Greedy
def maxProfitGreedy(prices: List[int]) -> int:
max_profit = 0
seen_min = prices[0]
for i in range(1, len(prices)):
max_profit = max(max_profit, prices[i] - seen_min)
seen_min = min(seen_min, prices[i])
return max_profit
# Fast Slow Pointers
def maxProfitFS(prices: List[int]) -> int:
max_profit = 0
slow, fast = 0, 1
while fast < len(prices):
if prices[fast] > prices[slow]:
max_profit = max(max_profit, prices[fast] - prices[slow])
else:
slow = fast
fast += 1
return max_profit
# |------------|------- |---------|
# | Approach | Time | Space |
# |------------|--------|---------|
# | Brute Force| O(n^2)| O(1) |
# | DP | O(n) | O(n) |
# | Greedy | O(n) | O(1) |
# | Fast Slow | O(n) | O(1) |
# |------------|--------|---------|
prices = [7, 1, 5, 3, 6, 4]
print(maxProfitBF(prices)) # 5
print(maxProfitDP(prices)) # 5
print(maxProfitGreedy(prices)) # 5
print(maxProfitFS(prices)) # 5
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfitMemo(vector<int> &prices) {
if (prices.size() <= 1) return 0;
int seen_min = prices[0];
int res = 0;
for (int &price : prices) {
res = max(res, price - seen_min);
seen_min = min(seen_min, price);
}
return res;
}
};
int main() {
vector<int> prices = {7, 1, 5, 3, 6, 4};
Solution obj;
cout << obj.maxProfitMemo(prices) << endl;
return 0;
}
3. Longest Substring Without Repeating Characters¶
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
"""Sliding Window: O(n) time, O(min(n, charset)) space.
Jump the left edge past each repeated character's previous index.
"""
left = 0
res = 0
seen = {}
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
res = max(res, right - left + 1)
return res
def lengthOfLongestSubstringSet(self, s: str) -> int:
"""Sliding Window Set: O(n) time, O(min(n, charset)) space.
Shrink until the current character is unique in the window.
"""
left = 0
res = 0
window = set()
for right, ch in enumerate(s):
while ch in window:
window.remove(s[left])
left += 1
window.add(ch)
res = max(res, right - left + 1)
return res
def test_length_of_longest_substring():
s = Solution()
cases = [
("abcabcbb", 3),
("bbbbb", 1),
("pwwkew", 3),
("", 0),
(" ", 1),
("abba", 2),
("dvdf", 3),
]
for text, expected in cases:
assert s.lengthOfLongestSubstring(text) == expected
assert s.lengthOfLongestSubstringSet(text) == expected
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int lengthOfLongestSubstring(string s) {
int n = s.length();
int res = 0;
int left = 0;
unordered_set<char> window;
for (int right = 0; right < n; right++) {
char ch = s[right];
while (window.find(ch) != window.end()) {
window.erase(s[left]);
left++;
}
window.insert(ch);
res = max(res, right - left + 1);
}
return (int)res;
}
int main() {
string s = "abcabcbb";
cout << lengthOfLongestSubstring(s) << endl; // 3
s = "bbbbb";
cout << lengthOfLongestSubstring(s) << endl; // 1
s = "pwwkew";
cout << lengthOfLongestSubstring(s) << endl; // 3
return 0;
}
56. Merge Intervals¶
def merge(intervals: list[list[int]]) -> list[list[int]]:
"""
Merge all overlapping intervals.
| G----H
| E===========F
| C--------D
| A========B
|
|-----------------------------------
Draw the above to explain the process to the interviewer.
Time complexity: O(nlogn) due to sorting.
Space complexity: O(n) for the result list.
"""
n = len(intervals)
if n <= 1:
return intervals
intervals.sort(key=lambda x: x[0])
res = [intervals[0]]
for i in range(1, n):
if intervals[i][0] <= res[-1][1]:
res[-1][1] = max(res[-1][1], intervals[i][1])
else:
res.append(intervals[i])
return res
print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// Interval
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& range : intervals) {
if (!res.empty() && range[0] <= res.back()[1]) {
res.back()[1] = max(res.back()[1], range[1]);
} else {
res.emplace_back(range);
}
}
return res;
}
int main() {
vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
vector<vector<int>> res = merge(intervals);
for (auto& range : res) {
cout << range[0] << ", " << range[1] << endl;
}
return 0;
}
49. Group Anagrams¶
from collections import defaultdict
from typing import List
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
"""Counting Hash Map: O(n * k) time, O(n) space.
Words with the same 26-letter frequency tuple are anagrams.
"""
groups = defaultdict(list)
for word in strs:
counts = [0] * 26
for ch in word:
counts[ord(ch) - ord("a")] += 1
groups[tuple(counts)].append(word)
return list(groups.values())
def test_group_anagrams():
def normalized(groups):
return sorted(sorted(group) for group in groups)
s = Solution()
result = s.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
assert normalized(result) == [
["ate", "eat", "tea"],
["bat"],
["nat", "tan"],
]
assert normalized(s.groupAnagrams([""])) == [[""]]
assert normalized(s.groupAnagrams(["a"])) == [["a"]]
#include <algorithm>
#include <cassert>
#include <ranges>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> map;
for (string& s : strs) {
string sorted = s;
ranges::sort(sorted);
map[sorted].push_back(s);
}
vector<vector<string>> res;
for (auto& kv : map) {
res.push_back(kv.second);
}
return res;
}
};
int main() {
Solution solution;
vector<string> strs = {"eat", "tea", "tan"};
vector<vector<string>> res = solution.groupAnagrams(strs);
assert((res == vector<vector<string>>{{"eat", "tea"}, {"tan"}} ||
res == vector<vector<string>>{{"tan"}, {"eat", "tea"}}));
return 0;
}
2. Add Two Numbers¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
class Solution:
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
"""Digit Carry Simulation: O(max(m, n)) time, O(max(m, n)) space.
Walk both reversed lists while carrying overflow into the next digit.
"""
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
carry, val = divmod(v1 + v2 + carry, 10)
cur.next = ListNode(val)
cur = cur.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
def test_add_two_numbers():
s = Solution()
l1 = LinkedList([2, 4, 3]).head
l2 = LinkedList([5, 6, 4]).head
assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [7, 0, 8]
l1 = LinkedList([0]).head
l2 = LinkedList([0]).head
assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [0]
l1 = LinkedList([9, 9, 9, 9, 9, 9, 9]).head
l2 = LinkedList([9, 9, 9, 9]).head
assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [
8,
9,
9,
9,
0,
0,
0,
1,
]
#include <cassert>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy;
ListNode* cur = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
if (l1) {
carry += l1->val;
l1 = l1->next;
}
if (l2) {
carry += l2->val;
l2 = l2->next;
}
cur->next = new ListNode(carry % 10);
cur = cur->next;
carry /= 10;
}
return dummy.next;
}
};
int main() {
Solution sol;
ListNode* l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
ListNode* l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
ListNode* result = sol.addTwoNumbers(l1, l2);
vector<int> expected = {7, 0, 8};
for (int val : expected) {
assert(result != nullptr && result->val == val);
result = result->next;
}
assert(result == nullptr); // End of list
return 0;
}
23. Merge k Sorted Lists¶
"""
- Prerequisite: 21. Merge Two Sorted Lists
- Video explanation: [23. Merge K Sorted Lists - NeetCode](https://youtu.be/q5a5OiGbT6Q?si=SQ2dCvsYQ3LQctPh)
"""
import copy
import heapq
from typing import List, Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def merge_k_lists_divide_conquer(
lists: List[Optional[ListNode]],
) -> Optional[ListNode]:
if not lists or len(lists) == 0:
return None
def mergeTwo(l1, l2):
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i + 1] if i + 1 < len(lists) else None
merged.append(mergeTwo(l1, l2))
lists = merged
return lists[0]
def merge_k_lists_heap(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
min_heap = [] # (val, idx, node)
for idx, head in enumerate(lists):
if head:
heapq.heappush(min_heap, (head.val, idx, head))
while min_heap:
_, idx, node = heapq.heappop(min_heap)
cur.next = node
cur = cur.next
node = node.next
if node:
heapq.heappush(min_heap, (node.val, idx, node))
return dummy.next
def test_merge_k_lists() -> None:
n1 = list_from_array([1, 4])
n2 = list_from_array([1, 3])
n3 = list_from_array([2, 6])
lists = [n1, n2, n3]
lists1 = copy.deepcopy(lists)
lists2 = copy.deepcopy(lists)
assert (list_to_array(merge_k_lists_divide_conquer(lists1))) == [
1,
1,
2,
3,
4,
6,
]
assert (list_to_array(merge_k_lists_heap(lists2))) == [1, 1, 2, 3, 4, 6]
15. 3Sum¶
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
"""Two Pointers: O(n^2) time, O(1) space.
Sort, fix one element, then two-pointer scan for complement.
"""
n = len(nums)
if n <= 2:
return []
res = []
nums.sort()
for k in range(n - 2):
if k > 0 and nums[k] == nums[k - 1]:
continue
i, j = k + 1, n - 1
while i < j:
total = nums[k] + nums[i] + nums[j]
if total > 0:
j -= 1
elif total < 0:
i += 1
else:
res.append([nums[k], nums[i], nums[j]])
while i < j and nums[i] == nums[i + 1]:
i += 1
while i < j and nums[j] == nums[j - 1]:
j -= 1
i += 1
j -= 1
return res
def test_three_sum():
s = Solution()
for fn in (s.threeSum,):
assert fn([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert fn([0, 1, 1]) == []
assert fn([0, 0, 0]) == [[0, 0, 0]]
assert fn([]) == []
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int n = nums.size();
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1, right = n - 1;
while (left < right) {
int total = nums[i] + nums[left] + nums[right];
if (total > 0)
right--;
else if (total < 0)
left++;
else {
res.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return res;
}
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4};
vector<vector<int>> res = threeSum(nums);
for (auto& v : res) {
for (int i : v) {
cout << i << " ";
}
cout << endl;
}
return 0;
}
20. Valid Parentheses¶
# Stack
def is_valid(s: str) -> bool:
if len(s) % 2:
return False
pairs = {
"(": ")",
"{": "}",
"[": "]",
}
stack = []
for ch in s:
if ch in pairs:
stack.append(ch)
elif not stack or ch != pairs[stack.pop()]:
return False
return True if not stack else False
def test_is_valid():
assert is_valid("()[]{}")
assert not is_valid("(]")
assert not is_valid("([)]")
assert is_valid("{[]}")
#include <cassert>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
bool isValid(string s) {
unordered_map<char, char> map{{')', '('}, {'}', '{'}, {']', '['}};
stack<char> stack;
if (s.length() % 2 == 1) return false;
for (char& ch : s) {
if (stack.empty() || map.find(ch) == map.end()) {
stack.push(ch);
} else {
if (map[ch] != stack.top()) {
return false;
}
stack.pop();
}
}
return stack.empty();
}
};
int main() {
Solution s;
assert(s.isValid("()") == true);
assert(s.isValid("()[]{}") == true);
assert(s.isValid("(]") == false);
assert(s.isValid("([)]") == false);
assert(s.isValid("{[]}") == true);
return 0;
}
33. Search in Rotated Sorted Array¶
from typing import List
# Binary Search
def search(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
print(search(nums, target)) # 4
53. Maximum Subarray¶
from typing import List
# DP Kadane
def maxSubArrayDP(nums: List[int]) -> int:
n = len(nums)
dp = [0 for _ in range(n)]
dp[0] = nums[0]
res = nums[0]
for i in range(1, n):
dp[i] = max(
dp[i - 1] + nums[i], # continue the previous subarray
nums[i], # start a new subarray
)
res = max(res, dp[i])
return res
# Greedy
def maxSubArrayGreedy(nums: List[int]) -> int:
max_sum = nums[0]
cur_sum = 0
for num in nums:
cur_sum = max(cur_sum + num, num)
max_sum = max(max_sum, cur_sum)
return max_sum
# Prefix Sum
def maxSubArrayPrefixSum(nums: List[int]) -> int:
prefix_sum = 0
prefix_sum_min = 0
res = float("-inf")
for num in nums:
prefix_sum += num
res = max(res, prefix_sum - prefix_sum_min)
prefix_sum_min = min(prefix_sum_min, prefix_sum)
return res
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArrayDP(nums)) # 6
print(maxSubArrayGreedy(nums)) # 6
print(maxSubArrayPrefixSum(nums)) # 6
138. Copy List with Random Pointer¶
from typing import Optional
class Node:
def __init__(self, x: int, next: "Node" = None, random: "Node" = None):
self.val = int(x)
self.next = next
self.random = random
def copyRandomList(head: "Optional[Node]") -> "Optional[Node]":
if not head:
return None
# Copy nodes and link them together
cur = head
while cur:
new_node = Node(cur.val)
new_node.next = cur.next
cur.next = new_node
cur = new_node.next
# Copy random pointers
cur = head
while cur:
cur.next.random = cur.random.next if cur.random else None
cur = cur.next.next
# Separate the original and copied lists
cur = head
new_head = head.next
while cur:
new_node = cur.next
cur.next = new_node.next
new_node.next = new_node.next.next if new_node.next else None
cur = cur.next
return new_head
127. Word Ladder¶
"""
- The most classic BFS problem.
- Return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
- Approach: BFS
- Time Complexity: O(n * m^2)
- Space Complexity: O(n * m)
"""
from collections import defaultdict, deque
from typing import List
# BFS
def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
n = len(beginWord)
graph = defaultdict(list) # pattern: words
wordList.append(beginWord)
for word in wordList:
for i in range(n):
pattern = word[:i] + "*" + word[i + 1 :]
graph[pattern].append(word)
visited = set([beginWord])
q = deque([beginWord])
res = 1
while q:
size = len(q)
for _ in range(size):
word = q.popleft()
if word == endWord:
return res
for i in range(n):
pattern = word[:i] + "*" + word[i + 1 :]
for neighbor in graph[pattern]:
if neighbor not in visited:
visited.add(neighbor)
q.append(neighbor)
res += 1
return 0
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
print(ladderLength(beginWord, endWord, wordList)) # 5
5. Longest Palindromic Substring¶
class longestPalindrome:
"""Return the longest palindromic substring in s."""
@staticmethod
def dp(s: str) -> str:
n = len(s)
if n <= 1:
return s
start, maxLen = 0, 1
# Init
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
# update
for j in range(1, n):
for i in range(j):
if s[i] == s[j]:
if j - i <= 2:
dp[i][j] = 1
else:
dp[i][j] = dp[i + 1][j - 1]
if dp[i][j] and j - i + 1 > maxLen:
maxLen = j - i + 1
start = i
return s[start : start + maxLen]
@staticmethod
def expand_around_center(s: str) -> str:
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
if len(s) <= 1:
return s
start, end = 0, 0
for i in range(len(s)):
odd = expand(i, i)
even = expand(i, i + 1)
maxLen = max(odd, even)
if maxLen > end - start:
start = i - (maxLen - 1) // 2
end = i + maxLen // 2
return s[start : end + 1]
if __name__ == "__main__":
s = "babad"
assert longestPalindrome.dp(s) in ["bab", "aba"]
assert longestPalindrome.expand_around_center(s) in ["bab", "aba"]
79. Word Search¶
from typing import List
def exist(board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
path = set()
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
def dfs(r, c, i):
if i == len(word):
return True
if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[i] or (r, c) in path:
return False
path.add((r, c))
for dr, dc in dirs:
if dfs(r + dr, c + dc, i + 1):
return True
path.remove((r, c))
return False
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
board = [
["A", "B", "C", "E"],
["S", "F", "C", "S"],
["A", "D", "E", "E"],
]
word = "ABCCED"
print(exist(board, word)) # True
88. Merge Sorted Array¶
from typing import List
class merge:
@staticmethod
def lr(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1, p2, t = m - 1, n - 1, m + n - 1
while p1 >= 0 or p2 >= 0:
if p1 == -1:
nums1[t] = nums2[p2]
p2 -= 1
elif p2 == -1:
nums1[t] = nums1[p1]
p1 -= 1
elif nums1[p1] > nums2[p2]:
nums1[t] = nums1[p1]
p1 -= 1
else:
nums1[t] = nums2[p2]
p2 -= 1
t -= 1
if __name__ == "__main__":
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
merge.lr(nums1, m, nums2, n)
assert nums1 == [1, 2, 2, 3, 5, 6]
#include <cassert>
#include <vector>
using namespace std;
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1, t = m + n - 1;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
nums1[t] = nums2[p2];
p2--;
} else if (p2 == -1) {
nums1[t] = nums1[p1];
p1--;
} else if (nums1[p1] > nums2[p2]) {
nums1[t] = nums1[p1];
p1--;
} else {
nums1[t] = nums2[p2];
p2--;
}
t--;
}
}
};
int main() {
Solution solution;
vector<int> nums1 = {1, 3, 6, 0, 0, 0};
vector<int> nums2 = {2, 5, 6};
vector<int> output = {1, 2, 3, 5, 6, 6};
solution.merge(nums1, 3, nums2, 3);
assert(nums1 == output);
return 0;
}
55. Jump Game¶
"""
- Return `True` if you can reach the last index, otherwise `False`.
"""
from typing import List
# Greedy - Interval
def canJump(nums: List[int]) -> bool:
n = len(nums)
reach = 0
i = 0
while reach >= i:
if reach >= n - 1:
return True
reach = max(reach, i + nums[i])
i += 1
return False
if __name__ == "__main__":
assert canJump([2, 3, 1, 1, 4]) is True
assert canJump([3, 2, 1, 0, 4]) is False
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool canJump(vector<int>& nums) {
int canReach = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (i > canReach) return false;
canReach = max(canReach, i + nums[i]);
}
return true;
}
};
int main() {
Solution obj;
vector<int> nums = {2, 3, 1, 1, 4};
cout << obj.canJump(nums) << endl;
return 0;
}
70. Climbing Stairs¶
from functools import cache
class Solution:
def climbStairs(self, n: int) -> int:
"""Optimized DP: O(n) time, O(1) space.
Only the previous two counts are needed to compute the next stair.
"""
if n <= 2:
return n
first, second = 1, 2
for _ in range(3, n + 1):
first, second = second, first + second
return second
def climbStairsDP(self, n: int) -> int:
"""Tabulation DP: O(n) time, O(n) space.
Each stair count is the sum of the ways to reach the previous two stairs.
"""
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
def climbStairsGreedy(self, n: int) -> int:
"""Greedy Rolling Counts: O(n) time, O(1) space.
The next answer is always determined by the two latest reachable counts.
"""
if n <= 2:
return n
prev, cur = 1, 2
for _ in range(3, n + 1):
prev, cur = cur, prev + cur
return cur
def climbStairsDFS(self, n: int) -> int:
"""Memoized DFS: O(n) time, O(n) space.
Caching prevents recomputing the same remaining-stair subproblems.
"""
@cache
def dfs(i: int) -> int:
if i <= 2:
return i
return dfs(i - 1) + dfs(i - 2)
return dfs(n)
def test_climb_stairs():
s = Solution()
for fn in (
s.climbStairs,
s.climbStairsDP,
s.climbStairsGreedy,
s.climbStairsDFS,
):
assert fn(1) == 1
assert fn(2) == 2
assert fn(3) == 3
assert fn(10) == 89
#include <cassert>
#include <iostream>
using namespace std;
int climbStairs(int n) {
if (n <= 2) return n;
int f1 = 1, f2 = 2;
int res;
int i = 3;
while (i <= n) {
res = f1 + f2;
f1 = f2;
f2 = res;
i++;
}
return res;
}
int main() {
assert(climbStairs(2) == 2);
assert(climbStairs(5) == 8);
assert(climbStairs(10) == 89);
return 0;
}
22. Generate Parentheses¶
from typing import List
# Backtracking
def generateParenthesis1(n: int) -> List[str]:
path, res = [], []
def dfs(openN, closeN):
if openN == closeN == n:
res.append("".join(path))
return
if openN < n:
path.append("(")
dfs(openN + 1, closeN)
path.pop()
if closeN < openN:
path.append(")")
dfs(openN, closeN + 1)
path.pop()
dfs(0, 0)
return res
# Backtracking
def generateParenthesis2(n: int) -> List[str]:
m = n * 2
res, path = [], [""] * m
def dfs(i, left):
if i == m:
res.append("".join(path))
return
if left < n:
path[i] = "("
dfs(i + 1, left + 1)
if i - left < left:
path[i] = ")"
dfs(i + 1, left)
dfs(0, 0)
return res
if __name__ == "__main__":
print(generateParenthesis1(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']
print(generateParenthesis2(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']
128. Longest Consecutive Sequence¶
from typing import List
# Set
def longestConsecutiveSet(nums: List[int]) -> int:
num_set = set(nums) # O(n)
longest = 0
for n in nums:
if (n - 1) not in num_set: # left boundary
length = 1
while (n + length) in num_set:
length += 1
longest = max(longest, length)
return longest
# Union Find
def longestConsecutiveUF(nums: List[int]) -> int:
if not nums:
return 0
par = {num: num for num in nums}
rank = {num: 1 for num in nums}
def find(num):
p = par[num]
while p != par[p]:
p = par[p]
return p
def union(num1, num2):
p1, p2 = find(num1), find(num2)
if p1 == p2:
return
if rank[p1] < rank[p2]:
par[p1] = p2
rank[p2] += rank[p1]
else:
par[p2] = p1
rank[p1] += rank[p2]
for num in nums:
if num - 1 in par:
union(num, num - 1)
return max(rank.values())
# |------------|------- |---------|
# | Approach | Time | Space |
# |------------|--------|---------|
# | Set | O(N) | O(N) |
# | Union Find | O(N) | O(N) |
# |------------|--------|---------|
nums = [100, 4, 200, 1, 3, 2]
print(longestConsecutiveSet(nums)) # 4
print(longestConsecutiveUF(nums)) # 4
14. Longest Common Prefix¶
from typing import List
class longestCommonPrefix:
def horizontal_scan(self, strs: List[str]) -> str:
if not strs:
return ""
prefix = strs[0]
for i in range(1, len(strs)):
while not strs[i].startswith(prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
def vertical_scan(self, strs: List[str]) -> str:
if not strs:
return ""
for i in range(len(strs[0])):
char = strs[0][i]
for j in range(1, len(strs)):
if i >= len(strs[j]) or strs[j][i] != char:
return strs[0][:i]
return strs[0]
def divide_conquer(self, strs: List[str]) -> str:
if not strs:
return ""
def merge(left, right):
n = min(len(left), len(right))
for i in range(n):
if left[i] != right[i]:
return left[:i]
return left[:n]
def find(strs, start, end):
if start == end:
return strs[start]
mid = start + (end - start) // 2
left = find(strs, start, mid)
right = find(strs, mid + 1, end)
return merge(left, right)
return find(strs, 0, len(strs) - 1)
def binary_search(self, strs: List[str]) -> str:
if not strs:
return ""
def isCommonPrefix(strs, length):
prefix = strs[0][:length]
return all(s.startswith(prefix) for s in strs)
minLen = min(len(s) for s in strs)
low, high = 0, minLen
while low < high:
mid = low + (high - low) // 2
if isCommonPrefix(strs, mid + 1):
low = mid + 1
else:
high = mid
return strs[0][:low]
if __name__ == "__main__":
solution = longestCommonPrefix()
strs = ["flower", "flow", "flight"]
assert solution.horizontal_scan(strs) == "fl"
assert solution.vertical_scan(strs) == "fl"
assert solution.divide_conquer(strs) == "fl"
assert solution.binary_search(strs) == "fl"
11. Container With Most Water¶
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
"""Two Pointers: O(n) time, O(1) space.
Move the shorter side inward to potentially find a taller line.
"""
left, right = 0, len(height) - 1
res = 0
while left < right:
w = right - left
h = min(height[left], height[right])
res = max(res, w * h)
if height[left] < height[right]:
left += 1
else:
right -= 1
return res
def maxAreaBF(self, height: List[int]) -> int:
"""Brute Force: O(n^2) time, O(1) space.
Check every pair of lines.
"""
res = 0
for i in range(len(height)):
for j in range(i + 1, len(height)):
res = max(res, min(height[i], height[j]) * (j - i))
return res
def test_max_area():
s = Solution()
for fn in (s.maxArea, s.maxAreaBF):
assert fn([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
assert fn([1, 1]) == 1
assert fn([4, 3, 2, 1, 4]) == 16
assert fn([1, 2, 1]) == 2
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int res = 0;
while (left < right) {
int h = min(height[left], height[right]);
int w = right - left;
res = max(res, h * w);
if (height[left] < height[right])
left++;
else
right--;
}
return res;
}
int main() {
vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
cout << maxArea(height) << endl; // 49
return 0;
}
140. Word Break II¶
26. Remove Duplicates from Sorted Array¶
from typing import List
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
"""Two Pointers: O(n) time, O(1) space.
Keep `left` at the last unique value and overwrite the next position
whenever `right` finds a different value.
Example: nums = [0, 0, 1, 1, 2]
start: left = 0, unique prefix = [0]
right 0: 0 == 0 -> unchanged
right 1: 0 == 0 -> unchanged
right 2: 1 != 0 -> left = 1, prefix = [0, 1]
right 3: 1 == 1 -> unchanged
right 4: 2 != 1 -> left = 2, prefix = [0, 1, 2]
Return 3; the first three values are [0, 1, 2].
"""
if not nums:
return 0
n = len(nums)
left = 0
for right in range(n):
if nums[right] != nums[left]:
left += 1
nums[left] = nums[right]
return left + 1
def test_remove_duplicates():
s = Solution()
for fn in (s.removeDuplicates,):
cases = [
([], []),
([1], [1]),
([1, 1, 2], [1, 2]),
([0, 0, 1, 1, 1, 2, 2, 3, 3, 4], [0, 1, 2, 3, 4]),
]
for nums, expected in cases:
k = fn(nums)
assert k == len(expected)
assert nums[:k] == expected
#include <cassert>
#include <vector>
using namespace std;
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int fast = 1, slow = 1;
int n = nums.size();
while (fast < n) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};
int main() {
Solution solution;
vector<int> nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
assert(solution.removeDuplicates(nums) == 5);
return 0;
}
21. Merge Two Sorted Lists¶
"""
- Task: Merge the two linked lists into one sorted list.
"""
from typing import Optional
from leetpattern.utils import ListNode
# Linked List
def merge_two_lists(
list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
if list1:
cur.next = list1
elif list2:
cur.next = list2
return dummy.next
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy;
ListNode* cur = &dummy;
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1;
list1 = list1->next;
} else {
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2;
return dummy.next;
}
};
int main() {
Solution sol;
ListNode* list1 = new ListNode(1, new ListNode(2, new ListNode(4)));
ListNode* list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
ListNode* merged = sol.mergeTwoLists(list1, list2);
vector<int> res;
while (merged) {
res.push_back(merged->val);
merged = merged->next;
}
assert(res == std::vector<int>({1, 1, 2, 3, 4, 4}));
return 0;
}
45. Jump Game II¶
"""
- Return the minimum number of jumps to reach the last index.
"""
from typing import List
# Greedy - Interval
def jump(nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 0
reach = 0
left, right = 0, 0
res = 0
while right < n - 1:
for i in range(left, right + 1):
reach = max(reach, i + nums[i])
left = right + 1
right = reach
res += 1
return res
if __name__ == "__main__":
assert jump([2, 3, 1, 1, 4]) == 2
assert jump([2, 3, 0, 1, 4]) == 2
54. Spiral Matrix¶
"""
- Return all elements of the matrix in spiral order.
"""
from typing import List
# Array
def spiralOrder(matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:
return []
res = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for i in range(left, right + 1):
res.append(matrix[top][i])
top += 1
for i in range(top, bottom + 1):
res.append(matrix[i][right])
right -= 1
if top <= bottom:
for i in range(right, left - 1, -1):
res.append(matrix[bottom][i])
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1):
res.append(matrix[i][left])
left += 1
return res
# Math
def spiralOrderMath(matrix: List[List[int]]) -> List[int]:
dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]] # Right Down Left Up
m, n = len(matrix), len(matrix[0])
size = m * n
res = []
i, j, di = 0, -1, 0
while len(res) < size:
dx, dy = dirs[di]
for _ in range(n):
i += dx
j += dy
res.append(matrix[i][j])
di = (di + 1) % 4
n, m = m - 1, n
return res
print(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
# [1, 2, 3, 6, 9, 8, 7, 4, 5]
print(spiralOrderMath([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]))
# [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
34. Find First and Last Position of Element in Sorted Array¶
from bisect import bisect_left
from typing import List
class searchRange:
"""
找 lower bound 和 upper bound
看灵神对这道题的题解，分类讨论区间的写法
target 的 upper bound 是 target + 1 的 lower bound - 1
这样就能统一用 lower bound 的写法
"""
# [left, right]
def bisect_left_closed(self, nums, target):
"""
闭区间写法
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
# [left, right)
def bisect_left_right_open(self, nums, target):
"""
左闭右开区间写法
"""
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left
# (left, right)
def bisect_left_open(self, nums, target):
"""
推荐开区间写法
"""
left, right = -1, len(nums)
while left + 1 < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid
else:
right = mid
return right
def search_range(self, nums: List[int], target: int) -> List[int]:
# edge case
if not nums:
return [-1, -1]
lower = self.bisect_left_closed(nums, target)
upper = self.bisect_left_closed(nums, target + 1) - 1
return [lower, upper] if lower <= upper else [-1, -1]
def search_range_bisect(self, nums: List[int], target: int) -> List[int]:
"""用 python bisect 库函数"""
# edge case
if not nums:
return [-1, -1]
lower = bisect_left(nums, target)
upper = bisect_left(nums, target + 1) - 1
return [lower, upper] if lower <= upper else [-1, -1]
if __name__ == "__main__":
nums = [5, 7, 7, 8, 8, 10]
target = 8
sol = searchRange()
assert sol.search_range(nums, target) == [3, 4]
assert sol.search_range_bisect(nums, target) == [3, 4]
#include <vector>
#include <iostream>
using namespace std;
class Solution
{
int bisect_left(vector<int> &nums, int target)
{
int left = 0, right = (int)nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return left;
}
public:
vector<int> searchRange(vector<int> &nums, int target)
{
int left = bisect_left(nums, target);
if (left == (int)nums.size() || nums[left] != target)
{
return {-1, -1};
}
int right = bisect_left(nums, target + 1) - 1;
return {left, right};
}
};
int main()
{
vector<int> nums = {5, 7, 7, 8, 8, 10};
int target = 8;
Solution s;
vector<int> res = s.searchRange(nums, target);
cout << res[0] << ", " << res[1] << endl;
return 0;
}
62. Unique Paths¶
"""
- Count the number of unique paths to reach the bottom-right corner of a `m x n` grid.
"""
# DP - 2D
def uniquePaths(m: int, n: int) -> int:
if m == 1 or n == 1:
return 1
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]
print(uniquePaths(m=3, n=7)) # 28
# [[1, 1, 1, 1, 1, 1, 1],
# [1, 2, 3, 4, 5, 6, 7],
# [1, 3, 6, 10, 15, 21, 28]]
#include <iostream>
#include <vector>
using namespace std;
int uniquePaths(int m, int n) {
vector dp(m, vector<int>(n, 1));
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
int main() {
int m = 3, n = 7;
cout << uniquePaths(m, n) << endl; // 28
return 0;
}