Microsoft¶
Table of Contents¶
- 1. Two Sum (Easy)
- 121. Best Time to Buy and Sell Stock (Easy)
- 88. Merge Sorted Array (Easy)
- 3. Longest Substring Without Repeating Characters (Medium)
- 15. 3Sum (Medium)
- 2. Add Two Numbers (Medium)
- 146. LRU Cache (Medium)
- 169. Majority Element (Easy)
- 14. Longest Common Prefix (Easy)
- 9. Palindrome Number (Easy)
- 56. Merge Intervals (Medium)
- 162. Find Peak Element (Medium)
- 42. Trapping Rain Water (Hard)
- 5. Longest Palindromic Substring (Medium)
- 4. Median of Two Sorted Arrays (Hard)
- 70. Climbing Stairs (Easy)
- 53. Maximum Subarray (Medium)
- 49. Group Anagrams (Medium)
- 48. Rotate Image (Medium)
- 224. Basic Calculator (Hard)
- 283. Move Zeroes (Easy)
- 75. Sort Colors (Medium)
- 51. N-Queens (Hard)
- 206. Reverse Linked List (Easy)
- 35. Search Insert Position (Easy)
- 11. Container With Most Water (Medium)
- 13. Roman to Integer (Easy)
- 21. Merge Two Sorted Lists (Easy)
- 200. Number of Islands (Medium)
- 20. Valid Parentheses (Easy)
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
169. Majority Element¶
"""
- Return the majority element in an array. The majority element is the element that appears more than `n // 2` times.
<iframe width="560" height="315" src="https://www.youtube.com/embed/7pnhv842keE?si=fBYlNfKzdkiLgkF1" 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>
| `num` | `count` | `res` |
| ----- | ------- | ----- |
| 2 | 1 | 2 |
| 2 | 2 | 2 |
| 1 | 1 | 2 |
| 1 | 0 | 2 |
| 1 | 1 | 1 |
| 2 | 0 | 1 |
| 2 | 1 | 2 |
"""
from collections import defaultdict
from typing import List
# Hash Map
def majorityElementHashMap(nums: List[int]) -> int:
n = len(nums)
freq = defaultdict(int)
for num in nums:
freq[num] += 1
if freq[num] > n // 2:
return num
# Array - Boyer-Moore Voting Algorithm
def majorityElementArray(nums: List[int]) -> int:
res = None
count = 0
for num in nums:
if count == 0:
res = num
count += 1 if num == res else -1
return res
# | Algorithm | Time Complexity | Space Complexity |
# |-----------|-----------------|------------------|
# | HashMap | O(N) | O(N) |
# | Array | O(N) | O(1) |
# |-----------|-----------------|------------------|
nums = [2, 2, 1, 1, 1, 2, 2]
print(majorityElementArray(nums)) # 2
print(majorityElementHashMap(nums)) # 2
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"
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
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;
}
162. Find Peak Element¶
42. Trapping Rain Water¶
"""
- 
<iframe width="560" height="315" src="https://www.youtube.com/embed/ZI2z5pq0TqA?si=OEYg01dbmzvmtIwZ" 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>
| Approach | Time | Space |
| ---------- | ---- | ----- |
| DP | O(N) | O(N) |
| Left Right | O(N) | O(1) |
| Monotonic | O(N) | O(N) |
"""
from typing import List
# DP
def trapDP(height: List[int]) -> int:
if not height:
return 0
n = len(height)
maxLeft, maxRight = [0 for _ in range(n)], [0 for _ in range(n)]
for i in range(1, n):
maxLeft[i] = max(maxLeft[i - 1], height[i - 1])
for i in range(n - 2, -1, -1):
maxRight[i] = max(maxRight[i + 1], height[i + 1])
res = 0
for i in range(n):
res += max(0, min(maxLeft[i], maxRight[i]) - height[i])
return res
# Left Right Pointers
def trapLR(height: List[int]) -> int:
if not height:
return 0
left, right = 0, len(height) - 1
maxL, maxR = height[left], height[right]
res = 0
while left < right:
if maxL < maxR:
left += 1
maxL = max(maxL, height[left])
res += maxL - height[left]
else:
right -= 1
maxR = max(maxR, height[right])
res += maxR - height[right]
return res
# Monotonic Stack
def trapStack(height: List[int]) -> int:
stack = []
total = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
top = stack.pop()
if not stack:
break
distance = i - stack[-1] - 1
bounded_height = min(height[i], height[stack[-1]]) - height[top]
total += distance * bounded_height
stack.append(i)
return total
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trapDP(height)) # 6
print(trapLR(height)) # 6
print(trapStack(height)) # 6
#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;
}
5. Longest Palindromic Substring¶
"""
- Return the longest palindromic substring in `s`.
"""
# DP - Interval
def longestPalindromeDP(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
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]
# Expand Around Center
def longestPalindromeCenter(s: str) -> str:
def expand_around_center(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)):
len1 = expand_around_center(i, i) # odd
len2 = expand_around_center(i, i + 1) # even
maxLen = max(len1, len2)
if maxLen > end - start:
start = i - (maxLen - 1) // 2
end = i + maxLen // 2
return s[start : end + 1]
s = "babad"
print(longestPalindromeDP(s)) # "bab"
print(longestPalindromeCenter(s)) # "aba"
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
70. Climbing Stairs¶
"""
- Return the number of distinct ways to reach the top of the stairs.
- `dp[n]` stores the number of distinct ways to reach the `n-th` stair.
- Formula: `dp[n] = dp[n - 1] + dp[n - 2]`.
- Initialize `dp[0] = 0`, `dp[1] = 1`, and `dp[2] = 2`.
"""
from functools import cache
# DP
def climbStairsDP(n: int) -> int:
if n <= 2:
return n
dp = [i for i in range(n + 1)]
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# DP (Optimized)
def climbStairsDPOptimized(n: int) -> int:
if n <= 2:
return n
first, second = 1, 2
for _ in range(3, n + 1):
first, second = second, first + second
return second
# Recursion
def climbStairsRecursion(n: int) -> int:
@cache
def dfs(i: int) -> int:
if i <= 1:
return 1
return dfs(i - 1) + dfs(i - 2)
return dfs(n)
# Greedy
def climbStairsGreedy(n: int) -> int:
if n <= 2:
return n
p1, p2 = 1, 2
for _ in range(3, n + 1):
p1, p2 = p2, p1 + p2
return p2
if __name__ == "__main__":
assert climbStairsDP(10) == 89
assert climbStairsDPOptimized(10) == 89
assert climbStairsRecursion(10) == 89
assert climbStairsGreedy(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;
}
53. Maximum Subarray¶
from typing import List
# DP Kadane
def maxSubArrayDP(nums: List[int]) -> int:
dp = [0 for _ in range(len(nums))]
dp[0] = nums[0]
maxSum = nums[0]
for i in range(1, len(nums)):
dp[i] = max(
dp[i - 1] + nums[i], # continue the previous subarray
nums[i], # start a new subarray
)
maxSum = max(maxSum, dp[i])
return maxSum
# 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
49. Group Anagrams¶
from collections import defaultdict
from typing import List
# Hash - List
def groupAnagrams(strs: List[str]) -> List[List[str]]:
result = defaultdict(list)
for s in strs:
count = [0] * 26
for i in s:
count[ord(i) - ord("a")] += 1
result[tuple(count)].append(s)
return list(result.values())
# |-------------|-----------------|--------------|
# | Approach | Time | Space |
# |-------------|-----------------|--------------|
# | Hash | O(n * k) | O(n) |
# |-------------|-----------------|--------------|
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(groupAnagrams(strs))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
#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;
}
48. Rotate Image¶
from copy import deepcopy
from typing import List
# Math
def rotate1(matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in range(n // 2):
for j in range(i, n - i - 1):
temp = matrix[i][j]
matrix[i][j] = matrix[n - j - 1][i]
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
matrix[j][n - i - 1] = temp
def rotate2(matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(n):
matrix[i].reverse()
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(matrix)
# [[1, 2, 3],
# [4, 5, 6],
# [7, 8, 9]]
matrix1 = deepcopy(matrix)
rotate1(matrix1)
print(matrix1)
# [[7, 4, 1],
# [8, 5, 2],
# [9, 6, 3]]
matrix2 = deepcopy(matrix)
rotate2(matrix2)
print(matrix2)
# [[7, 4, 1],
# [8, 5, 2],
# [9, 6, 3]]
224. Basic Calculator¶
# Stack
def calculate(s: str) -> int:
stack = []
result = 0
number = 0
sign = 1
for char in s:
if char.isdigit():
number = number * 10 + int(char)
elif char == "+":
result += sign * number
number = 0
sign = 1
elif char == "-":
result += sign * number
number = 0
sign = -1
elif char == "(":
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif char == ")":
result += sign * number
number = 0
result *= stack.pop() # pop sign
result += stack.pop() # pop previous result
result += sign * number
return result
print(calculate("(1+(4+5+2)-3)+(6+8)")) # 23
283. Move Zeroes¶
"""
- Move all zeroes to the end of the array while maintaining the relative order of the non-zero elements.
"""
from typing import List
def moveZeroes(nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
fast, slow = 0, 0
while fast < len(nums):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
fast += 1
nums = [0, 1, 0, 3, 12]
moveZeroes(nums)
print(nums) # [1, 3, 12, 0, 0]
#include <iostream>
#include <vector>
using namespace std;
void moveZeroes(vector<int>& nums) {
size_t n = nums.size();
size_t fast = 0, slow = 0;
while (fast < n) {
if (nums[fast] != 0) {
swap(nums[slow], nums[fast]);
slow++;
}
fast++;
}
}
int main() {
vector<int> nums = {0, 1, 0, 3, 12};
moveZeroes(nums);
// [1, 3, 12, 0, 0]
for (size_t i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << endl;
return 0;
}
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]
51. N-Queens¶
"""
- Hard
- [N-Queens](https://leetcode.com/problems/n-queens/)
- [N 皇后](https://leetcode.cn/problems/n-queens/)
"""
from typing import List
# Backtracking
def solveNQueens(n: int) -> List[List[str]]:
res = []
board = ["." * n for _ in range(n)]
def dfs(row):
if row == n:
res.append(board[:])
return None
for col in range(n):
if is_valid(row, col, board):
board[row] = board[row][:col] + "Q" + board[row][col + 1 :]
dfs(row + 1)
board[row] = board[row][:col] + "." + board[row][col + 1 :]
def is_valid(row, col, chessboard):
for i in range(row):
if chessboard[i][col] == "Q":
return False
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if chessboard[i][j] == "Q":
return False
i -= 1
j -= 1
i, j = row - 1, col + 1
while i >= 0 and j < len(chessboard):
if chessboard[i][j] == "Q":
return False
i -= 1
j += 1
return True
dfs(0)
return [["".join(row) for row in i] for i in res]
# Backtracking
def solveNQueens2(n: int) -> List[List[str]]:
res = []
queens = [0] * n
col = [False] * n
diag1 = [False] * (n * 2 - 1)
diag2 = [False] * (n * 2 - 1)
def dfs(r: int) -> None:
if r == n:
res.append(["." * c + "Q" + "." * (n - 1 - c) for c in queens])
return
for c, ok in enumerate(col):
if not ok and not diag1[r + c] and not diag2[r - c]:
queens[r] = c
col[c] = diag1[r + c] = diag2[r - c] = True
dfs(r + 1)
col[c] = diag1[r + c] = diag2[r - c] = False
dfs(0)
return res
if __name__ == "__main__":
print(solveNQueens(4))
# [['.Q..', '...Q', 'Q...', '..Q.'],
# ['..Q.', 'Q...', '...Q', '.Q..']]
print(solveNQueens(1))
# [['Q']]
print(solveNQueens2(4))
# [['.Q..', '...Q', 'Q...', '..Q.'],
# ['..Q.', 'Q...', '...Q', '.Q..']]
print(solveNQueens2(1))
# [['Q']]
206. Reverse Linked List¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def reverse_list_iterative(head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
prev = None
while cur:
temp = cur.next
cur.next = prev
prev = cur
cur = temp
return prev
def reverse_list_recursive(head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(cur, prev):
if not cur:
return prev
temp = cur.next
cur.next = prev
return reverse(temp, cur)
return reverse(head, None)
def test_reverse_list():
ll = LinkedList([1, 2, 3, 4, 5])
ll.head = reverse_list_iterative(ll.head)
assert ll.to_array() == [5, 4, 3, 2, 1]
ll = LinkedList([1, 2, 3, 4, 5])
ll.head = reverse_list_recursive(ll.head)
assert ll.to_array() == [5, 4, 3, 2, 1]
35. Search Insert Position¶
"""
- Return the index of the target if it is found. If not, return the index where it would be if it were inserted in order.
"""
from typing import List
# Binary Search
def searchInsert(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
return mid
return left
nums = [1, 3, 5, 6]
target = 5
print(searchInsert(nums, target)) # 2
#include <cassert>
#include <vector>
using namespace std;
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = 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;
}
};
int main() {
Solution solution;
vector<int> nums = {1, 3, 5, 6};
assert(solution.searchInsert(nums, 5) == 2);
assert(solution.searchInsert(nums, 2) == 1);
assert(solution.searchInsert(nums, 7) == 4);
assert(solution.searchInsert(nums, 0) == 0);
return 0;
}
11. Container With Most Water¶
"""
- Return the maximum area of water that can be trapped between the vertical lines.
"""
from typing import List
# Brute Force
def maxAreaBF(height: List[int]) -> int:
max_area = 0
for i in range(len(height)):
for j in range(i + 1, len(height)):
h = min(height[i], height[j])
w = j - i
max_area = max(max_area, h * w)
return max_area
# Left Right Pointers
def maxAreaLR(height: List[int]) -> int:
left, right = 0, len(height) - 1
res = 0
while left < right:
h = min(height[left], height[right])
w = right - left
res = max(res, h * w)
if height[left] < height[right]:
left += 1
else:
right -= 1
return res
# |------------|------- |---------|
# | Approach | Time | Space |
# |------------|--------|---------|
# | Brute Force| O(n^2) | O(1) |
# | Left Right | O(n) | O(1) |
# |------------|--------|---------|
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(maxAreaBF(height)) # 49
print(maxAreaLR(height)) # 49
#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;
}
13. Roman to Integer¶
from itertools import pairwise
# Arrays
def romanToInt(s: str) -> int:
ROMAN = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000,
}
res = 0
for x, y in pairwise(s):
x, y = ROMAN[x], ROMAN[y]
res += x if x >= y else -x
return res + ROMAN[s[-1]]
if __name__ == "__main__":
assert romanToInt("III") == 3
assert romanToInt("IV") == 4
assert romanToInt("IX") == 9
assert romanToInt("LVIII") == 58
assert romanToInt("MCMXCIV") == 1994
assert romanToInt("MMXXIII") == 2023
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;
}
200. Number of Islands¶
"""
- Count the number of islands in a 2D grid.
- Method 1: DFS
- Method 2: BFS (use a queue to traverse the grid)
- How to keep track of visited cells?
1. Mark the visited cell as `0` (or any other value) to avoid revisiting it.
2. Use a set to store the visited cells.
- Steps:
1. Init: variables
2. DFS/BFS: starting from the cell with `1`, turn all the connected `1`s to `0`.
3. Traverse the grid, and if the cell is `1`, increment the count and call DFS/BFS.
"""
from collections import deque
from copy import deepcopy
from typing import List
# DFS
def numIslandsDFS(grid: List[List[str]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
res = 0
def dfs(r, c):
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != "1":
return
grid[r][c] = "2"
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(m):
for c in range(n):
if grid[r][c] == "1":
dfs(r, c)
res += 1
return res
# BFS + Set
def numIslandsBFS1(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)]
visited = set()
res = 0
def bfs(r, c):
q = deque([(r, c)])
while q:
row, col = q.popleft()
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))
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))
bfs(r, c)
res += 1
return res
# BFS + Grid
def numIslandsBFS2(grid: List[List[str]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
res = 0
def bfs(r, c):
q = deque([(r, c)])
while q:
row, col = q.popleft()
for dr, dc in dirs:
nr, nc = dr + row, dc + col
if nr < 0 or nr >= m or nc < 0 or nc >= n or grid[nr][nc] != "1":
continue
grid[nr][nc] = "2"
q.append((nr, nc))
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
grid[i][j] = "2"
bfs(i, j)
res += 1
return res
grid = [
["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"],
]
print(numIslandsDFS(deepcopy(grid))) # 1
print(numIslandsBFS1(deepcopy(grid))) # 1
print(numIslandsBFS2(deepcopy(grid))) # 1
#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// dfs
int num_islands_dfs(vector<vector<char>> &grid) {
int m = grid.size(), n = grid[0].size();
int res = 0;
// c++23 lambda recursion
auto dfs = [&](this auto &&dfs, int r, int c) -> void {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1') {
return;
}
grid[r][c] = '0';
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') {
res++;
dfs(i, j);
}
}
}
return res;
}
// bfs
int num_islands_bfs(vector<vector<char>> &grid) {
int m = grid.size(), n = grid[0].size();
int res = 0;
vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
auto bfs = [&](int r, int c) {
queue<pair<int, int>> q;
q.push({r, c});
grid[r][c] = '0';
while (!q.empty()) {
auto [cr, cc] = q.front();
q.pop();
for (auto &[dr, dc] : dirs) {
int nr = cr + dr, nc = cc + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
grid[nr][nc] == '1') {
grid[nr][nc] = '0';
q.push({nr, nc});
}
}
}
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
res++;
bfs(i, j);
}
}
}
return res;
}
};
int main() {
Solution solution;
vector<vector<char>> grid = {{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}};
assert(solution.num_islands_dfs(grid) == 3);
grid = {{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}};
assert(solution.num_islands_bfs(grid) == 3);
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;
}