Classic Questions Summary

Posted on Edited on In ,

There are several classic questions that include data structure and algorithm.

Data Structure choices for questions

  • Use heap(s) when needs to find min/max/median value, top K
  • Use set, map for O(1) time requirement
  • Use {key: prev_node} to store linked list node
  • Consider 2 pointers for subarray, substring
  • DP related
    • Consider DP for subsequence
    • Use 1-d DP for a list, set the dp[i] including to the i-th element
    • Use 2-d DP for 2 lists, array
  • Tree
    • Consider recursion
    • If the results need to be checked at each node, or in leaf nodes, use an extra class field along with the return value
  • Consider binary search for log(n) case
  • BFS: shortest questions, whether existed questions, all solutions with a non-recursion method
  • DFS: all solutions, can use memo to decrease time
  • DP: max/min, whether valid, sum number of all solutions

Buy and Sell Stock

Transactions(buy and sell) at most k times in N days, and get the max profit.
Tag: DP, Divide Conditions

  • Simplify to a Greedy question when 2 * k >= N
  • Use 2-dimensional dp to solve the problem. dp[i][j] means the max profit gained in 0 to i day under at most k transactions
  • Find the recursive formula by classifying the conditions. When considering the i day
    • i day cannot buy stock(absolutely)
    • i day don’t sell stock. So i-1 day don’t buy stock, so profit[i][j] = profit[i - 1][j]
    • i day sell stock. So m (m<i) buy the stock, so profit[i][j] = price[i] - price[m] + profit[m][j - 1]
  • Find the simplified methods to reduce time complexity from O(n^2 * k) to O(nk)
    • price[i] - price[m] + profit[m][j - 1] = profit[m][j - 1] - price[m] + price[i] , and price[i] for each i is constant, so just need to consider profit[m][j - 1] - price[m] (m<i). More steps, just consider the maximum of this term.
  • Determine the iteration order. Iterate j and then iterate i.

Samples

  • No. 121 - Buy and sell once

    • Record the low price, update profit at each day
    • profit = max(profit, price - low_price)

  • No. 122 - Buy and sell multi-times

    • Greedy - As long as the current price larger than previous price, do the transactions
    • profit += prices[i] - prices[i - 1]

  • No. 123 - Buy and sell two times

    • Split in the ith day. Divide into two buy and sell once problem
    1
    2
    3
    p1[i] = max(p1[i-1], price - low_price)
    p2[j] = max(p2[j+1], max_price - price)
    profit = max(profit, p1[p], p2[p])

  • No. 188 - Buy and sell at most k times

    • If 2k>=n, it is same with the No. 122
    • Use DP, see comments below
    • Video and Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    def maxProfit(self, k: int, prices: List[int]) -> int:
        def no_limit(k: int, prices: List[int]) -> int:
                profit = 0
                for i in range(1, len(prices)):
                    if prices[i] - prices[i - 1] > 0:
                        profit += prices[i] - prices[i - 1]
                return profit
        if 2 * k >= n:
            return no_limit(k, prices)

        # profit[i][j] means the profit gained in first i days at most k transactions
        # prices[i] means the ith day (i = 0, 1, 2, ..., n - 1)
        # profit[i][j] = max(profit[i - 1][j], if day i doesn't buy and doesn't sell stock; profit[m][j - 1] + price[i] - prices[m], (m < i), if day i sell stock, that some day before i need buy stock)
        # profit[i][j] = max(profit[i - 1][j], prices[i] + max(profit[m][j - 1] - prices[m])) (m <= i)

        pre_profit = [0 for _ in range(n)]
        profit     = [0 for _ in range(n)]

        for j in range(1, k + 1):
            max_diff   = 0 - prices[0]
            pre_profit = profit.copy()
            for i in range(1, n):
                profit[i] = max(profit[i - 1], 
                                prices[i] + max_diff)
                max_diff = max(max_diff, 
                               pre_profit[i] - prices[i])
        return profit[-1]

  • No. 309 - Buy and sell with 1 day Cooldown

    • Use dp, similar method to divide the conditions
    • profit[i] = profit[i - 1] if day i won’t sell stocks
    • profit[i] = price[i] - price[m] + profit[m - 2] if day i sell stocks
    • Similar methods to simplify the question

