Leetcode ALG study plan list I

  1. Day 1 Binary Search
  2. Day 2 Two Pointers
  3. Day 3 Two Pointers
  4. Day 4 Two Pointers 
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo=0, hi=nums.size() - 1, mid;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if (nums[mid] == target)     return mid;
            else if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
};

class Solution {
public:
    int firstBadVersion(int n) {
        int lo=0, hi=n, mid;
        while (lo < hi){
            mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
};

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size(), mid;
        while (lo < hi){
            mid = lo + (hi - lo) / 2;
            if (nums[mid] >= target) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
};

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        vector<int> result;
        while (l <= r) {
            if (abs(nums[l]) < abs(nums[r])) 
                result.push_back(nums[r] * nums[r--]);
            else 
                result.push_back(nums[l] * nums[l++]);
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        int prev, curr, next, temp;
        k %= n;
        for (int start=0; start < gcd(n, k); start++){
            curr = start, prev = nums[start];
            while (true) {
                next = (curr + k) % n;
                temp = nums[next];
                nums[next] = prev;
                prev = temp;
                curr = next;
                if (curr == start) break;
            }
        }
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int l = 0, r = 0;
        while (r <  nums.size()) {
            while (r < nums.size() and nums[r] == 0) r++;
            if (r < nums.size()) swap(nums[l], nums[r]);
            l++;
            r++;
        }
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0, r = numbers.size() - 1;
        vector<int> result;
        while (l < r) {
            int s = numbers[l] + numbers[r];
            if (s == target) {
                result.push_back(l+1);
                result.push_back(r+1);
                break;
            }
            if (s > target) r--;
            if (s < target) l++;
        }
        return result;
    }
};

Leetcode ALG study plan list III

