Meta¶
Table of Contents¶
- 215. Kth Largest Element in an Array (Medium)
- 162. Find Peak Element (Medium)
- 199. Binary Tree Right Side View (Medium)
- 88. Merge Sorted Array (Easy)
- 1. Two Sum (Easy)
- 50. Pow(x, n) (Medium)
- 125. Valid Palindrome (Easy)
- 71. Simplify Path (Medium)
- 56. Merge Intervals (Medium)
- 129. Sum Root to Leaf Numbers (Medium)
- 138. Copy List with Random Pointer (Medium)
- 146. LRU Cache (Medium)
- 121. Best Time to Buy and Sell Stock (Easy)
- 23. Merge k Sorted Lists (Hard)
- 31. Next Permutation (Medium)
- 34. Find First and Last Position of Element in Sorted Array (Medium)
- 76. Minimum Window Substring (Hard)
- 133. Clone Graph (Medium)
- 65. Valid Number (Hard)
- 20. Valid Parentheses (Easy)
- 19. Remove Nth Node From End of List (Medium)
- 14. Longest Common Prefix (Easy)
- 207. Course Schedule (Medium)
- 2. Add Two Numbers (Medium)
- 3. Longest Substring Without Repeating Characters (Medium)
- 173. Binary Search Tree Iterator (Medium)
- 26. Remove Duplicates from Sorted Array (Easy)
- 4. Median of Two Sorted Arrays (Hard)
- 15. 3Sum (Medium)
- 9. Palindrome Number (Easy)
215. Kth Largest Element in an Array¶
162. Find Peak Element¶
199. Binary Tree Right Side View¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
# Binary Tree BFS
def rightSideViewBFS(root: Optional[TreeNode]) -> List[int]:
if not root:
return []
q = deque([root])
res = []
while q:
n = len(q)
for i in range(n):
node = q.popleft()
if i == n - 1:
res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
# Binary Tree DFS
def rightSideViewDFS(root: Optional[TreeNode]) -> List[int]:
"""后序遍历，先右后左，遇到的第一个节点就是该深度的最右侧节点"""
ans = []
def dfs(node, depth):
if node is None:
return
if depth == len(ans): # 这个深度首次遇到
ans.append(node.val)
dfs(node.right, depth + 1)
dfs(node.left, depth + 1)
dfs(root, 0)
return ans
if __name__ == "__main__":
root = [1, 2, 2, 3, 4, None, 3, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \ \
# 3 4 3
# /
# 5
assert rightSideViewBFS(root) == [1, 2, 3, 5]
assert rightSideViewDFS(root) == [1, 2, 3, 5]
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;
}
1. Two Sum¶
"""
- Return the indices of the two numbers such that they add up to a specific target.
- Approach: Use a hashmap to store the indices of the numbers.
- Time Complexity: O(n)
- Space Complexity: O(n)
"""
from typing import List
def two_sum(nums: List[int], target: int) -> List[int]:
hashmap = {} # val: idx
for idx, val in enumerate(nums):
if (target - val) in hashmap:
return [hashmap[target - val], idx]
hashmap[val] = idx
return []
def test_two_sum():
assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([3, 2, 4], 6) == [1, 2]
assert two_sum([3, 3], 6) == [0, 1]
assert two_sum([1, 2, 3, 4, 5], 10) == []
assert two_sum([-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;
}
50. Pow(x, n)¶
# Iterative
def myPowIterative(x: float, n: int) -> float:
if n == 0:
return 1
if n < 0:
x = 1 / x
n = -n
result = 1
cur = x
while n > 0:
if n % 2 == 1:
result *= cur
cur *= cur
n //= 2
return result
# Recursive
def myPowRecursive(x: float, n: int) -> float:
if n == 0:
return 1
if n < 0:
x = 1 / x
n = -n
if n % 2 == 0:
return myPowRecursive(x * x, n // 2)
else:
return x * myPowRecursive(x * x, n // 2)
x = 2.00000
n = 10
print(myPowIterative(x, n)) # 1024.0
print(myPowRecursive(x, n)) # 1024.0
125. Valid Palindrome¶
# List Comprehension
def isPalindrome(s: str) -> bool:
s = [char.lower() for char in s if char.isalnum()]
return s == s[::-1]
# Left Right Pointers
def isPalindromeLR(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
s = "A man, a plan, a canal: Panama"
print(isPalindrome(s)) # True
print(isPalindromeLR(s)) # True
71. Simplify Path¶
def simplify_path_stack(path: str) -> str:
if not path:
return "/"
stack = []
for p in path.split("/"):
if p == "" or p == ".":
continue
if p != "..":
stack.append(p)
elif stack:
stack.pop()
return "/" + "/".join(stack)
def test_simplify_path_stack():
assert simplify_path_stack("/home/") == "/home"
assert simplify_path_stack("/../") == "/"
assert simplify_path_stack("/home//foo/") == "/home/foo"
assert simplify_path_stack("/a/./b/../../c/") == "/c"
56. Merge Intervals¶
"""
- Merge all overlapping intervals.
<iframe width="560" height="315" src="https://www.youtube.com/embed/44H3cEC2fFM?si=J-Jr_Fg2eDse3-de" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
"""
from typing import List
# Intervals
def merge(intervals: List[List[int]]) -> List[List[int]]:
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;
}
129. Sum Root to Leaf Numbers¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
class sumNumbers:
def dfs(self, root: Optional[TreeNode]) -> int:
self.res = 0
def dfs(node, cur):
if not node:
return
cur = cur * 10 + node.val
if not node.left and not node.right:
self.res += cur
return
dfs(node.left, cur)
dfs(node.right, cur)
dfs(root, 0)
return self.res
if __name__ == "__main__":
root = [1, 2, 3]
root = build(root)
print(root)
# 1
# / \
# 2 3
assert sumNumbers().dfs(root) == 25
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
146. LRU Cache¶
"""
- Design and implement a data structure for **Least Recently Used (LRU) cache**. It should support the following operations: get and put.
- [lru](https://media.geeksforgeeks.org/wp-content/uploads/20240909142802/Working-of-LRU-Cache-copy-2.webp)
- 
| Data structure | Description |
| ------------------ | ----------------------------- |
| Doubly Linked List | To store the key-value pairs. |
| Hash Map | To store the key-node pairs. |
"""
from collections import OrderedDict
# Doubly Linked List
class Node:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.head = Node()
self.tail = Node()
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 move_to_last(self, node):
self.remove(node)
self.add_to_last(node)
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.move_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.move_to_last(node)
return None
if len(self.cache) == self.cap:
del self.cache[self.head.next.key]
self.remove(self.head.next)
node = Node(key=key, val=value)
self.cache[key] = node
self.add_to_last(node)
# OrderedDict
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
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
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
print("LRU Cache passed")
print("LRU Cache Ordered Dict passed")
#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;
}
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;
}
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]
31. Next Permutation¶
from typing import List
def nextPermutation(nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
i = n - 1
while i > 0 and nums[i - 1] >= nums[i]:
i -= 1
if i != 0:
j = n - 1
while nums[j] <= nums[i - 1]:
j -= 1
nums[i - 1], nums[j] = nums[j], nums[i - 1]
left, right = i, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
nums = [1, 2, 3]
nextPermutation(nums)
print(nums) # [1, 3, 2]
nums = [1, 2, 3, 4, 6, 5]
nextPermutation(nums)
print(nums) # [1, 2, 3, 5, 4, 6]
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;
}
76. Minimum Window Substring¶
from collections import Counter
def minWindow(s: str, t: str) -> str:
if not t or not s:
return ""
counts = Counter(t)
required = len(counts)
left, right = 0, 0
formed = 0
window_counts = dict()
result = float("inf"), None, None
while right < len(s):
char = s[right]
window_counts[char] = window_counts.get(char, 0) + 1
if char in counts and window_counts[char] == counts[char]:
formed += 1
while left <= right and formed == required:
char = s[left]
if right - left + 1 < result[0]:
result = (right - left + 1, left, right)
window_counts[char] -= 1
if char in counts and window_counts[char] < counts[char]:
formed -= 1
left += 1
right += 1
return "" if result[0] == float("inf") else s[result[1] : result[2] + 1]
s = "ADOBECODEBANC"
t = "ABC"
print(minWindow(s, t)) # BANC
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]
65. Valid Number¶
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;
}
19. Remove Nth Node From End of List¶
"""
- Given the `head` of a linked list, remove the `n-th` node from the end of the list and return its head.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
# Linked List
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
fast, slow = dummy, dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
def test_removeNthFromEnd() -> None:
head = list_from_array([1, 2, 3, 4, 5])
assert (list_to_array(removeNthFromEnd(head, 2))) == [1, 2, 3, 5]
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"
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;
}
2. Add Two Numbers¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def add_two_numbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
"""Add two numbers represented by linked lists."""
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2:
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
if carry:
cur.next = ListNode(val=carry)
return dummy.next
def test_add_two_numbers():
l1 = LinkedList([2, 4, 3]).head
l2 = LinkedList([5, 6, 4]).head
added = add_two_numbers(l1, l2)
assert LinkedList(added).to_array() == [7, 0, 8]
#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;
}
3. Longest Substring Without Repeating Characters¶
"""
- Classic variable sliding window problem. Use a set to keep track of the characters in the current window.
- Return the length of the longest substring without repeating characters.
- [Template tutorial by 灵山茶艾府](https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/1959540/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks)
"""
from collections import defaultdict
# Sliding Window Variable Max - HashMap
def lengthOfLongestSubstringHash(s: str) -> int:
n = len(s)
if n <= 1:
return n
left = 0
cnt = defaultdict(int)
res = 0
for right in range(n):
cnt[s[right]] += 1
while cnt[s[right]] > 1:
cnt[s[left]] -= 1
left += 1
res = max(res, right - left + 1)
return res
# Sliding Window Variable Max - Set
def lengthOfLongestSubstringSet(s: str) -> int:
n = len(s)
if n <= 1:
return n
left = 0
res = 0
window = set()
for right in range(n):
while left < right and s[right] in window:
window.remove(s[left])
left += 1
window.add(s[right])
res = max(res, right - left + 1)
return res
if __name__ == "__main__":
s = "abcabcbb"
assert lengthOfLongestSubstringHash(s) == 3
assert lengthOfLongestSubstringSet(s) == 3
#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;
}
173. Binary Search Tree Iterator¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# BST
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
self._leftmost_inorder(root)
def _leftmost_inorder(self, root):
while root:
self.stack.append(root)
root = root.left
def next(self) -> int:
topmost_node = self.stack.pop()
if topmost_node.right:
self._leftmost_inorder(topmost_node.right)
return topmost_node.val
def hasNext(self) -> bool:
return len(self.stack) > 0
root = build([7, 3, 15, None, None, 9, 20])
print(root)
# 7__
# / \
# 3 15
# / \
# 9 20
obj = BSTIterator(root)
print(obj.next()) # 3
print(obj.next()) # 7
print(obj.hasNext()) # True
26. Remove Duplicates from Sorted Array¶
#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;
}
4. Median of Two Sorted Arrays¶
from typing import List
# Brute Force
def findMedianSortedArraysBF(nums1: List[int], nums2: List[int]) -> float:
nums = sorted(nums1 + nums2)
n = len(nums)
if n % 2 == 0:
return (nums[n // 2 - 1] + nums[n // 2]) / 2
else:
return nums[n // 2]
# Binary Search
def findMedianSortedArraysBS(nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
imin, imax, half_len = 0, m, (m + n + 1) // 2
while imin <= imax:
i = (imin + imax) // 2
j = half_len - i
if i < m and nums2[j - 1] > nums1[i]:
imin = i + 1
elif i > 0 and nums1[i - 1] > nums2[j]:
imax = i - 1
else:
if i == 0:
max_of_left = nums2[j - 1]
elif j == 0:
max_of_left = nums1[i - 1]
else:
max_of_left = max(nums1[i - 1], nums2[j - 1])
if (m + n) % 2 == 1:
return max_of_left
if i == m:
min_of_right = nums2[j]
elif j == n:
min_of_right = nums1[i]
else:
min_of_right = min(nums1[i], nums2[j])
return (max_of_left + min_of_right) / 2
# |--------------|-----------------|--------------|
# | Approach | Time | Space |
# |--------------|-----------------|--------------|
# | Brute Force | O((n+m)log(n+m))| O(n+m) |
# | Binary Search| O(log(min(n,m)))| O(1) |
# |--------------|-----------------|--------------|
nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArraysBF(nums1, nums2)) # 2.0
print(findMedianSortedArraysBS(nums1, nums2)) # 2.0
15. 3Sum¶
from typing import List
# Left Right Pointers
def threeSum(nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total > 0:
right -= 1
elif total < 0:
left += 1
else:
res.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return res
nums = [-1, 0, 1, 2, -1, -4]
assert threeSum(nums) == [[-1, -1, 2], [-1, 0, 1]]
#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;
}
9. Palindrome Number¶
"""
- Return true if the given number is a palindrome. Otherwise, return false.
"""
# Reverse
def isPalindromeReverse(x: int) -> bool:
if x < 0:
return False
return str(x) == str(x)[::-1]
# Left Right Pointers
def isPalindromeLR(x: int) -> bool:
if x < 0:
return False
x = list(str(x)) # 121 -> ['1', '2', '1']
left, right = 0, len(x) - 1
while left < right:
if x[left] != x[right]:
return False
left += 1
right -= 1
return True
# |------------|------- |---------|
# | Approach | Time | Space |
# |------------|--------|---------|
# | Reverse | O(N) | O(N) |
# | Left Right | O(N) | O(1) |
# |------------|--------|---------|
x = 121
print(isPalindromeReverse(x)) # True
print(isPalindromeLR(x)) # True