Scanning Line

Scanning Line for Geometric Questions

  • No. 218 - The Skyline Problem
    • Divide Conditions
    • Each edge can be categorized into rising edge or falling edge
      • If it is a rising edge, add it to answer if it is the most top edge so far. Add it to heap
      • If it is a falling edge, add the second high edge to answer if it is the most top edge(remove it from heap, check its height with current most top height in heap, if it larger than the height in heap, put the height in heap to answer)

Topological Order (Important Path)

  • No. 207, 210 - Course Schedule I II
    • Topological sorting is a powerful way to solve the problem of arranging tasks based on dependency
    • Create a graph, and calculate the in degrees for each vertex

Search a pattern in a matrix

  • No. 79, 212 - Word Search I, II
    • Single word search $\Rightarrow$ DFS, Backtracking
    • Groups words search $\Rightarrow$ Trie Tree

Word Break

Break a string into several words from word dictionary

  • No. 139, 140 - Word Break I, II
    • Check availability $\Rightarrow$ Recursion with memo or DP
    • Return answers $\Rightarrow$ Recursion with memo

Word Ladder

Shortest path changing from one word to another word

  • No. 127, 126 - Word Ladder I, II
    • Check steps $\Rightarrow$ BFS, Generate states myself
    • Return answers $\Rightarrow$ BFS get the distance, DFS find the answer according to the distance

Word Pattern

  • No. 291 - Word Pattern II
    • Backtracking

Sudoku

  • No. 36, 37 - Sudoku Valid, Solver
    • Valid $\Rightarrow$ Check
    • Solver $\Rightarrow$ Backtracking

The Maze

  • No. 490, 505, 499 - The Maze I, II, III
    • Valid $\Rightarrow$ BFS
    • Shortest Path Length $\Rightarrow$ BFS, No closed list but have a distance matrix
    • Shortest Path Answer $\Rightarrow$ BFS + DFS, Have closed list and a distance matrix

Find bridge in a graph

Tarjan Algorithm

  • No. 1192 - Critical Connections in a Network
    • There is a edge of (u, v), if low(v) > low(u), that means v cannot go back to u or previous node, so this is a critical edge

Subsets

  • No. 78, 90 - Subsets I, II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
nums.sort()
dfs(0, [])

def dfs(index, prev):
    self.ans.append(prev.copy())

    for i in range(index, len(nums)):
        # deal with duplicate elements
        if i > index and nums[i] == nums[i - 1]:
            continue

        # get cases with nums[i] inside the result
        prev.append(nums[i])
        dfs(i + 1, prev)

        # get cases without nums[i] inside the result
        prev.pop()

Permutation

No. 47 - Permutation II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
dfs(set(), [], [])

def dfs(visited, prev, result):
    if len(prev) == len(nums):
        result.append(prev.copy())
        return

    for i in range(len(nums)):
        if i in visited:
            continue

        # deal with duplicate elements
        if i > 0 and nums[i] == nums[i - 1] and i - 1 not in visited:
            continue

        # get cases put nums[i] in current pos
        prev.append(nums[i])
        visited.add(i)
        dfs(visited, prev)

        # get cases put other nums in current pos
        prev.pop()
        visited.remove(i)

Find the Celebrity

Find the largest person j who don’t know following people, then only the person j could be the celebrity.

Bike Series TBD

  • Sort
  • DP

Prefix infix suffix expression

Regular Expression Matching TBD

DP

Find elements in a rotated array

Binary search, while left + 1 < right, always compared with the right values.

Serialize and Deserialize Binary Tree

Use BFS traversal for the binary tree.

Lowest Common Ancestor (LCA)

Closest elements

Find 1 closest element in sorted array

Binary search

Find k closest elements in sorted array

Binary search + 2 pointers

Find 1 closest element in BST

Binary search / in-order traversal

Find k closest elements in BST

In-order traversal, binary search, two pointers

Valid Palindrome III

Whether a valid palindrome with removing at most K elements. Get the longest palindrome substring, compare with total length - k.

Sort colors

3 Pointers