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
  7. Day 7 Linked List
  8. Day 8 Linked List
  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]
        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)

###