## Leetcode DS study plan list I

1. Day 1 Array
2. 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

1. Day 1 Array
2. Day 2 Array
3. Day 3 Array
4. Day 4 String
5. Day 5 String
6. Day 6 String
9. Day 9 Stack / Queue
10. 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
11. Day 11 Stack / Queue
12. Day 12 Stack / Queue
13. Day 13 Tree
14. Day 14 Tree
15. Day 15 Tree
16. Day 16 Tree
17. Day 17 Graph / Union Find
18. Day 18 Graph / Union Find
19. Day 19 Graph / Union Find
20. Day 20 Graph / Union Find
21. Day 21 Graph / Union Find
22. Day 22 Priority queue
23. Day 23 Priority queue
24. Day 24 Priority queue
25. Day 25 Ordered Set
26. Day 26 Trie
27. Day 27 Prefix Tree
28. 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]

• 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)


### 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


### 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]


### 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)


### 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 |= 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]


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)

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
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)


###