Data Structure
Leetcode DS study plan list I
- Day 1 Array
- Day 2 Array
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
set<int> m;
for (int num:nums) {
if (m.count(num)) return true;
m.insert(num);
}
return false;
}
};
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int accum = 0, max_sum = nums[0];
for (int num:nums) {
accum = max(num, num + accum);
max_sum = max(max_sum, accum);
}
return max_sum;
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> num_to_idx;
int j;
for (j= 0; j < nums.size(); j++) {
if (num_to_idx.count(target - nums[j])) break;
num_to_idx[nums[j]] = j;
}
return vector<int> {j, num_to_idx[target-nums[j]]};
}
};
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int t = m + n - 1;
while (m > 0 and n > 0) {
if (nums1[m-1] > nums2[n-1]) {
nums1[t] = nums1[m-1];
m--;
} else {
nums1[t] = nums2[n-1];
n--;
}
t--;
}
while (n > 0) {
nums1[t] = nums2[n-1];
n--;
t--;
}
}
};
Leetcode DS study plan list III
- Day 1 Array
- 325. Maximum Size Subarray Sum Equals k
- Prefix Sum
- 1151. Minimum Swaps to Group All 1’s Together
- Sliding Window
- 325. Maximum Size Subarray Sum Equals k
- Day 2 Array
- 1588. Sum of All Odd Length Subarrays
- Math Pattern
- 452. Minimum Number of Arrows to Burst Balloons
- Sorting / Sweep line
- 1588. Sum of All Odd Length Subarrays
- Day 3 Array
- 128. Longest Consecutive Sequence
- HashSet
- 448. Find All Numbers Disappeared in an Array
- Inplace Annotate / Swap
- 454. 4Sum II
- HasMap
- 128. Longest Consecutive Sequence
- Day 4 String
- Day 5 String
- 187. Repeated DNA Sequences
- Rolling Hash
- 5. Longest Palindromic Substring
- Two Pointers
- 187. Repeated DNA Sequences
- Day 6 String
- 44. Wildcard Matching
- Backtrack
- 214. Shortest Palindrome
- KMP
- 44. Wildcard Matching
- Day 7 Linked List
- 1634. Add Two Polynomials Represented as Linked Lists
- Two Pointers
- 369. Plus One Linked List
- Two Pointers
- 1634. Add Two Polynomials Represented as Linked Lists
- Day 8 Linked List
- 148. Sort List
- Bottom up merge sort on linked list
- 138. Copy List with Random Pointer
- 3 passes: 1) insert copy after original 2) add random for the copies 3) seperate
- 430. Flatten a Multilevel Doubly Linked List
- DFS
- 148. Sort List
- Day 9 Stack / Queue
- 281. Zigzag Iterator
- Use a queue to store [num_elements_left, iterator]
- 394. Decode String
- Put on stack when we see [, pop from stack and combine when we see ]
- 281. Zigzag Iterator
- Day 10 Stack / Queue
- 739. Daily Temperatures
- Monotonic Stack
- 42. Trapping Rain Water
- Sweep Line. Bidirection with a level line. level line is max(level, min(l, r)), it never goes down, and only goes as if both side archieve this new height. Alwasy move the shorter side
- 739. Daily Temperatures
- Day 11 Stack / Queue
- 402. Remove K Digits
- Monotonic Stack
- 456. 132 Pattern
- Monotonic Stack
- 402. Remove K Digits
- Day 12 Stack / Queue
- 84. Largest Rectangle in Histogram
- Monotonic Stack (Index)
- 862. Shortest Subarray with Sum at Least K
- Monotonic Deque
- 84. Largest Rectangle in Histogram
- Day 13 Tree
- 1602. Find Nearest Right Node in Binary Tree
- BFS
- 1469. Find All The Lonely Nodes
- BFS/DFS, check xor between two childrens each node in the tree.
- 1602. Find Nearest Right Node in Binary Tree
- Day 14 Tree
- 1522. Diameter of N-Ary Tree
- Postorder Traversal
- 337. House Robber III
- DP on tree
- 1522. Diameter of N-Ary Tree
- Day 15 Tree
- 1325. Delete Leaves With a Given Value
- Postorder Traversal, populate parents pointer, short link when child is leaf with target value
- 366. Find Leaves of Binary Tree
- Postorder Traversal, annotate node with height, then collect nodes by height
- 1325. Delete Leaves With a Given Value
- Day 16 Tree
- 124. Binary Tree Maximum Path Sum
- Postorder Traversal, cache maximum sum from leaf to each node.
- 968. Binary Tree Cameras
- Postorder Traversal, greedy place cameras.
- 124. Binary Tree Maximum Path Sum
- Day 17 Graph / Union Find
- 886. Possible Bipartition
- BFS / DFS find contradiction.
- 787. Cheapest Flights Within K Stops
- DP
- 886. Possible Bipartition
- Day 18 Graph / Union Find
- 261. Graph Valid Tree
- DFS / count number of connected components, check for cycle
- 547. Number of Provinces
- DFS / count number of connected components
- 261. Graph Valid Tree
- Day 19 Graph / Union Find
- 990. Satisfiability of Equality Equations
- Union Find to find connected components with = sign, then go through the != signs and check for violation
- 1319. Number of Operations to Make Network Connected
- DFS connected components count
- 990. Satisfiability of Equality Equations
- Day 20 Graph / Union Find
- 305. Number of Islands II
- Union Find, save number of connected components after each operation
- 1579. Remove Max Number of Edges to Keep Graph Fully Traversable
- Union Find, union with type 3 edges first. then check all type 2 and type 1 edges for redundency
- 305. Number of Islands II
- Day 21 Graph / Union Find
- 323. Number of Connected Components in an Undirected Graph
- DFS count number of connected components
- 1101. The Earliest Moment When Everyone Become Friends
- Union Find
- 323. Number of Connected Components in an Undirected Graph
- Day 22 Priority queue
- 253. Meeting Rooms II
- Use priority queue to track of meeting rooms in use. priority is the end time of on going meeting in each room.
- 23. Merge k Sorted Lists
- Use priority queue to keep track of iterator of linked lists
- 253. Meeting Rooms II
- Day 23 Priority queue
- 378. Kth Smallest Element in a Sorted Matrix Binary Search
- Binary Search
- 295. Find Median from Data Stream
- Priority Queue, use two priority queues one for smaller half, one for larger half
- 378. Kth Smallest Element in a Sorted Matrix Binary Search
- Day 24 Priority queue
- Day 25 Ordered Set
- Day 26 Trie
- Day 27 Prefix Tree
- Day 28 Prefix Tree
325. Maximum Size Subarray Sum Equals k
- Prefix Sum
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
max_len = 0
prefix_sum = {0:-1}
accum = 0
for r, num in enumerate(nums):
accum += num
if accum - k in prefix_sum:
max_len = max(max_len, r - prefix_sum[accum - k])
if accum not in prefix_sum:
prefix_sum[accum] = r
return max_len
1151. Minimum Swaps to Group All 1’s Together
- Sliding Window
class Solution:
def minSwaps(self, data: List[int]) -> int:
ws = sum(data)
accum = sum(data[:ws])
min_swaps = ws - accum
for r in range(ws, len(data)):
accum += data[r]
accum -= data[r - ws]
min_swaps = min(min_swaps, ws - accum)
return min_swaps
1588. Sum of All Odd Length Subarrays
- Prefix Sum O(N^2)
class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
prefix_sum = [0]
for num in arr: prefix_sum.append(prefix_sum[-1] + num)
total = 0
for l in range(1, len(arr) + 1):
for r in range(l, len(arr) + 1):
if (r - l + 1) % 2 == 0: continue
total += prefix_sum[r] - prefix_sum[l - 1]
return total
- Math O(N) arr[i] will be the starting entry in (n - i) subarries arr[i] will be a non-staring entry in (n - i) * i subarries total (n - i) + (n - i) * i = (i + 1) * (n - i) among them about half is odd length.
class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
total = 0
n = len(arr)
for i, num in enumerate(arr):
total += num * (((i + 1) * (n - i) + 1) // 2)
return total
452. Minimum Number of Arrows to Burst Balloons
- Sorting / Sweep line
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key=lambda x: x[1])
total = 1
end = points[0][1]
for l, r in points:
if l > end:
total += 1
end = r
return total
128. Longest Consecutive Sequence
- HashSet
Hash the numbers. For each unique number x, if x-1 not in set, means it is a head for a desired sequence, loop and mark the sequence’s length.
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
unique_nums = set(nums)
max_length = 0
for num in unique_nums:
if num - 1 not in unique_nums:
i = num
length = 1
while i + 1 in unique_nums:
i += 1
length += 1
max_length = max(max_length, length)
return max_length
448. Find All Numbers Disappeared in an Array
- Inplace annotate
Use negative sign to mark number exist or not.
class Solution:
def findDisappearedNumbers(self, nums):
for num in nums:
nums[abs(num) - 1] = - abs(nums[abs(num) - 1])
return [i for i, num in enumerate(nums, 1) if num > 0]
- Swap
Try to put x at nums[x-1] by swapping nums[i] with nums[nums[i] - 1]
class Solution:
def findDisappearedNumbers(self, nums):
for i, num in enumerate(nums):
while i != nums[i] - 1 and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
results = [i for i, c in enumerate(nums, 1) if i != c]
return results
Example:
Input
i
|
0 1 2 3 4 5 6 7
[4, 3, 2, 7, 8, 2, 3, 1]
| |
nums[i] nums[nums[i]-1]
After 1 swap i | 0 1 2 3 4 5 6 7 [7, 3, 2, 4, 8, 2, 3, 1] | | nums[i] nums[nums[i]-1]
After 2 swap i | 0 1 2 3 4 5 6 7 [3, 3, 2, 4, 8, 2, 7, 1] # 7 is at its right location! | | | nums[nums[i]-1] nums[i]
After 3 swap i | 0 1 2 3 4 5 6 7 [2, 3, 3, 4, 8, 2, 7, 1] # 3 is at its right location 2 | | | nums[nums[i]-1] nums[i]
After 4 swap i | 0 1 2 3 4 5 6 7 [3, 2, 3, 4, 8, 2, 7, 1] # deuplicate found can’t do anything more move on | | | nums[nums[i]-1] nums[i]
i
| 0 1 2 3 4 5 6 7 [3, 2, 3, 4, 8, 2, 7, 1] # i == nums[i] - 1 already in right location
|
nums[i]
i
| 0 1 2 3 4 5 6 7 [3, 2, 3, 4, 8, 2, 7, 1] # i == nums[i] - 1 already in right location
|
nums[i]
i
| 0 1 2 3 4 5 6 7 [3, 2, 3, 4, 8, 2, 7, 1] # i == nums[i] - 1 already in right location
|
nums[i]
i
| 0 1 2 3 4 5 6 7 [3, 2, 3, 4, 8, 2, 7, 1] # should swap
| |
nums[i] nums[nums[i] - 1]
After 5 swap
i
| 0 1 2 3 4 5 6 7 [3, 2, 3, 4, 1, 2, 7, 8] # should swap | | | nums[i] nums[nums[i] - 1]
[1, 2, 3, 4, 3, 2, 7, 8] will terminate at this / / / / x x / /
454. 4Sum II
- HasMap
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
def get_two_sums(iterables):
counter = Counter()
for elements in itertools.product(*iterables):
counter[sum(elements)] += 1
return counter
two_sum_1, two_sum_2 = list(map(get_two_sums, [(nums1, nums2), (nums3, nums4)]))
total = 0
for s1, c1 in two_sum_1.items():
if 0 - s1 in two_sum_2:
total += c1 * two_sum_2[0-s1]
return total
1427. Perform String Shifts
- Math
class Solution:
def stringShift(self, s: str, shift: List[List[int]]) -> str:
shifts = 0
for d, amt in shift:
shifts = shifts + amt if d == 1 else shifts - amt
shifts = shifts % len(s)
return s[-shifts:] + s[:-shifts]
409. Longest Palindrome
- Math
class Solution:
def longestPalindrome(self, s: str) -> int:
char_counts = Counter(s)
has_odd = 0
total = 0
for v in char_counts.values():
has_odd |= v & 1
total += 2 * (v // 2)
return total + has_odd
187. Repeated DNA Sequences
- Rolling Hash
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
mask = (1 << (2 * 10)) -1
to_int = {c:i for i, c in enumerate("ACGT")}
def rolling_hash(code, c):
code <<= 2
code &= mask
code |= to_int[c]
return code
code = 0
for c in s[:10]: code = rolling_hash(code, c)
result = []
seen = {code: 1}
for r, c in enumerate(s[10:], 10):
code = rolling_hash(code, c)
seen[code] = seen.get(code, 0) + 1
if seen[code] == 2: result.append(s[r-9:r+1])
return result
5. Longest Palindromic Substring
- Two Pointers
class Solution:
def longestPalindrome(self, s: str) -> str:
max_length, max_l, max_r = 0, None, None
for i in range(len(s)):
l, r, length = i-1, i+1, 1
while 0 <= l < r < len(s) and s[l] == s[r]: length += 2; l -= 1; r += 1
if length > max_length: max_length, max_l, max_r = length, l+1, r-1
l, r, length = i, i + 1, 0
while 0 <= l < r < len(s) and s[l] == s[r]: length += 2; l -= 1; r += 1
if length > max_length: max_length, max_l, max_r = length, l+1, r-1
return s[max_l: max_r + 1]
1634. Add Two Polynomials Represented as Linked Lists
Like add two list, careful with coeff 0.
class Solution:
def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':
curr = sentinel = PolyNode()
while poly1 and poly2:
if poly1.power > poly2.power:
curr.next = PolyNode(poly1.coefficient, poly1.power)
curr = curr.next
poly1 = poly1.next
elif poly2.power > poly1.power:
curr.next = PolyNode(poly2.coefficient, poly2.power)
curr = curr.next
poly2 = poly2.next
else:
coef = poly1.coefficient + poly2.coefficient
if coef != 0:
curr.next = PolyNode(coef, poly1.power)
curr = curr.next
poly1 = poly1.next
poly2 = poly2.next
curr.next = None
if poly1: curr.next = poly1
if poly2: curr.next = poly2
return sentinel.next
369. Plus One Linked List
Watch out for 123999. Keep track of the last non 9 node. increment that by 1 and set the rest 9 to 0.
class Solution:
def plusOne(self, head: ListNode) -> ListNode:
sentinel = slow = ListNode(val=0, next=head)
fast = head
while fast:
if fast.val != 9:
slow = fast
fast = fast.next
slow.val += 1
while slow.next:
slow.next.val = 0
slow = slow.next
return sentinel if sentinel.val == 1 else sentinel.next
281. Zigzag Iterator
class ZigzagIterator:
def __init__(self, *vectors):
self.vectors = vectors
self.__iter__()
def __iter__(self):
self.deque = deque()
for vec in self.vectors:
length = len(vec)
if length > 0:
self.deque.append((length, iter(vec)))
def __next__(self):
n, it = self.deque.popleft()
val = next(it)
n -= 1
if n: self.deque.append((n, it))
return val
next = __next__
def hasNext(self):
return len(self.deque) > 0
402. Remove K Digits
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stack = []
for digit in num:
while stack and k and stack[-1] > digit:
k -= 1
stack.pop()
stack.append(digit)
if k: stack = stack[:-k]
num = ''.join(stack)
l = 0
while l < len(num) and num[l] == '0': l += 1
return num[l:] if num[l:] else '0'
862. Shortest Subarray with Sum at Least K
class Solution:
def shortestSubarray(self, nums: List[int], k: int) -> int:
n = len(nums)
prefix_sum = [0]
for num in nums:
prefix_sum.append(prefix_sum[-1] + num)
shortest = n + 1
queue = deque()
for r, r_sum in enumerate(prefix_sum):
while queue and r_sum <= prefix_sum[queue[-1]]:
queue.pop()
while queue and r_sum - prefix_sum[queue[0]] >= k:
shortest = min(shortest, r - queue[0])
queue.popleft()
queue.append(r)
return shortest if shortest < n + 1 else -1
1602. Find Nearest Right Node in Binary Tree
class Solution:
def findNearestRightNode(self, root: TreeNode, u: TreeNode) -> Optional[TreeNode]:
level = deque([root])
found = False
while level:
for _ in range(len(level)):
node = level.popleft()
if found: return node
if node == u: found = True
level.extend((child for child in (node.left, node.right) if child))
if found: return None
return None
1522. Diameter of N-Ary Tree
class Solution:
def diameter(self, root: 'Node') -> int:
diameter = 0
depth = dict()
stack = [(root, 0)]
while stack:
node, post = stack.pop()
if not post:
stack.append((node, 1))
for child in node.children:
stack.append((child, 0))
else:
children_depths = [depth.get(child, 0) for child in node.children]
top_2 = nlargest(2, children_depths)
depth[node] = max(top_2, default=0) + 1
diameter = max(diameter, sum(top_2))
return diameter
124. Binary Tree Maximum Path Sum
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
max_path_sum = root.val
path_sum = {None: 0}
stack = [(root, 0)]
while stack:
node, post = stack.pop()
if node is None: continue
if post:
l = path_sum[node.left]
r = path_sum[node.right]
path_sum[node] = max(node.val, l + node.val, r + node.val, 0)
max_path_sum = max(max_path_sum, l + r + node.val)
else:
stack.extend([(node, 1), (node.left, 0), (node.right, 0)])
return max_path_sum
1579. Remove Max Number of Edges to Keep Graph Fully Traversable
class UnionFind:
def __init__(self, n):
self.parents = list(range(n))
self.sizes = [1] * n
def _find_recursive(self, i):
while i != self.parents[i]:
# path compression, have i points to the cluster centroid
self.parents[i] = self._find_recursive(self.parents[i])
i = self.parents[i]
return i
def _find_iterative(self, i):
# 1 path to find the root
root = i
while self.parents[root] != root:
root = self.parents[root]
# 2 path to assign every node in the path to points at root
while self.parents[i] != root:
parent = self.parents[i]
self.parents[i] = root
i = parent
return root
find = _find_recursive
def union(self, p, q):
root_p, root_q = map(self.find, (p, q))
if root_p == root_q: return 0
small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
self.parents[small] = big
self.sizes[big] += self.sizes[small]
return 1
class Solution:
def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
total = extra = 0
ufa = UnionFind(n + 1)
ufb = UnionFind(n + 1)
for t, i, j in edges:
if t == 3: # both
if a_need := ufa.union(i, j): total += 1
if b_need := ufb.union(i, j): total += 1
if a_need == 0 and b_need == 0: extra += 1
for t, i, j in edges:
if t == 1: # alice
if a_need := ufa.union(i, j): total += 1
else: extra += 1
elif t == 2: # bob
if b_need := ufb.union(i, j): total += 1
else: extra += 1
return extra if total == 2 * n - 2 else -1
1756. Design Most Recently Used Queue
from sortedcontainers import SortedList
class MRUQueue:
def __init__(self, n: int):
self.data = SortedList((i, i) for i in range(1, n+1))
def fetch(self, k: int) -> int:
_, x = self.data.pop(k-1)
i = self.data[-1][0] + 1 if self.data else 0
self.data.add((i, x))
return x
211. Design Add and Search Words Data Structure
class TrieNode(defaultdict):
def __init__(self):
self.terminal = False
self.default_factory = TrieNode
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for char in word: node = node[char]
node.terminal = True
def search(self, word: str) -> bool:
n = len(word)
def dfs(node, i):
if i == n: return node.terminal
char = word[i]
if char == '.':
for key in node:
if dfs(node[key], i+1): return True
return False
elif char not in node: return False
else: return dfs(node[char], i+1)
return dfs(self.root, 0)
###