  1. Day 1 Binary Search
  2. Day 2 Binary Search
  3. Day 3 Two Pointers
    • 287. Find the Duplicate Number
      • Cycle detection. First phase slow meets fast. Second phase, reset slow, set fast to slow speed. When they meet again.
    • 1229. Meeting Scheduler
      • Sort two peoples schedule and do two pointers sweep line. min(e1, e2) >= max(s1, s2) + d then return. Otherwise, advance the people with smallest e.
      • Can be done with min priority queue, push all opening longer than duration on to it. keep checking the top two. Since one person’s schedule don’t allow overlap, if overlap, they must be two people.
  4. Day 4 Two Pointers
    • 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
    • 1868. Product of Two Run-Length Encoded Arrays
      • For each RLE, use two variables indicating the ith entry we are accessing and how many of it used up already.
  5. Day 5 Sliding Window
  6. Day 6 Sliding Window
  7. Day 7 Breadth-First Search / Depth-First Search
  8. Day 8 Breadth-First Search / Depth-First Search
  9. Day 9 Breadth-First Search / Depth-First Search
  10. Day 10 Breadth-First Search / Depth-First Search
  11. Day 11 Recursion / Backtracking
    • 254. Factor Combinations
      • Backtrack on [list of factors, previous factor, remainder], choice is new factor in range(previous factor, remainder ** .5)
    • 394. Decode String
      • When encounter [ recurse call with index + 1, return string built and index. Can be solved with stack too.
  12. Day 12 Recursion / Backtracking
    • 51. N-Queens
      • Candidate / state is the set of queen position. Go row by row, at given row consider each valid column and dfs on.
      • main diagonal and off diagnoal can be identified by r + c and r - c
    • 37. Sudoku Solver
      • Candidate / state is board. Go through each unfilled locations, consider each valid guess and dfs on.
      • the subbox given point is in is range(r // 3 * 3, r // 3 * 3 + 3), range(c // 3 * 3, c // 3 * 3 + 3)
  13. Day 13 Recursion / Backtracking
  14. Day 14 Recursion / Backtracking
  15. Day 15 Divide and Conquer
  16. Day 16 Dynamic Programming
  17. Day 17 Dynamic Programming
  18. Day 18 Dynamic Programming
    • 221. Maximal Square
      • f(i, j) = max side length of square with bottom right corner at (i, j)
    • 85. Maximal Rectangle
      • Precompute maximum height from top(or bottom or left or right) at each location. Then use largest rectangle area functions to columns(or rows).
  19. Day 19 Dynamic Programming
  20. Day 20 Dynamic Programming
  21. Day 21 Dynamic Programming
  22. Day 22 Topological Sort
  23. Day 23 Topological Sort
  24. Day 24 Topological Sort
  25. Day 25 Bit Manipulation
  26. Day 26 Others
  27. Day 27 Others

1868. Product of Two Run-Length Encoded Arrays

class Solution:
    def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
        i1 = i2 = u1 = u2 = 0
        result = []
        
        while i1 < len(encoded1) and i2 < len(encoded2):
            (v1, c1), (v2, c2) = encoded1[i1], encoded2[i2]
            n1, n2 = c1 - u1, c2 - u2
            product, reps = v1 * v2, min(n1, n2)
            
            if result and product == result[-1][0]: result[-1][1] += reps
            else: result.append([product, reps])

            if n1 > reps:  u1 += reps
            else:          i1 += 1; u1 = 0
            
            if n2 > reps: u2 += reps
            else:         i2 += 1; u2 = 0

        return result

159. Longest Substring with At Most Two Distinct Characters

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str, k: int = 2) -> int:
        n = len(s)
        max_length = 0
        window = dict()
        
        l, r = 0, 0
        while r != n:
            window[s[r]] = window.get(s[r], 0) + 1
            while len(window) > k:
                window[s[l]] -= 1
                if window[s[l]] == 0: window.pop(s[l])
                l += 1

            max_length = max(max_length, r - l + 1)
            r += 1
        return max_length

340. Longest Substring with At Most K Distinct Characters

class LRU(OrderedDict):
    'Store items in the order the keys were last added'
    def __init__(self, k):
        super().__init__()
        self.k = k
    
    def add(self, key, value):
        super().__setitem__(key, value)
        self.move_to_end(key)
        
    def pop(self):
        if len(self) <= self.k: return None
        _, v = self.popitem(last=False)
        return v
    
class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        if not s or not k: return 0
        max_len = 0
        l = -1            
        window = LRU(k)
        for r, char in enumerate(s): # O(N)
            window.add(char, r)
            pos = window.pop()
            if pos is not None: l = pos
            max_len = max(max_len, r-l)
        return max_len

1469. Find All The Lonely Nodes

class Solution:
    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:
        lonely = []        
        stack = [root]
        while stack:
            node = stack.pop()
            if node.left and not node.right: lonely.append(node.left.val)
            if node.right and not node.left: lonely.append(node.right.val)
            if node.left: stack.append(node.left)    
            if node.right: stack.append(node.right)
        return lonely

863. All Nodes Distance K in Binary Tree

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        parents = {root: None}
        stack = [root]
        while stack:
            node = stack.pop()
            for child in [node.left, node.right]:
                if not child: continue
                parents[child] = node
                stack.append(child)
                
        visited = set([target])
        queue = deque([target])
        for _ in range(k):
            for i in range(len(queue)):
                node = queue.popleft()
                for next_node in [node.left, node.right, parents[node]]:
                    if not next_node or next_node in visited: continue
                    queue.append(next_node)
                    visited.add(next_node)
        
        return [nd.val for nd in queue]

752. Open the Lock

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:     
        if target in deadends or "0000" in deadends: return -1
        def get_nei(n):
            if n == "0": return "19"
            if n == "9": return "08"
            return f"{int(n)+1}{int(n)-1}"
        
        def get_next(state):
            for i in range(4):
                for n in get_nei(state[i]):
                    new_state = state[:i] + n + state[i+1:]
                    yield new_state
            
        seen = set()
        queue = deque(["0000"])
        k = 0
        while queue:
            for _ in range(len(queue)):
                state = queue.popleft()
                if state == target: return k
                for new_state in get_next(state):
                    if new_state in seen or new_state in deadends: continue
                    seen.add(new_state)
                    queue.append(new_state)
            k += 1
            
        return -1

1319. Number of Operations to Make Network Connected

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1: return -1
        n_components = 0
        
        adj_list = defaultdict(set)
        for p1, p2 in connections:
            adj_list[p1].add(p2)
            adj_list[p2].add(p1)
        
        visited = set()
        for p in range(n):
            if p in visited: continue
            n_components += 1

            stack = [p]
            while stack:
                pc = stack.pop()
                if pc in visited: continue
                visited.add(pc)
                stack.extend(adj_list[pc])
        
        return n_components - 1

1192. Critical Connections in a Network

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        # graph processing from edge lists to adjacency lists
        adj_lists = defaultdict(set)
        for n1, n2 in connections:
            adj_lists[n1].add(n2)
            adj_lists[n2].add(n1)
            
        connections = set(tuple(sorted(edge)) for edge in connections)
        rank = dict()

        def dfs(node, depth):
            if node in rank: return rank[node]
            
            rank[node] = depth
            min_back_depth = n
            for neighbor in adj_lists[node]:
                if rank.get(neighbor, None) == depth - 1: continue
                    
                back_depth = dfs(neighbor, depth + 1)
                if back_depth <= depth:
                    connections.discard(tuple(sorted((node, neighbor))))
                min_back_depth = min(min_back_depth, back_depth)
            return min_back_depth
            
        dfs(0, 0) 
        return list(connections)

51. N-Queens

class Solution:
    def solveNQueens(self, n):
        rows = ["." * c + "Q" + "." * (n - c - 1) for c in range(n)]
        queens = [None] * n
        columns = [0] * n
        main_diag, off_diag = [0] * (2 * n), [0] * (2 * n)
        
        def add_queen(r, c):
            queens[r] = c
            main_diag[r + c] = 1
            off_diag[r - c + n] = 1
            columns[c] = 1
            
        def remove_queen(r, c):
            queens[r] = None
            main_diag[r + c] = 0
            off_diag[r - c + n] = 0
            columns[c] = 0
        
        def valid(r, c):
            if columns[c]: return False
            if main_diag[r + c]: return False
            if off_diag[r - c + n]: return False
            return True
        
        def form_board(queens):
            board = [rows[c] for c in queens]
            return board.copy()

        def backtrack(queens, r):
            if r == n: return solution.append(form_board(queens))
            for c in range(n):
                if not valid(r, c): continue
                add_queen(r, c)
                backtrack(queens, r + 1)
                remove_queen(r, c)                

        solution = []            
        backtrack(queens, 0)
        return solution

37. Sudoku Solver

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        nrow, ncol = len(board), len(board[0])
        digits = set('123456789')
        not_visited = [(r, c) for r in range(9) for c in range(9) if board[r][c] == '.']

        def valid_choices(r, c):
            row = board[r]
            col = [board[i][c] for i in range(9)]
            square = [board[i][j] for i in range(r // 3 * 3, r // 3 * 3 + 3)
                                  for j in range(c // 3 * 3, c // 3 * 3 + 3)]
            choices = digits.difference(row).difference(col).difference(square)
            return choices

        def backtrack(board, not_visited):
            if not not_visited: return True
            (r, c) = not_visited.pop()
            for digit in valid_choices(r, c):
                board[r][c] = digit
                if backtrack(board, not_visited): return True
                board[r][c] = '.'
            not_visited.append((r, c))
            return False

        backtrack(board, not_visited)

10. Regular Expression Matching

  • DP
  • Hard
  • O(MN)

DP[i,j] isMatch s[i:-1] and p[j:-1]

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dp(i, j):
            if j == len(p): return i == len(s)
            single_char_match = i < len(s) and p[j] in [s[i], '.']
            if j + 1 < len(p) and p[j + 1] == '*':  
                return dp(i, j + 2) or (single_char_match and dp(i + 1, j))
            return single_char_match and dp(i + 1, j + 1)
        return dp(0, 0)

    def isMatch(self, s, p):
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
        dp[-1][-1] = True
        for i in reversed(range(len(s) + 1)):
            for j in reversed(range(len(p))):
                single_char_match = i < len(s) and p[j] in [s[i], '.']
                if j + 1 < len(p) and p[j + 1] == '*':
                    dp[i][j] = dp[i][j+2] or (single_char_match and dp[i + 1][j])
                else:
                    dp[i][j] = single_char_match and dp[i+1][j+1]
        return dp[0][0]

241. Different Ways to Add Parentheses

  • Recurrsion
  • Medium
  • O(2^N)
class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        nums, ops = [], []
        num = 0
        for c in expression:
            if c.isdigit(): num = 10 * num + int(c)
            else:
                ops.append(c)
                nums.append(num)
                num = 0
        nums.append(num)
        
        @cache
        def calculate(l, r):
            if l == r:  return [nums[l]]

            result = []
            for k in range(l, r):
                result.extend([
                    eval(f"l_val {ops[k]} r_val")
                    for l_val, r_val in product(
                        calculate(l, k),
                        calculate(k + 1, r)                                            
                    )
                ])
            return result
        
        total = calculate(0, len(nums) - 1)
        return total

309. Best Time to Buy and Sell Stock with Cooldown

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        hold, sold, rest = -prices[0], 0, 0
        for price in prices:
            hold, sold, rest = max(hold, rest - price), hold + price, max(rest, sold)
        return max(hold, sold, rest)

714. Best Time to Buy and Sell Stock with Transaction Fee

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        sold, hold = 0, -prices[0]
        for price in prices[1:]:
            sold, hold = max(sold, hold + price - fee), max(hold, sold - price)
        return sold

1136. Parallel Courses

class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        taken = set()
        edge_list = defaultdict(set)
        n_prereqs = defaultdict(int)
        
        for pre, seq in relations:
            edge_list[pre].add(seq)
            n_prereqs[seq] += 1
        
        curr_semester = set(range(1, n + 1)) - set([seq for pre, seq in relations])
        if not curr_semester: return -1
        
        semester = 0
        while curr_semester:
            semester += 1
            next_semester = set()
            
            for course in curr_semester:
                if course in taken: return -1
                for seq in edge_list[course]:
                    n_prereqs[seq] -= 1
                    if n_prereqs[seq] == 0:
                        next_semester.add(seq)
            taken.update(curr_semester)
            curr_semester = next_semester
        return semester if len(taken) == n else -1

1396. Design Underground System

class UndergroundSystem:
    def __init__(self):
        self.ids = set()
        self.memo = dict()
        self.avg_time = dict()

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        if id in self.ids: return
        self.ids.add(id)
        self.memo[id] = (stationName, t)
        
    def checkOut(self, id: int, stationName: str, t: int) -> None:
        if id not in self.ids: return
        self.ids.remove(id)
        
        start_station, start_time = self.memo[id]
        self.memo.pop(id)
        end_station, end_time = stationName, t
        
        route = (start_station, end_station)
        delta_t = end_time - start_time
        
        average_time, count = self.avg_time.get(route, (0, 0))
        self.avg_time[route] = ((average_time * count + delta_t) / (count + 1), count + 1)

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        return self.avg_time[(startStation, endStation)][0]