# 1. Two Sum (opens new window)
# Hashtable
Store the value-index pair of each element in map. For value x of nums, check if target - x also in the map and get the corresponding index from map.
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); ++i){
if (map.find(target - nums[i]) != map.end())
return {map[target - nums[i]], i};
map[nums[i]] = i;
}
return {};
}
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i){
if (map.containsKey(target - nums[i])){
result[0] = i;
result[1] = map.get(target - nums[i]);
return result;
}
map.put(nums[i], i);
}
return result;
}
def twoSum(self, A: List[int], t: int) -> List[int]:
pos = collections.defaultdict(int)
for i, a in enumerate(A):
if t - a in pos:
return [pos[t - a], i]
pos[a] = i
# 146. LRU Cache (opens new window)
Double linked list
class LRUCache {
class Node{
int key;
int val;
Node next;
Node prev;
}
private void move(Node node){
Node pre = node.prev;
Node nxt = node.next;
pre.next = nxt;
nxt.prev = pre;
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private Map<Integer, Node> map = new HashMap<>();
private int c;
private int capacity;
private Node head, tail;
public LRUCache(int capacity) {
this.c = 0;
this.capacity = capacity;
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
else{
move(node);
return node.val;
}
}
public void put(int key, int value) {
Node node = map.get(key);
if (node != null){
node.val = value;
move(node);
}
else{
Node newnode = new Node();
newnode.key = key;
newnode.val = value;
map.put(key, newnode);
if (c == capacity){
Node cur = tail.prev;
map.remove(cur.key);
tail.prev = tail.prev.prev;
tail.prev.next = tail;
c--;
}
newnode.prev = head;
newnode.next = head.next;
head.next.prev = newnode;
head.next = newnode;
c++;
}
}
}
class Node:
def __init__(self, key = None, val = None):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.c = capacity
self.map = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def move_to_top(self, key):
node = self.map[key]
node.prev.next = node.next
node.next.prev = node.prev
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key in self.map:
self.move_to_top(key)
res = self.map.get(key, -1)
if res == -1:
return res
else:
return res.val
def put(self, key: int, value: int) -> None:
if key in self.map:
self.map[key].val = value
self.move_to_top(key)
else:
if len(self.map) == self.c:
self.map.pop(self.tail.prev.key)
self.tail.prev = self.tail.prev.prev
self.tail.prev.next = self.tail
new = Node(key, value)
self.map[key] = new
new.prev = self.head
new.next = self.head.next
self.head.next.prev = new
self.head.next = new
# 1249. Minimum Remove to Make Valid Parentheses (opens new window)
Two pass, remove the extra ')' from left to right, and extra '(' from right to left.
private StringBuilder remove(CharSequence string, char open, char close) {
StringBuilder sb = new StringBuilder();
int curr = 0;
for (int i = 0; i < string.length(); ++i) {
char ch = string.charAt(i);
if (ch == open) {
curr++;
} if (ch == close) {
if (curr == 0) continue;
curr--;
}
sb.append(ch);
}
return sb;
}
public String minRemoveToMakeValid(String s) {
StringBuilder result = remove(s, '(', ')');
result = remove(result.reverse(), ')', '(');
return result.reverse().toString();
}
def minRemoveToMakeValid(self, s: str) -> str:
def remove(s, op, cl):
ans, curr = "", 0
for ch in s:
if ch == op:
curr += 1
if ch == cl:
if curr == 0:
continue
curr -= 1
ans += ch
return ans
res = remove(s, '(', ')')
return remove(res[::-1], ')', '(')[::-1]
# 56. Merge Intervals (opens new window)
Greedy.
We sort intervals by the starting position. Then traverse the sorted intervals, if the current interval [x, y] doesn't overlap with the previous ones, meaning there exist a gap before x.
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
for (auto interval : intervals) {
if (ans.empty() || ans.back()[1] < interval[0])
ans.push_back(interval);
else
ans.back()[1] = max(ans.back()[1], interval[1]);
}
return ans;
}
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
LinkedList<int[]> ans = new LinkedList<>();
for (int[] interval : intervals) {
if (ans.isEmpty() || ans.getLast()[1] < interval[0])
ans.add(interval);
else
ans.getLast()[1] = Math.max(ans.getLast()[1], interval[1]);
}
return ans.toArray(new int[ans.size()][]);
}
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
res=[]
for i in intervals:
if res and res[-1][1]>=i[0]:
res[-1][1]=max(res[-1][1],i[1])
else:
res.append(i)
return res
# 200. Number of Islands (opens new window)
BFS over grids, when we reach an unvisited land, find all the lands of the same island.
int numIslands(vector<vector<char>>& A) {
int m = A.size(), n = A[0].size(), ans = 0;
vector<vector<int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
deque<vector<int>> deq;
vector<int> cur;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (A[i][j] == '1') {
A[i][j] = 'v';
deq.clear();
deq.push_back({i, j});
while (!deq.empty()) {
cur = deq.front();
deq.pop_front();
for (auto dir : dirs) {
int nx = cur[0] + dir[0], ny = cur[1] + dir[1];
if (0 <= nx && nx < m && 0 <= ny && ny < n && A[nx][ny] == '1') {
A[nx][ny] = 'v';
deq.push_back({nx, ny});
}
}
}
ans++;
}
return ans;
}
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
index = 0
dirs = ((1, 0), (0, 1), (-1, 0), (0, -1))
dq = collections.deque()
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
grid[i][j] = "v"
dq.append((i, j))
while dq:
ox, oy = dq.popleft()
for x, y in dirs:
nx, ny = x + ox, y + oy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1":
dq.append((nx, ny))
grid[nx][ny] = "v"
index += 1
return index
# 680. Valid Palindrome II (opens new window)
def validPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]:
a, b = s[l + 1 : r + 1], s[l : r]
return l + 1 == r or a == a[::-1] or b == b[::-1]
l += 1
r -= 1
return True
# 314. Binary Tree Vertical Order Traversal (opens new window)
DFS over tree and save nodes by horizontal and vertical indexes.
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
d = collections.defaultdict(list)
def dfs(root, col, dep):
if not root:
return []
d[col].append([dep, root.val])
if root.left:
dfs(root.left, col - 1, dep + 1)
if root.right:
dfs(root.right, col + 1, dep + 1)
dfs(root, 0, 0)
ans = []
for i in sorted(d.keys()):
cur = sorted(d[i], key = lambda x : x[0])
ans.append(list(x[1] for x in cur))
return ans
BFS
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
d = collections.defaultdict(list)
dq = collections.deque()
dq.append((root, 0, 0))
while dq:
curn, curx, cury = dq.popleft()
d[curx].append([cury, curn.val])
if curn.left:
dq.append([curn.left, curx - 1, cury - 1])
if curn.right:
dq.append([curn.right, curx + 1, cury - 1])
ans = []
for i in sorted(d.keys()):
cur = sorted(d[i], key = lambda x : -x[0])
ans.append(list(x[1] for x in cur))
return ans