AmazonVO¶
Table of Contents¶
- 772. Basic Calculator III (Hard) 👑
- 359. Logger Rate Limiter (Easy) 👑
- 146. LRU Cache (Medium)
- 207. Course Schedule (Medium)
- 210. Course Schedule II (Medium)
- 384. Shuffle an Array (Medium)
- 1236. Web Crawler (Medium) 👑
- 673. Number of Longest Increasing Subsequence (Medium)
- 149. Max Points on a Line (Hard)
- 3. Longest Substring Without Repeating Characters (Medium)
- 733. Flood Fill (Easy)
- 205. Isomorphic Strings (Easy)
- 863. All Nodes Distance K in Binary Tree (Medium)
- 107. Binary Tree Level Order Traversal II (Medium)
- 128. Longest Consecutive Sequence (Medium)
- 1041. Robot Bounded In Circle (Medium)
- 895. Maximum Frequency Stack (Hard)
- 36. Valid Sudoku (Medium)
- 37. Sudoku Solver (Hard)
- 380. Insert Delete GetRandom O(1) (Medium)
- 381. Insert Delete GetRandom O(1) - Duplicates allowed (Hard)
- 588. Design In-Memory File System (Hard) 👑
- 642. Design Search Autocomplete System (Hard) 👑
- 297. Serialize and Deserialize Binary Tree (Hard)
- 17. Letter Combinations of a Phone Number (Medium)
- 140. Word Break II (Hard)
- 101. Symmetric Tree (Easy)
- 237. Delete Node in a Linked List (Medium)
- 284. Peeking Iterator (Medium)
- 695. Max Area of Island (Medium)
- 349. Intersection of Two Arrays (Easy)
- 350. Intersection of Two Arrays II (Easy)
- 322. Coin Change (Medium)
- 460. LFU Cache (Hard)
- 973. K Closest Points to Origin (Medium)
- 1296. Divide Array in Sets of K Consecutive Numbers (Medium)
- 62. Unique Paths (Medium)
- 63. Unique Paths II (Medium)
- 980. Unique Paths III (Hard)
- 75. Sort Colors (Medium)
- 79. Word Search (Medium)
- 535. Encode and Decode TinyURL (Medium)
- 64. Minimum Path Sum (Medium)
- 133. Clone Graph (Medium)
- 238. Product of Array Except Self (Medium)
- 268. Missing Number (Easy)
- 136. Single Number (Easy)
- 572. Subtree of Another Tree (Easy)
- 543. Diameter of Binary Tree (Easy)
- 1245. Tree Diameter (Medium) 👑
- 257. Binary Tree Paths (Easy)
- 545. Boundary of Binary Tree (Medium) 👑
- 490. The Maze (Medium) 👑
- 505. The Maze II (Medium) 👑
- 1152. Analyze User Website Visit Pattern (Medium) 👑
772. Basic Calculator III 👑¶
# Stack
def calculate(s: str) -> int:
def helper(index):
stack = []
num = 0
sign = "+"
while index < len(s):
char = s[index]
if char.isdigit():
num = num * 10 + int(char)
if char == "(":
num, index = helper(index + 1)
if char in "+-*/)" or index == len(s) - 1:
if sign == "+":
stack.append(num)
elif sign == "-":
stack.append(-num)
elif sign == "*":
stack.append(stack.pop() * num)
elif sign == "/":
stack.append(int(stack.pop() / num)) # 向零取整
num = 0
sign = char
if char == ")":
break
index += 1
return sum(stack), index
s = s.replace(" ", "")
result, _ = helper(0)
return result
s = "2*(5+5*2)/3+(6/2+8)"
print(calculate(s)) # 21
359. Logger Rate Limiter 👑¶
146. LRU Cache¶
from collections import OrderedDict
class DoublyListNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
"""
Design and implement a data structure for Least Recently Used (LRU) cache.
It should support the following operations: get and put.
"""
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.head = DoublyListNode()
self.tail = DoublyListNode()
self.head.next = self.tail
self.tail.prev = self.head
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def add_to_last(self, node):
self.tail.prev.next = node
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.remove(node)
self.add_to_last(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.val = value
self.remove(node)
self.add_to_last(node)
else:
node = DoublyListNode(key=key, val=value)
self.cache[key] = node
self.add_to_last(node)
if len(self.cache) > self.cap:
lru = self.head.next
del self.cache[lru.key]
self.remove(lru)
class LRUCacheOrderedDict:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.cap = capacity
def get(self, key: int):
if key not in self.cache:
return -1
self.cache.move_to_end(key, last=True)
return self.cache[key]
def put(self, key: int, value: int):
if key in self.cache:
self.cache.move_to_end(key, last=True)
elif len(self.cache) >= self.cap:
self.cache.popitem(last=False)
self.cache[key] = value
def test_lru_cache():
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
assert cache.get(1) == 1
cache.put(3, 3)
assert cache.get(2) == -1
cache.put(4, 4)
assert cache.get(1) == -1
assert cache.get(3) == 3
assert cache.get(4) == 4
updated = LRUCache(2)
updated.put(1, 1)
updated.put(2, 2)
updated.put(1, 10)
updated.put(3, 3)
assert updated.get(1) == 10
assert updated.get(2) == -1
single = LRUCache(1)
single.put(1, 1)
single.put(2, 2)
assert single.get(1) == -1
assert single.get(2) == 2
def test_lru_cache_ordered_dict():
cache = LRUCacheOrderedDict(2)
cache.put(1, 1)
cache.put(2, 2)
assert cache.get(1) == 1
cache.put(3, 3)
assert cache.get(2) == -1
cache.put(4, 4)
assert cache.get(1) == -1
assert cache.get(3) == 3
assert cache.get(4) == 4
#include <cassert>
#include <iostream>
#include <unordered_map>
using namespace std;
class Node {
public:
int key;
int val;
Node *prev;
Node *next;
Node(int k = 0, int v = 0) : key(k), val(v), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
int cap;
unordered_map<int, Node *> cache;
Node *head;
Node *tail;
void remove(Node *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void insert_to_last(Node *node) {
tail->prev->next = node;
node->prev = tail->prev;
tail->prev = node;
node->next = tail;
}
void move_to_last(Node *node) {
remove(node);
insert_to_last(node);
}
public:
LRUCache(int capacity) {
this->cap = capacity;
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.find(key) != cache.end()) {
Node *node = cache[key];
move_to_last(node);
return node->val;
}
return -1;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node *node = cache[key];
node->val = value;
move_to_last(node);
} else {
Node *newNode = new Node(key, value);
cache[key] = newNode;
insert_to_last(newNode);
if ((int)cache.size() > cap) {
Node *removed = head->next;
remove(removed);
cache.erase(removed->key);
delete removed;
}
}
}
};
int main() {
LRUCache lru(2);
lru.put(1, 1);
lru.put(2, 2);
assert(lru.get(1) == 1); // returns 1
lru.put(3, 3); // evicts key 2
assert(lru.get(2) == -1); // returns -1 (not found)
lru.put(4, 4); // evicts key 1
assert(lru.get(1) == -1); // returns -1 (not found)
assert(lru.get(3) == 3); // returns 3
assert(lru.get(4) == 4); // returns 4
return 0;
}
207. Course Schedule¶
from collections import defaultdict, deque
from typing import List
# BFS (Kahn's Algorithm)
def canFinishBFS(numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
indegree = defaultdict(int)
for crs, pre in prerequisites:
graph[pre].append(crs)
indegree[crs] += 1
q = deque([i for i in range(numCourses) if indegree[i] == 0])
count = 0
while q:
crs = q.popleft()
count += 1
for nxt in graph[crs]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return count == numCourses
# DFS + Set
def canFinishDFS1(numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
for crs, pre in prerequisites:
graph[crs].append(pre)
visiting = set()
def dfs(crs):
if crs in visiting: # cycle detected
return False
if graph[crs] == []:
return True
visiting.add(crs)
for pre in graph[crs]:
if not dfs(pre):
return False
visiting.remove(crs)
graph[crs] = []
return True
for crs in range(numCourses):
if not dfs(crs):
return False
return True
# DFS + List
def canFinishDFS2(numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
for pre, crs in prerequisites:
graph[crs].append(pre)
# 0: init, 1: visiting, 2: visited
status = [0] * numCourses
def dfs(crs):
if status[crs] == 1: # cycle detected
return False
if status[crs] == 2:
return True
status[crs] = 1
for pre in graph[crs]:
if not dfs(pre):
return False
status[crs] = 2
return True
for crs in range(numCourses):
if not dfs(crs):
return False
return True
prerequisites = [[0, 1], [0, 2], [1, 3], [1, 4], [3, 4]]
print(canFinishBFS(5, prerequisites)) # True
print(canFinishDFS1(5, prerequisites)) # True
print(canFinishDFS2(5, prerequisites)) # True
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// BFS
bool canFinishBFS(int numCourses, vector<vector<int>> &prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> indegree(numCourses, 0);
for (auto &pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
indegree[pre[0]]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
int cnt = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
cnt++;
for (int nxt : graph[cur]) {
indegree[nxt]--;
if (indegree[nxt] == 0) {
q.push(nxt);
}
}
}
return cnt == numCourses;
}
// DFS
bool canFinishDFS(int numCourses, vector<vector<int>> &prerequisites) {
vector<vector<int>> graph(numCourses);
for (auto &pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
}
// 0: not visited, 1: visiting, 2: visited
vector<int> state(numCourses, 0);
function<bool(int)> dfs = [&](int pre) -> bool {
state[pre] = 1; // visiting
for (int crs : graph[pre]) {
if (state[crs] == 1 || (state[crs] == 0 && dfs(crs))) {
return true;
}
}
state[pre] = 2; // visited
return false;
};
for (int i = 0; i < numCourses; i++) {
if (state[i] == 0 && dfs(i)) {
return false;
}
}
return true;
}
};
int main() {
Solution sol;
vector<vector<int>> prerequisites = {{1, 0}, {2, 1}, {3, 2}, {4, 3},
{5, 4}, {6, 5}, {7, 6}, {8, 7},
{9, 8}, {10, 9}};
int numCourses = 11;
cout << sol.canFinishBFS(numCourses, prerequisites) << endl;
cout << sol.canFinishDFS(numCourses, prerequisites) << endl;
return 0;
}
210. Course Schedule II¶
"""
- Return the ordering of courses you should take to finish all courses. If there are multiple valid answers, return any of them.
"""
from collections import defaultdict, deque
from typing import List
# 1. BFS - Kahn's Algorithm
def findOrderBFS(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
graph = defaultdict(list)
indegree = defaultdict(int)
for crs, pre in prerequisites:
graph[pre].append(crs)
indegree[crs] += 1
q = deque([i for i in range(numCourses) if indegree[i] == 0])
order = []
while q:
pre = q.popleft()
order.append(pre)
for crs in graph[pre]:
indegree[crs] -= 1
if indegree[crs] == 0:
q.append(crs)
return order if len(order) == numCourses else []
# 2. DFS + Set
def findOrderDFS1(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj = defaultdict(list)
for crs, pre in prerequisites:
adj[crs].append(pre)
visit, cycle = set(), set()
order = []
def dfs(crs):
if crs in cycle:
return False
if crs in visit:
return True
cycle.add(crs)
for pre in adj[crs]:
if not dfs(pre):
return False
cycle.remove(crs)
visit.add(crs)
order.append(crs)
return True
for crs in range(numCourses):
if not dfs(crs):
return []
return order
# 3. DFS + List
def findOrderDFS2(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj = defaultdict(list)
for pre, crs in prerequisites:
adj[crs].append(pre)
# 0: not visited, 1: visiting, 2: visited
state = [0] * numCourses
order = []
def dfs(crs):
if state[crs] == 1:
return False
if state[crs] == 2:
return True
state[crs] = 1
for pre in adj[crs]:
if not dfs(pre):
return False
state[crs] = 2
order.append(crs)
return True
for crs in range(numCourses):
if not dfs(crs):
return []
return order[::-1]
numCourses = 5
prerequisites = [[0, 1], [0, 2], [1, 3], [1, 4], [3, 4]]
print(findOrderBFS(numCourses, prerequisites)) # [2, 4, 3, 1, 0]
print(findOrderDFS1(numCourses, prerequisites)) # [4, 3, 1, 2, 0]
print(findOrderDFS2(numCourses, prerequisites)) # [4, 3, 2, 1, 0]
#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// BFS
vector<int> findOrderBFS(int numCourses,
vector<vector<int>> &prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> in_degree(numCourses, 0);
vector<int> res;
for (auto &pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
in_degree[pre[0]]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++)
if (in_degree[i] == 0) q.push(i);
while (!q.empty()) {
int cur = q.front();
q.pop();
res.push_back(cur);
for (int next : graph[cur]) {
in_degree[next]--;
if (in_degree[next] == 0) q.push(next);
}
}
return (int)res.size() == numCourses ? res : vector<int>{};
}
};
int main() {
Solution obj;
vector<vector<int>> prerequisites{{1, 0}, {2, 0}, {3, 1}, {3, 2}};
vector<int> res = obj.findOrderBFS(4, prerequisites);
assert((res == vector<int>{0, 1, 2, 3} || res == vector<int>{0, 2, 1, 3}));
return 0;
}
384. Shuffle an Array¶
1236. Web Crawler 👑¶
673. Number of Longest Increasing Subsequence¶
from typing import List
# DP - LIS
def findNumberOfLIS(nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
dp = [1 for _ in range(n)]
counts = [1 for _ in range(n)]
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
counts[i] = counts[j]
elif dp[j] + 1 == dp[i]:
counts[i] += counts[j]
longest = max(dp)
return sum(c for i, c in enumerate(counts) if dp[i] == longest)
nums = [1, 3, 5, 4, 7]
print(findNumberOfLIS(nums)) # 2
149. Max Points on a Line¶
from collections import defaultdict
from typing import List
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
# edge case
n = len(points)
if n <= 2:
return n
res = 0
for i in range(n - 1):
x1, y1 = points[i]
cnt = defaultdict(int)
for j in range(i + 1, n):
x2, y2 = points[j]
g = "inf" if x1 == x2 else (y2 - y1) / (x2 - x1)
cnt[g] += 1
res = max(res, 1 + max(cnt.values()))
return res
if __name__ == "__main__":
sol = Solution()
points = [[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]
assert sol.maxPoints(points) == 4
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;
}
733. Flood Fill¶
"""
- Replace all the pixels of the same color starting from the given pixel.
- In other words, find the connected component of the starting pixel and change the color of all the pixels in that component.
- Edge cases: If the starting pixel is already the target color, return the image as it is.
- **Flood Fill** is essentially a graph traversal algorithm (like BFS or DFS) applied to matrices (2D grids).
It checks adjacent cells (up, down, left, right) of a starting point to determine whether they belong to the same region.
Typically, it involves modifying or marking the cells that belong to the same connected component.
| 1 | 1 | 1 |
| :-: | :---: | :-: |
| 1 | ==1== | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| :-: | :---: | :-: |
| 1 | ==2== | 0 |
| 1 | 0 | 1 |
| 1 | ==2== | 1 |
| :---: | :---: | :-: |
| ==2== | ==2== | 0 |
| 1 | 0 | 1 |
| ==2== | ==2== | ==2== |
| :---: | :---: | :---: |
| ==2== | ==2== | 0 |
| ==2== | 0 | 1 |
"""
from collections import deque
from typing import List
# DFS
def floodFillDFS(image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
org = image[sr][sc]
m, n = len(image), len(image[0])
if org == color:
return image
def dfs(r, c):
if r < 0 or r >= m or c < 0 or c >= n or image[r][c] != org:
return None
image[r][c] = color
dfs(r - 1, c)
dfs(r + 1, c)
dfs(r, c - 1)
dfs(r, c + 1)
dfs(sr, sc)
return image
# BFS
def floodFillBFS(image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
org = image[sr][sc]
m, n = len(image), len(image[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
if org == color:
return image
q = deque([(sr, sc)])
while q:
r, c = q.popleft()
image[r][c] = color
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and image[nr][nc] == org:
q.append((nr, nc))
return image
image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
sr = 1
sc = 1
print(floodFillDFS(image, sr, sc, 2))
# [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
print(floodFillBFS(image, sr, sc, 2))
# [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
#include <cassert>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
class Solution {
private:
void dfs(vector<vector<int>>& image, int org, int color, int r, int c) {
int m = image.size(), n = image[0].size();
if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] != org) {
return;
}
image[r][c] = color;
dfs(image, org, color, r - 1, c);
dfs(image, org, color, r + 1, c);
dfs(image, org, color, r, c - 1);
dfs(image, org, color, r, c + 1);
}
public:
// DFS
vector<vector<int>> flood_fill_dfs(vector<vector<int>>& image, int sr,
int sc, int color) {
int org = image[sr][sc];
if (org == color) return image;
dfs(image, org, color, sr, sc);
return image;
}
// DFS with lambda
vector<vector<int>> flood_fill_dfs_lambda(vector<vector<int>>& image,
int sr, int sc, int color) {
int org = image[sr][sc];
if (org == color) return image;
int m = image.size(), n = image[0].size();
function<void(int, int)> dfs = [&](int r, int c) -> void {
if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] != org) {
return;
}
image[r][c] = color;
dfs(r - 1, c);
dfs(r + 1, c);
dfs(r, c - 1);
dfs(r, c + 1);
};
dfs(sr, sc);
return image;
}
// BFS
vector<vector<int>> flood_fill_bfs(vector<vector<int>>& image, int sr,
int sc, int color) {
int org = image[sr][sc];
if (org == color) return image;
int m = image.size(), n = image[0].size();
vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
queue<pair<int, int>> q;
q.push({sr, sc});
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
image[r][c] = color;
for (auto& dir : dirs) {
int nr = r + dir.first;
int nc = c + dir.second;
if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
image[nr][nc] == org) {
q.push({nr, nc});
}
}
}
return image;
}
};
int main() {
Solution solution;
vector<vector<int>> image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
solution.flood_fill_dfs(image, 1, 1, 2);
vector<vector<int>> expected = {{2, 2, 2}, {2, 2, 0}, {2, 0, 1}};
assert((image == expected));
image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
solution.flood_fill_dfs_lambda(image, 1, 1, 2);
assert((image == expected));
image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
solution.flood_fill_bfs(image, 1, 1, 2);
assert((image == expected));
return 0;
}
205. Isomorphic Strings¶
#include <cassert>
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
bool isIsomorphic(string s, string t) {
if (s.size() != t.size()) return false;
unordered_map<char, char> map_s2t;
unordered_map<char, char> map_t2s;
for (size_t i = 0; i < s.size(); i++) {
char a = s[i];
char b = t[i];
if (map_s2t.count(a) && map_s2t[a] != b) return false;
if (map_t2s.count(b) && map_t2s[b] != a) return false;
map_s2t[a] = b;
map_t2s[b] = a;
}
return true;
}
};
int main() {
Solution sol;
assert(sol.isIsomorphic("egg", "add") == true);
return 0;
}
863. All Nodes Distance K in Binary Tree¶
from collections import deque
from typing import List
from binarytree import Node as TreeNode
from binarytree import build
# BFS
def distanceK(root: TreeNode, target: TreeNode, k: int) -> List[int]:
parent = dict()
def dfs(node, par=None):
if node:
parent[node] = par
dfs(node.left, node)
dfs(node.right, node)
dfs(root)
q = deque([(target, 0)])
seen = set([target])
while q:
node, dist = q.popleft()
if dist == k:
return [node.val] + [node.val for node, _ in q]
for nei in (node.left, node.right, parent[node]):
if nei and nei not in seen:
seen.add(nei)
q.append((nei, dist + 1))
return []
root = build([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
print(root)
# ______3__
# / \
# 5__ 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
target = root.left
k = 2
print(distanceK(root, target, k)) # [7, 4, 1]
107. Binary Tree Level Order Traversal II¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
def levelOrderBottom(root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
res = []
q = deque([root])
while q:
level = []
n = len(q)
for _ in range(n):
cur = q.popleft()
level.append(cur.val)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
res.append(level)
return res[::-1]
tree = build([3, 9, 20, None, None, 15, 7])
print(tree)
# 3___
# / \
# 9 _20
# / \
# 15 7
print(levelOrderBottom(tree)) # [[15, 7], [9, 20], [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
1041. Robot Bounded In Circle¶
895. Maximum Frequency Stack¶
36. Valid Sudoku¶
from typing import List
# Set
def isValidSudoku(board: List[List[str]]) -> bool:
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for i in range(9):
for j in range(9):
if board[i][j] == ".":
continue
if board[i][j] in rows[i]:
return False
rows[i].add(board[i][j])
if board[i][j] in cols[j]:
return False
cols[j].add(board[i][j])
box_index = (i // 3) * 3 + j // 3
if board[i][j] in boxes[box_index]:
return False
boxes[box_index].add(board[i][j])
return True
board = [
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"],
]
print(isValidSudoku(board)) # True
37. Sudoku Solver¶
"""
- [Sudoku Solver](https://leetcode.com/problems/sudoku-solver/)
- [解数独](https://leetcode.cn/problems/sudoku-solver/)
- Hard
"""
from pprint import pprint
from typing import List
# Backtracking - Board
def solveSudoku(board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def backtracking(board: List[List[str]]) -> bool:
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] != ".":
continue
for k in range(1, 10):
if is_valid(i, j, k, board):
board[i][j] = str(k)
if backtracking(board):
return True
board[i][j] = "."
return False
return True
def is_valid(row: int, col: int, val: int, board: List[List[str]]) -> bool:
for i in range(9):
if board[row][i] == str(val):
return False
for j in range(9):
if board[j][col] == str(val):
return False
start_row = (row // 3) * 3
start_col = (col // 3) * 3
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == str(val):
return False
return True
backtracking(board)
board = [
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"],
]
solveSudoku(board)
pprint(board)
# [['5', '3', '4', '6', '7', '8', '9', '1', '2'],
# ['6', '7', '2', '1', '9', '5', '3', '4', '8'],
# ['1', '9', '8', '3', '4', '2', '5', '6', '7'],
# ['8', '5', '9', '7', '6', '1', '4', '2', '3'],
# ['4', '2', '6', '8', '5', '3', '7', '9', '1'],
# ['7', '1', '3', '9', '2', '4', '8', '5', '6'],
# ['9', '6', '1', '5', '3', '7', '2', '8', '4'],
# ['2', '8', '7', '4', '1', '9', '6', '3', '5'],
# ['3', '4', '5', '2', '8', '6', '1', '7', '9']]
380. Insert Delete GetRandom O(1)¶
import random
class RandomizedSet:
def __init__(self):
self.nums = []
self.pos = {} # num: idx
def insert(self, val: int) -> bool:
if val in self.pos:
return False
self.pos[val] = len(self.nums)
self.nums.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.pos:
return False
idx = self.pos[val]
last_val = self.nums[-1]
self.nums[idx] = last_val
self.pos[last_val] = idx
self.nums.pop()
del self.pos[val]
return True
def getRandom(self) -> int:
return random.choice(self.nums)
def test_RandomizedSet():
obj = RandomizedSet()
assert obj.insert(1)
assert not obj.remove(2)
assert obj.insert(2)
assert obj.getRandom() in [1, 2]
assert obj.remove(1)
assert not obj.insert(2)
assert obj.getRandom() == 2
381. Insert Delete GetRandom O(1) - Duplicates allowed¶
588. Design In-Memory File System 👑¶
from collections import defaultdict
class TrieNode:
def __init__(self):
self.children = defaultdict(TrieNode)
self.content = ""
# Trie
class FileSystem:
def __init__(self):
self.root = TrieNode()
def ls(self, path: str) -> list:
cur = self.root
if path != "/":
paths = path.split("/")[1:]
for p in paths:
cur = cur.children[p]
if cur.content:
return [path.split("/")[-1]]
return sorted(cur.children.keys())
def mkdir(self, path: str) -> None:
cur = self.root
paths = path.split("/")[1:]
for p in paths:
cur = cur.children[p]
def addContentToFile(self, filePath: str, content: str) -> None:
cur = self.root
paths = filePath.split("/")[1:]
for p in paths:
cur = cur.children[p]
cur.content += content
def readContentFromFile(self, filePath: str) -> str:
cur = self.root
paths = filePath.split("/")[1:]
for p in paths:
cur = cur.children[p]
return cur.content
obj = FileSystem()
obj.mkdir("/a/b/c")
obj.addContentToFile("/a/b/c/d", "hello")
print(obj.ls("/")) # ["a"]
print(obj.readContentFromFile("/a/b/c/d")) # "hello"
642. Design Search Autocomplete System 👑¶
-
Tags: String, Depth First Search, Design, Trie, Sorting, Heap Priority Queue, Data Stream
297. Serialize and Deserialize Binary Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# BFS
class BFS:
def serialize(self, root: Optional[TreeNode]) -> str:
if not root:
return ""
res = []
q = deque([root])
while q:
node = q.popleft()
if node:
res.append(str(node.val))
q.append(node.left)
q.append(node.right)
else:
res.append("null")
return ",".join(res)
def deserialize(self, data: str) -> Optional[TreeNode]:
if not data:
return None
nodes = data.split(",")
root = TreeNode(int(nodes[0]))
q = deque([root])
index = 1
while q:
node = q.popleft()
if nodes[index] != "null":
node.left = TreeNode(int(nodes[index]))
q.append(node.left)
index += 1
if nodes[index] != "null":
node.right = TreeNode(int(nodes[index]))
q.append(node.right)
index += 1
return root
# DFS
class DFS:
def serialize(self, root: Optional[TreeNode]) -> str:
def dfs(node):
if not node:
return ["null"]
return [str(node.val)] + dfs(node.left) + dfs(node.right)
return ",".join(dfs(root))
def deserialize(self, data: str) -> Optional[TreeNode]:
nodes = data.split(",")
self.index = 0
def dfs():
if nodes[self.index] == "null":
self.index += 1
return None
node = TreeNode(int(nodes[self.index]))
self.index += 1
node.left = dfs()
node.right = dfs()
return node
root = dfs()
return root
root = build([1, 2, 3, None, None, 4, 5])
print(root)
# 1__
# / \
# 2 3
# / \
# 4 5
bfs = BFS()
data1 = bfs.serialize(root)
print(data1) # "1,2,3,null,null,4,5,null,null,null,null"
root1 = bfs.deserialize(data1)
print(root1)
# 1__
# / \
# 2 3
# / \
# 4 5
dfs = DFS()
data2 = dfs.serialize(root)
print(data2) # "1,2,null,null,3,4,null,null,5,null,null"
root2 = dfs.deserialize(data2)
print(root2)
# 1__
# / \
# 2 3
# / \
# 4 5
17. Letter Combinations of a Phone Number¶
"""
- Return all possible letter combinations that the number could represent.
"""
from typing import List
# Backtracking
def letterCombinations(digits: str) -> List[str]:
letter_map = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
n = len(digits)
if n == 0:
return []
res = []
def dfs(idx, path):
if idx == n:
res.append(path)
return None
letters = letter_map[digits[idx]]
for i in range(len(letters)):
dfs(idx + 1, path + letters[i])
dfs(0, "")
return res
if __name__ == "__main__":
assert letterCombinations("23") == [
"ad",
"ae",
"af",
"bd",
"be",
"bf",
"cd",
"ce",
"cf",
]
140. Word Break II¶
101. Symmetric Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def is_symmetric_recursive(root: Optional[TreeNode]) -> bool:
if not root:
return True
def check(left, right):
if left is right:
return True
if not left or not right or left.val != right.val:
return False
outside = check(left.left, right.right)
inside = check(left.right, right.left)
return outside and inside
return check(root.left, root.right)
# Iterative
def is_symmetric_iterative(root: Optional[TreeNode]) -> bool:
if not root:
return True
q = deque()
q.append(root.left)
q.append(root.right)
while q:
left = q.popleft()
right = q.popleft()
if not left and not right:
continue
if not left or not right or left.val != right.val:
return False
q.append(left.left)
q.append(right.right)
q.append(left.right)
q.append(right.left)
return True
if __name__ == "__main__":
root = [1, 2, 2, 3, 4, 4, 3]
root = build(root)
print(root)
# __1__
# / \
# 2 2
# / \ / \
# 3 4 4 3
assert is_symmetric_recursive(root) is True
assert is_symmetric_iterative(root) is True
#include <iostream>
#include "include/trees.hpp"
class Solution {
private:
bool dfs(TreeNode *Left, TreeNode *Right) {
if (Left == nullptr && Right == nullptr) return true;
if (Left == nullptr || Right == nullptr || Left->val != Right->val)
return false;
return dfs(Left->left, Right->right) && dfs(Left->right, Right->left);
}
public:
bool isSymmetric(TreeNode *root) {
return root == nullptr || dfs(root->left, root->right);
}
};
int main() {
Solution solution;
// Test with a symmetric tree
std::vector<int> values = {1, 2, 2, 3, 4, 4, 3};
TreeNode *root = TreeUtils::buildTree(values);
bool result = solution.isSymmetric(root);
std::cout << "Is symmetric: " << (result ? "true" : "false") << std::endl;
return 0;
}
237. Delete Node in a Linked List¶
"""
- Delete a node in a singly linked list. You are given only the node to be deleted.
"""
from leetpattern.utils import LinkedList, ListNode
def deleteNode(node: ListNode) -> None:
node.val = node.next.val
node.next = node.next.next
def test_deleteNode():
# Test case 1: Delete middle node
ll = LinkedList([4, 5, 1, 9])
assert ll.to_array() == [4, 5, 1, 9]
node = ll.head.next # node with value 5
deleteNode(node)
assert ll.to_array() == [4, 1, 9]
# Test case 2: Delete another middle node
ll2 = LinkedList([4, 5, 1, 9])
node2 = ll2.head.next.next # node with value 1
deleteNode(node2)
assert ll2.to_array() == [4, 5, 9]
284. Peeking Iterator¶
695. Max Area of Island¶
from collections import deque
from typing import List
# DFS
def maxAreaOfIslandDFS(grid: List[List[int]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0:
return 0
grid[r][c] = 0
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
res = max(res, dfs(i, j))
return res
# BFS
def maxAreaOfIslandBFS1(grid: List[List[int]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = set()
res = 0
def bfs(r, c):
q = deque([(r, c)])
area = 0
while q:
row, col = q.popleft()
area += 1
for dr, dc in dirs:
nr, nc = row + dr, col + dc
if (
nr < 0
or nr >= m
or nc < 0
or nc >= n
or grid[nr][nc] == 0
or (nr, nc) in visited
):
continue
visited.add((nr, nc))
q.append((nr, nc))
return area
for r in range(m):
for c in range(n):
if grid[r][c] == 1 and (r, c) not in visited:
visited.add((r, c))
res = max(res, bfs(r, c))
return res
# BFS + Grid
def numIslandsBFS2(grid: List[List[str]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
res = 0
def bfs(r, c):
q = deque([(r, c)])
area = 0
while q:
row, col = q.popleft()
area += 1
for dr, dc in dirs:
nr, nc = row + dr, col + dc
if nr < 0 or nr >= m or nc < 0 or nc >= n or grid[nr][nc] == 0:
continue
q.append((nr, nc))
grid[nr][nc] = 0
return area
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
grid[r][c] = 0
res = max(res, bfs(r, c))
return res
grid = [
[0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
]
print(maxAreaOfIslandDFS(grid)) # 6
print(maxAreaOfIslandBFS1(grid)) # 6
print(numIslandsBFS2(grid)) # 6
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int max_area_of_island(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int res = 0;
auto dfs = [&](this auto&& dfs, int r, int c) -> int {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1) {
return 0;
}
grid[r][c] = 0;
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) +
dfs(r, c - 1);
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int area = dfs(i, j);
res = max(res, area);
}
}
}
return res;
}
};
int main() {
Solution solution;
vector<vector<int>> grid = {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
{0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
{0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
assert(solution.max_area_of_island(grid) == 6);
return 0;
}
349. Intersection of Two Arrays¶
from typing import List
# Set
def intersectionSet(nums1: List[int], nums2: List[int]) -> List[int]:
set1 = set(nums1)
set2 = set(nums2)
return list(set1 & set2)
# Hash
def intersectionHash(nums1: List[int], nums2: List[int]) -> List[int]:
set1 = set(nums1)
result = set()
for num in nums2:
if num in set1:
result.add(num)
return list(result)
# |------------|------- |---------|
# | Approach | Time | Space |
# |------------|--------|---------|
# | Set | O(n+m) | O(n+m) |
# | Hash | O(n+m) | O(n) |
# |------------|--------|---------|
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersectionSet(nums1, nums2)) # [2]
print(intersectionHash(nums1, nums2)) # [2]
350. Intersection of Two Arrays II¶
"""
- Return the intersection of two arrays.
"""
from collections import defaultdict
from typing import List
# Hashmap
def intersect(nums1: List[int], nums2: List[int]) -> List[int]:
hashmap = defaultdict(int) # {num: count}
result = []
for i in nums1:
hashmap[i] += 1
for i in nums2:
if hashmap[i] > 0:
result.append(i)
hashmap[i] -= 1
return result
# |-------------|-------------|--------------|
# | Approach | Time | Space |
# |-------------|-------------|--------------|
# | Hashmap | O(n + m) | O(min(n, m)) |
# |-------------|-------------|--------------|
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersect(nums1, nums2)) # [2, 2]
322. Coin Change¶
from typing import List
def coinChange(coins: List[int], amount: int) -> int:
dp = [float("inf") for _ in range(amount + 1)]
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if i - c >= 0:
dp[i] = min(dp[i], 1 + dp[i - c])
return dp[amount] if dp[amount] != float("inf") else -1
coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount)) # 3
460. LFU Cache¶
from collections import OrderedDict, defaultdict
class LFUCache:
def __init__(self, capacity: int):
self.cap = capacity
# key -> [val, freq]
self.key_to_val_freq = {}
# freq -> OrderedDict of keys
self.freq_to_keys = defaultdict(OrderedDict)
self.min_freq = 0
def remove_least_frequent(self):
lfu_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
del self.key_to_val_freq[lfu_key]
# If the frequency list is empty after removal, delete it
if not self.freq_to_keys[self.min_freq]:
del self.freq_to_keys[self.min_freq]
def update_freq(self, key):
"""Updates the frequency of an existing key."""
value, freq = self.key_to_val_freq[key]
# Remove key from current frequency group
del self.freq_to_keys[freq][key]
if not self.freq_to_keys[freq]:
del self.freq_to_keys[freq]
if self.min_freq == freq:
self.min_freq += 1
# Update key frequency
new_freq = freq + 1
self.key_to_val_freq[key] = [value, new_freq]
self.freq_to_keys[new_freq][key] = None
def add_new_key(self, key, value):
if len(self.key_to_val_freq) >= self.cap:
self.remove_least_frequent()
# Insert the new key with frequency 1
self.key_to_val_freq[key] = [value, 1]
self.freq_to_keys[1][key] = None
self.min_freq = 1
def get(self, key: int) -> int:
if key not in self.key_to_val_freq:
return -1
self.update_freq(key)
return self.key_to_val_freq[key][0]
def put(self, key: int, value: int) -> None:
if self.cap == 0:
return
if key in self.key_to_val_freq:
self.key_to_val_freq[key][0] = value
self.update_freq(key)
else:
self.add_new_key(key, value)
lfu = LFUCache(2)
lfu.put(1, 1)
lfu.put(2, 2)
print(lfu.get(1)) # 1
lfu.put(3, 3)
print(lfu.get(2)) # -1
print(lfu.get(3)) # 3
lfu.put(4, 4)
print(lfu.get(1)) # -1
print(lfu.get(3)) # 3
973. K Closest Points to Origin¶
-
Tags: Array, Math, Divide And Conquer, Geometry, Sorting, Heap Priority Queue, Quickselect
import heapq
from typing import List
def kClosest(points: List[List[int]], k: int) -> List[List[int]]:
heap = []
for x, y in points:
dist = -(x**2 + y**2) # max heap
if len(heap) < k:
heapq.heappush(heap, (dist, x, y))
else:
heapq.heappushpop(heap, (dist, x, y)) # push and pop the smallest
return [[x, y] for (_, x, y) in heap]
# Time complexity: O(n * log(k))
# - O(log(k)) for heapify
# - O(n) for iterating through the input list
# Space complexity: O(k)
points = [[1, 3], [-2, 2]]
k = 1
print(kClosest(points, k)) # [[-2, 2]]
1296. Divide Array in Sets of K Consecutive Numbers¶
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;
}
63. Unique Paths II¶
from functools import cache
from typing import List
class UniquePathsWithObstacles:
def memoization(self, obstacleGrid: List[List[int]]) -> int:
"""
Approach: DFS with Memoization
Time complexity: O(mn).
Space complexity: O(mn).
"""
@cache
def dfs(i: int, j: int) -> int:
if i < 0 or j < 0 or obstacleGrid[i][j]:
return 0
if i == 0 and j == 0:
return 1
return dfs(i - 1, j) + dfs(i, j - 1)
m, n = len(obstacleGrid), len(obstacleGrid[0])
return dfs(m - 1, n - 1)
def dp_2d(self, obstacleGrid: List[List[int]]) -> int:
"""
Approach: 2D Dynamic Programming
Time complexity: O(mn).
Space complexity: O(mn).
"""
# edge cases
if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
# init dp
dp = [[0] * n for _ in range(m)]
for i in range(m):
if obstacleGrid[i][0] == 0:
dp[i][0] = 1
else:
break
for j in range(n):
if obstacleGrid[0][j] == 0:
dp[0][j] = 1
else:
break
# update dp
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
continue
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]
def dp_1d(self, obstacleGrid: List[List[int]]) -> int:
"""
Approach: 1D Dynamic Programming
Time complexity: O(mn).
Space complexity: O(n).
"""
n = len(obstacleGrid[0])
dp = [0] * (n + 1)
dp[1] = 1
for row in obstacleGrid:
for j, x in enumerate(row):
if x == 0:
dp[j + 1] += dp[j]
else:
dp[j + 1] = 0
return dp[n]
if __name__ == "__main__":
solution = UniquePathsWithObstacles()
obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
assert solution.dp_2d(obstacleGrid) == 2
assert solution.memoization(obstacleGrid) == 2
assert solution.dp_1d(obstacleGrid) == 2
980. Unique Paths III¶
75. Sort Colors¶
from copy import deepcopy
from typing import List
# Left Right Pointers
def sort_colors_lr_pointers(nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
left = 0
for right in range(n):
if nums[right] == 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
for right in range(left, n):
if nums[right] == 1:
nums[left], nums[right] = nums[right], nums[left]
left += 1
# Three Pointers
def sort_colors_three_pointers(nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
left, right = 0, len(nums) - 1
cur = 0
while cur <= right:
if nums[cur] == 0:
nums[left], nums[cur] = nums[cur], nums[left]
left += 1
cur += 1
elif nums[cur] == 2:
nums[right], nums[cur] = nums[cur], nums[right]
right -= 1
else:
cur += 1
nums = [2, 0, 2, 1, 1, 0]
nums1, nums2 = deepcopy(nums), deepcopy(nums)
sort_colors_lr_pointers(nums1)
print(nums1) # [0, 0, 1, 1, 2, 2]
sort_colors_three_pointers(nums2)
print(nums2) # [0, 0, 1, 1, 2, 2]
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
535. Encode and Decode TinyURL¶
64. Minimum Path Sum¶
from functools import cache
from typing import List
# Iterative
def minPathSum(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
# init
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = grid[i][0] + dp[i - 1][0]
for j in range(1, n):
dp[0][j] = grid[0][j] + dp[0][j - 1]
# update
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]
# Recursive
def minPathSumDFS(grid: List[List[int]]) -> int:
INF = 10**18
@cache
def dfs(i, j):
if i < 0 or j < 0:
return INF
if i == 0 and j == 0:
return grid[i][j]
return min(dfs(i, j - 1), dfs(i - 1, j)) + grid[i][j]
return dfs(len(grid) - 1, len(grid[0]) - 1)
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
print(minPathSum(grid)) # 7
print(minPathSumDFS(grid)) # 7
133. Clone Graph¶
from collections import deque
from typing import Optional
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
class CloneGraph:
def dfs(self, node: Optional["Node"]) -> Optional["Node"]:
hashmap = {}
def dfs(node):
if node in hashmap:
return hashmap[node]
res = Node(node.val)
hashmap[node] = res
for nei in node.neighbors:
res.neighbors.append(dfs(nei))
return res
return dfs(node) if node else None
def bfs(self, node: Optional["Node"]) -> Optional["Node"]:
if not node:
return None
hashmap = {node: Node(node.val)}
q = deque([node])
while q:
cur = q.popleft()
for nei in cur.neighbors:
if nei not in hashmap:
hashmap[nei] = Node(nei.val)
q.append(nei)
hashmap[cur].neighbors.append(hashmap[nei])
return hashmap[node]
238. Product of Array Except Self¶
"""
- Classic **Prefix Sum** problem
- Return an array `output` such that `output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.
| Approach | Time | Space |
| ------------------ | ---- | ----- |
| Prefix | O(n) | O(n) |
| Prefix (Optimized) | O(n) | O(1) |
"""
from typing import List
# Prefix
def productExceptSelf(nums: List[int]) -> List[int]:
n = len(nums)
prefix = [1 for _ in range(n)]
suffix = [1 for _ in range(n)]
for i in range(1, n):
prefix[i] = nums[i - 1] * prefix[i - 1]
for i in range(n - 2, -1, -1):
suffix[i] = nums[i + 1] * suffix[i + 1]
result = [i * j for i, j in zip(prefix, suffix)]
return result
# Prefix (Optimized)
def productExceptSelfOptimized(nums: List[int]) -> List[int]:
n = len(nums)
result = [1 for _ in range(n)]
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
print(productExceptSelf([1, 2, 3, 4]))
# [24, 12, 8, 6]
print(productExceptSelfOptimized([1, 2, 3, 4]))
# [24, 12, 8, 6]
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> productExceptSelf(vector<int> &nums) {
int n = nums.size();
vector<int> prefix(n, 1);
vector<int> suffix(n, 1);
vector<int> res(n, 1);
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] * nums[i - 1];
}
for (int i = n - 2; i >= 0; i--) {
suffix[i] = suffix[i + 1] * nums[i + 1];
}
for (int i = 0; i < n; i++) {
res[i] = prefix[i] * suffix[i];
}
return res;
}
};
int main() {
vector<int> nums = {1, 2, 3, 4};
Solution obj;
vector<int> result = obj.productExceptSelf(nums);
assert(result == vector<int>({24, 12, 8, 6}));
return 0;
}
268. Missing Number¶
from typing import List
# Math
def missingNumberMath(nums: List[int]) -> int:
n = len(nums)
return (n * (n + 1)) // 2 - sum(nums)
# Bit Manipulation (XOR)
def missingNumberXOR(nums: List[int]) -> int:
n = len(nums)
for i, num in enumerate(nums):
n ^= i ^ num
return n
nums = [3, 0, 1]
print(missingNumberMath(nums)) # 2
print(missingNumberXOR(nums)) # 2
136. Single Number¶
from functools import reduce
from operator import xor
from typing import List
# XOR
def singleNumber(nums: List[int]) -> int:
res = 0
for num in nums:
res ^= num
return res
# XOR
def singleNumberXOR(nums: List[int]) -> int:
return reduce(xor, nums)
# XOR
def singleNumberXORLambda(nums: List[int]) -> int:
return reduce(lambda x, y: x ^ y, nums)
nums = [4, 1, 2, 1, 2]
print(singleNumber(nums)) # 4
print(singleNumberXOR(nums)) # 4
print(singleNumberXORLambda(nums)) # 4
572. Subtree of Another Tree¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# DFS - Tree
def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
if not root:
return False
return (
isSameTree(root, subRoot)
or isSubtree(root.left, subRoot)
or isSubtree(root.right, subRoot)
)
# |------------|---------|----------|
# | Approach | Time | Space |
# |------------|---------|----------|
# | DFS | O(n * m)| O(n) |
# |------------|---------|----------|
root = build([3, 4, 5, 1, 2, None, None, None, None, 0])
subRoot = build([4, 1, 2])
print(root)
# ____3
# / \
# 4__ 5
# / \
# 1 2
# /
# 0
print(subRoot)
# 4
# / \
# 1 2
print(isSubtree(root, subRoot)) # False
543. Diameter of Binary Tree¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Tree DFS
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.diameter = 0
def dfs(node):
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
self.diameter = max(self.diameter, left + right)
return 1 + max(left, right)
dfs(root)
return self.diameter
root = build([1, 2, 3, 4, 5])
print(root)
# __1
# / \
# 2 3
# / \
# 4 5
obj = Solution()
print(obj.diameterOfBinaryTree(root)) # 3
#include <algorithm>
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right)
: val(x), left(left), right(right) {}
};
int diameterOfBinaryTree(TreeNode* root) {
int diameter = 0;
auto dfs = [&](auto&& self, TreeNode* node) -> int {
if (!node) return 0;
int left = self(self, node->left);
int right = self(self, node->right);
diameter = max(diameter, left + right);
return 1 + max(left, right);
};
dfs(dfs, root);
return diameter;
}
int main() {
// [1, 2, 3, 4, 5]
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
cout << diameterOfBinaryTree(root) << endl; // 3
return 0;
}
1245. Tree Diameter 👑¶
from collections import defaultdict, deque
from typing import List
# Tree Diameter
def treeDiameter(edges: List[List[int]]) -> int:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = {0}
q = deque([0])
cur = 0
while q:
size = len(q)
for _ in range(size):
cur = q.popleft()
for nxt in graph[cur]:
if nxt not in visited:
q.append(nxt)
visited.add(nxt)
visited = {cur}
q = deque([cur])
res = -1
while q:
size = len(q)
for _ in range(size):
cur = q.popleft()
for nxt in graph[cur]:
if nxt not in visited:
q.append(nxt)
visited.add(nxt)
res += 1
return res
edges = [[0, 1], [1, 2], [2, 3], [1, 4], [4, 5]]
assert treeDiameter(edges) == 4
257. Binary Tree Paths¶
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def binaryTreePaths(root: Optional[TreeNode]) -> List[str]:
res = []
def dfs(node, path):
if not node:
return
path += str(node.val)
if not node.left and not node.right:
res.append(path)
return
path += "->"
dfs(node.left, path)
dfs(node.right, path)
dfs(root, "")
return res
root = build([1, 2, 3, None, 5])
print(root)
# __1
# / \
# 2 3
# \
# 5
print(binaryTreePaths(root)) # ['1->2->5', '1->3']
545. Boundary of Binary Tree 👑¶
490. The Maze 👑¶
from collections import deque
from typing import List
# BFS
def hasPathBFS(maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m, n = len(maze), len(maze[0])
dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
q = deque([start])
maze[start[0]][start[1]] = -1
while q:
r, c = q.popleft()
if [r, c] == destination:
return True
for dr, dc in dirs:
nr, nc = r, c
while 0 <= nr + dr < m and 0 <= nc + dc < n and maze[nr + dr][nc + dc] != 1:
nr += dr
nc += dc
if maze[nr][nc] != -1:
q.append([nr, nc])
maze[nr][nc] = -1
return False
maze = [
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 1],
[0, 0, 0, 0, 0],
]
start = [0, 4]
destination = [4, 4]
print(hasPathBFS(maze, start, destination)) # True
505. The Maze II 👑¶
-
Tags: Array, Depth First Search, Breadth First Search, Graph, Heap Priority Queue, Matrix, Shortest Path
import heapq
from typing import List
# Dijkstra
def shortestDistance(
maze: List[List[int]], start: List[int], destination: List[int]
) -> int:
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
m, n = len(maze), len(maze[0])
dist = [[float("inf")] * n for _ in range(m)]
dist[start[0]][start[1]] = 0
heap = [(0, start[0], start[1])]
while heap:
d, r, c = heapq.heappop(heap)
if [r, c] == destination:
return d
for dr, dc in directions:
nr, nc, nd = r, c, d
while 0 <= nr + dr < m and 0 <= nc + dc < n and maze[nr + dr][nc + dc] == 0:
nr += dr
nc += dc
nd += 1
if nd < dist[nr][nc]:
dist[nr][nc] = nd
heapq.heappush(heap, (nd, nr, nc))
return -1
maze = [
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 1],
[0, 0, 0, 0, 0],
]
start = [0, 4]
destination = [4, 4]
print(shortestDistance(maze, start, destination)) # 12