Apple¶
Table of Contents¶
- 146. LRU Cache (Medium)
- 121. Best Time to Buy and Sell Stock (Easy)
- 347. Top K Frequent Elements (Medium)
- 139. Word Break (Medium)
- 1. Two Sum (Easy)
- 56. Merge Intervals (Medium)
- 155. Min Stack (Medium)
- 36. Valid Sudoku (Medium)
- 1606. Find Servers That Handled Most Number of Requests (Hard)
- 49. Group Anagrams (Medium)
- 189. Rotate Array (Medium)
- 200. Number of Islands (Medium)
- 122. Best Time to Buy and Sell Stock II (Medium)
- 125. Valid Palindrome (Easy)
- 14. Longest Common Prefix (Easy)
- 54. Spiral Matrix (Medium)
- 215. Kth Largest Element in an Array (Medium)
- 387. First Unique Character in a String (Easy)
- 622. Design Circular Queue (Medium)
- 88. Merge Sorted Array (Easy)
- 714. Best Time to Buy and Sell Stock with Transaction Fee (Medium)
- 560. Subarray Sum Equals K (Medium)
- 362. Design Hit Counter (Medium) 👑
- 283. Move Zeroes (Easy)
- 34. Find First and Last Position of Element in Sorted Array (Medium)
- 3. Longest Substring Without Repeating Characters (Medium)
- 208. Implement Trie (Prefix Tree) (Medium)
- 348. Design Tic-Tac-Toe (Medium) 👑
- 151. Reverse Words in a String (Medium)
- 53. Maximum Subarray (Medium)
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;
}
347. Top K Frequent Elements¶
-
Tags: Array, Hash Table, Divide And Conquer, Sorting, Heap Priority Queue, Bucket Sort, Counting, Quickselect
import heapq
from collections import Counter
from typing import List
# Heap + Counter
def topKFrequent(nums: List[int], k: int) -> List[int]:
minHeap = []
for val, freq in Counter(nums).items():
if len(minHeap) < k:
heapq.heappush(minHeap, (freq, val))
else:
heapq.heappushpop(minHeap, (freq, val))
return [i for _, i in minHeap]
# Counter (Most Common)
def topKFrequentCounter(nums: List[int], k: int) -> List[int]:
commons = Counter(nums).most_common(k)
return [i for i, _ in commons]
nums = [1, 1, 1, 2, 2, 3]
k = 2
print(topKFrequent(nums, k)) # [1, 2]
print(topKFrequentCounter(nums, k)) # [1, 2]
139. Word Break¶
from typing import List
# DP (Unbounded Knapsack)
def wordBreak(s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False for _ in range(n + 1)]
dp[0] = True
for i in range(1, n + 1):
for word in wordDict:
m = len(word)
if s[i - m : i] == word and dp[i - m]:
dp[i] = True
return dp[-1]
s = "leetcode"
wordDict = ["leet", "code"]
print(wordBreak(s, wordDict)) # True
#include <algorithm>
#include <cassert>
#include <ranges>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int max_len = ranges::max(wordDict, {}, &string::length).length();
unordered_set<string> words(wordDict.begin(), wordDict.end());
int n = s.length();
vector<int> f(n + 1);
f[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = i - 1; j >= max(i - max_len, 0); j--) {
if (f[j] && words.count(s.substr(j, i - j))) {
f[i] = true;
break;
}
}
}
return f[n];
}
};
int main() {
Solution solution;
string s = "leetcode";
vector<string> wordDict = {"leet", "code"};
assert(solution.wordBreak(s, wordDict) == true);
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;
}
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;
}
155. Min Stack¶
"""
- Implement a stack that supports push, pop, top, and retrieving the minimum element in constant time.
"""
# Stack
class MinStack:
def __init__(self):
self.stack = []
def push(self, val: int) -> None:
if self.stack:
self.stack.append((val, min(val, self.getMin())))
else:
self.stack.append((val, val))
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][1]
obj = MinStack()
obj.push(3)
obj.push(2)
obj.pop()
print(obj.top()) # 3
print(obj.getMin()) # 3
#include <algorithm>
#include <climits>
#include <iostream>
#include <stack>
#include <utility>
using namespace std;
class MinStack {
stack<pair<int, int>> st;
public:
MinStack() { st.emplace(0, INT_MAX); }
void push(int val) { st.emplace(val, min(getMin(), val)); }
void pop() { st.pop(); }
int top() { return st.top().first; }
int getMin() { return st.top().second; }
};
int main() {
MinStack minStack;
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
cout << minStack.getMin() << endl; // -3
minStack.pop();
cout << minStack.top() << endl; // 0
cout << minStack.getMin() << endl; // -2
return 0;
}
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
1606. Find Servers That Handled Most Number of Requests¶
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;
}
189. Rotate Array¶
"""
- Rotate array with reversing subarrays
"""
from typing import List
# Array
def rotate(nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(i: int, j: int) -> None:
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
n = len(nums)
k %= n
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
rotate(nums, k)
print(nums) # [5, 6, 7, 1, 2, 3, 4]
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// Array
void rotate(vector<int>& nums, int k) {
k %= nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
int k = 3;
rotate(nums, k);
// [5, 6, 7, 1, 2, 3, 4]
for (const auto& num : nums) {
cout << num << " ";
}
cout << endl;
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;
}
122. Best Time to Buy and Sell Stock II¶
"""
- Return the maximum profit you can achieve.
"""
from typing import List
# DP
def maxProfitDP1(prices: List[int]) -> int:
n = len(prices)
if n <= 1:
return 0
dp = [[0] * 2 for _ in range(n)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
return dp[-1][1]
# DP - Optimized
def maxProfitDP2(prices: List[int]) -> int:
n = len(prices)
if n <= 1:
return 0
hold = -prices[0]
profit = 0
for i in range(1, n):
hold = max(hold, profit - prices[i])
profit = max(profit, hold + prices[i])
return profit
# Greedy
def maxProfitGreedy(prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
profit += max(prices[i] - prices[i - 1], 0)
return profit
# |------------|------- |---------|
# | Approach | Time | Space |
# |------------|--------|---------|
# | DP1 | O(n) | O(n) |
# | DP2 | O(n) | O(1) |
# | Greedy | O(n) | O(1) |
# |------------|--------|---------|
prices = [7, 1, 5, 3, 6, 4]
print(maxProfitDP1(prices)) # 7
print(maxProfitDP2(prices)) # 7
print(maxProfitGreedy(prices)) # 7
#include <array>
#include <cassert>
#include <climits>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfitMemo(vector<int>& prices) {
int n = prices.size();
vector<array<int, 2>> memo(n, {-1, -1});
auto dfs = [&](this auto&& dfs, int i, bool hold) -> int {
if (i < 0) {
return hold ? INT_MIN : 0;
}
int& res = memo[i][hold];
if (res != -1) {
return res;
}
if (hold) {
return res = max(dfs(i - 1, true), // skip
dfs(i - 1, false) - prices[i]); // buy
} else {
return res = max(dfs(i - 1, false), // skip
dfs(i - 1, true) + prices[i]); // sell
}
};
return dfs(n - 1, false);
}
int maxProfitIterative(vector<int>& prices) {
int n = prices.size();
vector<array<int, 2>> dp(n, {0, 0});
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // buy
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); // sell
}
return dp[n - 1][1];
}
int maxProfitIterativeOptimized(vector<int>& prices) {
int n = prices.size();
if (n <= 1) return 0;
int hold = -prices[0], res = 0;
for (int i = 1; i < n; i++) {
hold = max(hold, res - prices[i]); // buy
res = max(res, hold + prices[i]); // sell
}
return res;
}
int maxProfitGreedy(vector<int>& prices) {
int n = prices.size();
if (n <= 1) return 0;
int res = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
res += prices[i] - prices[i - 1];
}
}
return res;
}
};
int main() {
Solution solution;
vector<int> prices = {7, 1, 5, 3, 6, 4};
assert(solution.maxProfitMemo(prices) == 7);
assert(solution.maxProfitIterative(prices) == 7);
assert(solution.maxProfitIterativeOptimized(prices) == 7);
assert(solution.maxProfitGreedy(prices) == 7);
return 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
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"
54. Spiral Matrix¶
"""
- Return all elements of the matrix in spiral order.
"""
from typing import List
# Array
def spiralOrder(matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:
return []
res = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for i in range(left, right + 1):
res.append(matrix[top][i])
top += 1
for i in range(top, bottom + 1):
res.append(matrix[i][right])
right -= 1
if top <= bottom:
for i in range(right, left - 1, -1):
res.append(matrix[bottom][i])
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1):
res.append(matrix[i][left])
left += 1
return res
# Math
def spiralOrderMath(matrix: List[List[int]]) -> List[int]:
dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]] # Right Down Left Up
m, n = len(matrix), len(matrix[0])
size = m * n
res = []
i, j, di = 0, -1, 0
while len(res) < size:
dx, dy = dirs[di]
for _ in range(n):
i += dx
j += dy
res.append(matrix[i][j])
di = (di + 1) % 4
n, m = m - 1, n
return res
print(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
# [1, 2, 3, 6, 9, 8, 7, 4, 5]
print(spiralOrderMath([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]))
# [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
215. Kth Largest Element in an Array¶
387. First Unique Character in a String¶
622. Design Circular Queue¶
# Design
class MyCircularQueue:
def __init__(self, k: int):
self.queue = [0] * k
self.head = 0
self.tail = -1
self.size = 0
self.capacity = k
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
self.tail = (self.tail + 1) % self.capacity
self.queue[self.tail] = value
self.size += 1
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
self.head = (self.head + 1) % self.capacity
self.size -= 1
return True
def Front(self) -> int:
if self.isEmpty():
return -1
return self.queue[self.head]
def Rear(self) -> int:
if self.isEmpty():
return -1
return self.queue[self.tail]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capacity
obj = MyCircularQueue(3)
print(obj.enQueue(1)) # True
print(obj.enQueue(2)) # True
print(obj.enQueue(3)) # True
print(obj.enQueue(4)) # False
print(obj.Rear()) # 3
print(obj.isFull()) # True
print(obj.deQueue()) # True
88. Merge Sorted Array¶
from typing import List
class merge:
@staticmethod
def lr(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1, p2, t = m - 1, n - 1, m + n - 1
while p1 >= 0 or p2 >= 0:
if p1 == -1:
nums1[t] = nums2[p2]
p2 -= 1
elif p2 == -1:
nums1[t] = nums1[p1]
p1 -= 1
elif nums1[p1] > nums2[p2]:
nums1[t] = nums1[p1]
p1 -= 1
else:
nums1[t] = nums2[p2]
p2 -= 1
t -= 1
if __name__ == "__main__":
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
merge.lr(nums1, m, nums2, n)
assert nums1 == [1, 2, 2, 3, 5, 6]
#include <cassert>
#include <vector>
using namespace std;
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1, t = m + n - 1;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
nums1[t] = nums2[p2];
p2--;
} else if (p2 == -1) {
nums1[t] = nums1[p1];
p1--;
} else if (nums1[p1] > nums2[p2]) {
nums1[t] = nums1[p1];
p1--;
} else {
nums1[t] = nums2[p2];
p2--;
}
t--;
}
}
};
int main() {
Solution solution;
vector<int> nums1 = {1, 3, 6, 0, 0, 0};
vector<int> nums2 = {2, 5, 6};
vector<int> output = {1, 2, 3, 5, 6, 6};
solution.merge(nums1, 3, nums2, 3);
assert(nums1 == output);
return 0;
}
714. Best Time to Buy and Sell Stock with Transaction Fee¶
"""
- Return the maximum profit you can achieve with the given transaction fee.
"""
from typing import List
# 1. DP
def maxProfitDP(prices: List[int], fee: int) -> int:
n = len(prices)
if n <= 1:
return 0
dp = [[0] * 2 for _ in range(n)]
dp[0][0] = -prices[0] - fee
dp[0][1] = 0
for i in range(1, n):
dp[i][0] = max(
dp[i - 1][0], # hold
dp[i - 1][1] - prices[i] - fee, # buy
)
dp[i][1] = max(
dp[i - 1][1], # hold
dp[i - 1][0] + prices[i], # sell
)
return max(dp[-1])
# 2. Greedy
def maxProfitGreedy(prices: List[int], fee: int) -> int:
n = len(prices)
if n == 0:
return 0
buy = prices[0]
profit = 0
for i in range(1, n):
if prices[i] < buy:
buy = prices[i]
elif prices[i] > buy + fee:
profit += prices[i] - buy - fee
buy = prices[i] - fee
return profit
prices = [1, 3, 2, 8, 4, 9]
fee = 2
print(maxProfitDP(prices, fee)) # 8
print(maxProfitGreedy(prices, fee)) # 8
560. Subarray Sum Equals K¶
from collections import defaultdict
from typing import List
# Prefix Sum
def subarraySum(nums: List[int], k: int) -> int:
preSums = defaultdict(int)
preSums[0] = 1
curSum = 0
res = 0
for num in nums:
curSum += num
res += preSums[curSum - k]
preSums[curSum] += 1
return res
nums = [1, 1, 1]
k = 2
print(subarraySum(nums, k)) # 2
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> prefixSum(n + 1);
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int res = 0;
unordered_map<int, int> cnt;
for (int ps : prefixSum) {
if (cnt.find(ps - k) != cnt.end()) res += cnt[ps - k];
cnt[ps]++;
}
return res;
}
int main() {
vector<int> nums = {1, 1, 1};
int k = 2;
cout << subarraySum(nums, k) << endl; // 2
return 0;
}
362. Design Hit Counter 👑¶
from collections import deque
class HitCounter:
def __init__(self):
self.hits = deque()
def hit(self, timestamp: int) -> None:
self.hits.append(timestamp)
def getHits(self, timestamp: int) -> int:
# Remove hits that are older than 5 minutes (300 seconds)
while self.hits and self.hits[0] <= timestamp - 300:
self.hits.popleft()
return len(self.hits)
obj = HitCounter()
obj.hit(1)
obj.hit(2)
obj.hit(3)
print(obj.getHits(4)) # 3
obj.hit(300)
print(obj.getHits(300)) # 4
print(obj.getHits(301)) # 3
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;
}
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;
}
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;
}
208. Implement Trie (Prefix Tree)¶
"""
### Trie
- A trie is a tree-like data structure whose nodes store the letters of an alphabet.
"""
class TrieNode:
def __init__(self):
self.children = {}
self.endOfWord = None
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.endOfWord = True
def search(self, word: str) -> bool:
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.endOfWord
def startsWith(self, prefix: str) -> bool:
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
# Your Trie object will be instantiated and called as such:
obj = Trie()
obj.insert("apple")
print(obj.search("word")) # False
print(obj.startsWith("app")) # True
348. Design Tic-Tac-Toe 👑¶
151. Reverse Words in a String¶
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