366. Find Leaves of Binary Tree

  • Tree
  • Medium
  • O(N)

Categorize nodes by height, post-order traversal as node’s height = max(children’s height) + 1.

1293. Shortest Path in a Grid with Obstacles Elimination

  • Graph Search
  • Hard
  • O(NK) -> O(NK*KlogK) (but empirically faster)

BFS brute force -> Improve with Priority Queue where priority is (distance + steps used). A*? Hash (r, c, k) to avoid duplicate.

1937. Maximum Number of Points with Cost

  • DP
  • Medium
  • O(N^3) brute force; O(N^2) if smart

f(i,j) is maximum score of (i, j), f(i+1, j) = max(f(i,j) + abs(k - j) for j ) + points(i+1,j). Instead of brute foce max of, use kadane from both directions.

843. Guess the Word

  • Random / Math
  • Hard
  • Does not apply

Random guess -> match guess with secret -> filter words have a different match with guess -> try again. Collect info to help filter?

68. Text Justification

  • Greedy / DP
  • Hard
  • O(N) or O(N^2)

Depends on how we define desired white space placement. If MS word Greedy. If LaTeX then DP. f(i) = min(f(k) + badness(i, k))

1146. Snapshot Array

  • Design / Binary Search
  • Medium
  • O(1) set O(logN) get

For each index keep a stack of (snap_id, val). For get, use binary search.

2007. Find Original Array From Doubled Array

  • Math / Sort
  • Medium
  • O(N)

From smallest to largest, 2x has two sources, original or doubled. How do we know how many are doubled? Count(X) on a caveat, when Count(x//2) = 0, or we work on this from smallest x to largest.

359. Logger Rate Limiter

  • Design / Hashmap
  • Medium
  • O(1) or O(Q)

Memory not concern: Hash messages to timestamps. Limited Queue memory size -> deque + set

833. Find And Replace in String

  • Sweep line / Two Pointers
  • Medium
  • O(N + KlogK)

Sweep line process replacements from left to right.

1048. Longest String Chain

  • DP
  • Medium
  • O(log(N) + L^2)

Sort words by length. Hash word to its chain length where length is max(chain_length up to this one) + 1 or 1 if no chain.

1610. Maximum Number of Visible Points

  • Geometry / Sliding Window
  • Hard
  • O(NlogN)

Sort by degree angle. Stand on the point and rotate the view counterclockwise. To hangle wrap, copy points and add 360 and append to tail.

792. Number of Matching Subsequences

  • Greedy / HashMap
  • Medium
  • O(N+MK)

Hash first character to next_iterator. Go over S, pop matching iterators, get next, and hash back.

690. Employee Importance

  • Tree
  • Medium
  • O(N)

Traverse the tree, add up node property values.

552. Student Attendance Record II

  • DP / State Machine
  • Hard
  • O(logN*M^3)

DP or state machine -> matrix power vector of init state * (state_trans_matrix) ^ N

954. Array of Doubled Pairs

  • Math
  • Medium
  • O(N + K)

Count -> Sort keys by abs value. Go over sorted keys, if double has 0 occurrences found a violation, otherwise, decrement the count for double.

2034. Stock Price Fluctuation

  • Sorted Containers (AVL Tree)
  • Medium
  • O(logK) for all ops

time -> price for current price lookup: sorted by key - time; price -> timestamps for min max price lookup: sorted by key - price

1277. Count Square Submatrices with All Ones

  • DP
  • Medium
  • O(N^2)

f(i, j) is length of desired matrics with bottom right at i,j. Original problem is sum(f(i,j) for i for j). f(i, j) = min(f[i-1,j], f(i, j-1), f(i-1,j-1)) + 1 or 0.

2013. Detect Squares

  • Hash Map / Math
  • Medium
  • O(N^2)

Hash point to counts. Given p1, iterate over p3, let p1, p3 form the diag, check counts for p2, p4. Do math.

384. Shuffle an Array

  • Math
  • Medium
  • O(N)

Iterate over i in range(n), random sample i <= j < n, swap A[i], A[j].

1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

  • Backtracking
  • Hard
  • O((MN)^2)

Not sure a better solution exists? Brute force backtracking is accepted in OJ.

418. Sentence Screen Fitting

  • Greedy / Memoization
  • Medium
  • O(N)

Greedy fill row by row. May cache on (start_word_idx) -> [end_idx, n_rounds] to speed up next time when a row starts with the same index.

1834. Single-Threaded CPU

  • Priority Queue / Sweep line
  • Medium
  • O(N*logQ)

Follow the timeline. Adding tasks if start_time <= current time to priority queue with priority (processing_time, start_time).

631. Design Excel Sum Formula

  • Design?
  • Hard
  • O(MN)

Code the static version with is straight forward just tedious. Is it actually about this?

727. Minimum Window Subsequence

  • Two Pointers
  • Hard
  • O(MN)

Start from o rfind(next) till end mark r. From r lfind(prev) until start mark l. keep track of min(r-l+1). Move to l+1 and start again.

1877. Minimize Maximum Pair Sum in Array

  • Sort + Greedy
  • Medium
  • O(NlogN + N)

Sort then two pinter finding max. proof four numbers. al <= ai <= aj <= ar max(al+ar, ai+aj) is always <= max(al+ai, aj+ar).

652. Find Duplicate Subtrees

  • Hash Map / Tree
  • Medium
  • O(N^2) Time and Space.

Hash subtree to list of subtree roots. Optimize how to hash subtree?

1218. Longest Arithmetic Subsequence of Given Difference

  • DP
  • Medium
  • O(N)

1D DP O(N^2) f(i) = f(arr.index(arr[i] - diff)) + 1 or 1 -> kadane f(d) = f(d-diff) + 1 or 1

735. Asteroid Collision

  • Stack / Sweep line
  • Medium
  • O(N)

Encounter a positive one append; Encounter a negative one -> handle collision if needed, pop/append per result.

410. Split Array Largest Sum

  • Greedy / Binary Search
  • Hard
  • O(NlogS)

Can verify a guess in O(N) time. Apply binary search to find the max.

664. Strange Printer

  • DP
  • Hard
  • O(N^2)

f(i,j) = # ops to cover [i to j), solution to original problem is f(i, n). relation f(i,j) = min(f(i+1,j) +1, f(i+1, k) + f(k+1, j) for k between i and j)

302. Smallest Rectangle Enclosing Black Pixels

  • DFS/BFS / Binary Search
  • Hard
  • O(MN) or O(MlogN + NlogM)

DFS to find min_r, max_r, min_c, max_c; or binary search twice on [1 in row[i]] which evals to FFFTTTFFF to find min and max. Do the same on columns.

777. Swap Adjacent in LR String

  • Two Pointers
  • Medium
  • O(N)

R can only go right and can not cross other R or L. L can only go left and can not cross other R or L.

981. Time Based Key-Value Store

  • Design / Binary Search
  • Medium
  • O(logN)

Map key to SortedDict with time be key. So query can be done by binary search on key-time.

940. Distinct Subsequences II

  • DP
  • Hard
  • O(N)

Very tricky relation: f(i) = 2 * f(i-1) - f(last_loc(char_at(i))

1397. Find All Good Strings

  • String / KMP
  • Hard
  • O(N)

Treat evil as pattern, dp(i, j, lower, upper) = number of good string at string[i] matched at pattern[j] where currently we can choose lower to upper. dp(i, j, lower, upper) = sum( dp(i + 1, j’, lower’, upper’) for all k ~ (lower, upper, s1, s2, i))` Each i, we have choices depends on s1[i], s2[i] lower, upper, once we made a choice k, we find j’ by matching k with evil[j].

1776. Car Fleet II

  • Monotonic Stack
  • Hard
  • O(N)

Given a car, it will only see the car on its right. Only the slowest car matters. Keep a monotonic stack of cars decreasing in speed. E -> A -> B -> C if A is slower than B, from E’s perspective, A is all that matters. if A crashes B before E can catch up with A. Then from E’s perspective, A is equivalent to B.

1987. Number of Unique Good Subsequences

  • DP
  • Hard
  • O(N)

Leave 0 to the last. expansion f(i, k) be # of good subsequences end at i with value k. f(i, k) = sum(f(i-1, k) + b[i] for all k) very tricky

150. Evaluate Reverse Polish Notation

  • Stack
  • Medium
  • O(N)

Put number on stack, when encounter operator, pop two numbers out and carry out operation, put result back on stack.

900. RLE Iterator

  • Design
  • Medium
  • O(N)

Use index and used to keep track of the RLE we are using and how many used. Avoid modifying encoding itself.

1691. Maximum Height by Stacking Cuboids

  • DP / Greedy
  • Hard
  • O(NlogN + N^2)

Proof we want all boxes to be the tallest side up. Use contracdiction. Then sort and DP up. dp[i] = max(dp[j] +boxes[j].height for all j if j fit)

465. Optimal Account Balancing

  • DFS
  • Hard
  • O(N2^N)

Start with everyone’s end balance. Try to cancel the debt in one trans, if we can’t, then give money from pos to neg and keep going.

  • Trie
  • Hard
  • O(NK^2 + QK)

Build prefix and suffix Trie. Test intersection. Or build trie with suffix[:i]#prefix for all i for each word. Check suffix#prefix at run time.

489. Robot Room Cleaner

  • DFS
  • Hard
  • O(MN)

Detail on how to manage direction. Backtrack without changing direction by rotating backward then rotating back. Try all four directions by RRRR or LLLL.

871. Minimum Number of Refueling Stops

  • Priority Queue / Greedy
  • Hard
  • O(NlogN)

Use priority to keep track of past gas stations, where the priority is higher capacity(thus we fill up as few times as possible). Follow the stations, whenever we find ran out of fuel, go back to priority queue to see if we filled up before can we get here. If not we fail, otherwise add new station to queue and move forward.

299. Bulls and Cows

  • Array
  • Medium
  • O(N)

Two pass: count bull, when not bull count freq for each digit in secret and guess separately. Cows = sum(min_count(s.count(c), g.count(c)) for all c) One pass: count bull the same way. Keep a balance, secret + guess -. When guessed more than secret + 1

388. Longest Absolute File Path

  • Stack
  • Medium
  • O(N)

Use stack to keep track of section length, len(stack) is the number of levels for the current path. the level can also be determined by count(“/t”) if not agree, pop.

528. Random Pick with Weight

  • Math / Binary Search
  • Medium
  • O(N) init O(logN) search

Calculate CDF, do binary search on it.

1423. Maximum Points You Can Obtain from Cards

  • Sliding Window
  • Medium
  • O(N)

Slide a circular window to cover all cases between the two extremes, all left and all right.

1499. Max Value of Equation

  • Sliding Window / Deque
  • Hard
  • O(N)

Note i <= j, equation evaluates to yj + xj + yi - xi => problem is finding max(yi - xi) in window of length k(with at least 2 points). Maintain a monotonic increasing deque. With elements of tuple(yi - xi, xi) popleft as window moves right.

853. Car Fleet

  • Sort
  • Medium
  • O(NlogN)

sort cars by starting position. calculate the arrival times for each car as if no other car. Iterate the arrival time backward. Each peak is a leader in a fleet.

1032. Stream of Characters

  • Trie
  • Hard
  • O(K) query

Make a Trie of reversed words. Keep append characters to stream, check reverse of stream with the Trie.

269. Alien Dictionary

  • Topological Sort
  • Hard
  • O(VE)

Build graph. DFS (with cycle detection) collect postorder. Or BFS en queue when in_degree decreased to 0.

305. Number of Islands II

  • Union Find
  • Hard
  • O(MN)

Dynamic connectivity -> Union Find.

818. Race Car

  • DP / Bit Manipulation
  • Hard
  • O(NlogN)

Think of fulfilling the bits in the binary representation of t. Either overshot and do the complement. Or clear the second most significant bits. T = 1101 if overshoot we do 1111 and reverse do the complement 10 if clear most significant bit we can do 111 or 110 or 100 with 3 4 5 steps.

1368. Minimum Cost to Make at Least One Valid Path in a Grid

  • Deque / BFS / DFS
  • Hard
  • O(MN)

0-1 BFS with relaxation. Initialize costs for all loc as INF. Use a deque, vising nodes’ neighbors. updating the cost to visit for neighbor locations. if cost not increasing, put (cost, nr, nc) to left to continue touring, otherwise put (cost + 1, nr, nc) to right.

394. Decode String

  • Stack
  • Medium
  • O(N)

Keep track of string and rep, when encounter ‘[’ put both on stack, when encounter ‘]’ pop string and rep update string with string = prev + curr * rep.

447. Number of Boomerangs

  • HashMap
  • Medium
  • O(N^2)

Iterate over node as I. Inner loop iterate over all other nodes, count number of nodes per distance to i. Aggregate to total.

660. Remove 9

  • Math
  • Hard
  • O(N)

The number is nth number as if base 9. Remove a single digit will be basically the same, just need to map digits. For example if we remove 7, we treat it as if it is remove 9, in the result, just turn 7 into 8, 8 into 9.

803. Bricks Falling When Hit

  • Union Find
  • Hard
  • O(MN)

Reverse the order and do union-find. Use a sink/hook for the ceiling.

659. Split Array into Consecutive Subsequences

  • Greedy
  • Medium
  • O(N)

Keep track of sequnces by ending number and length. Greedy extending sequences as we see new number. Always add number to shortest sequence ending with number - 1. In the end there should be no length 1 or 2 sequence.

1680. Concatenation of Consecutive Binary Numbers

  • Bit
  • Medium
  • O(N)
Iterate over n, accum = (accum « n.bit_lengt() n) % m.

990. Satisfiability of Equality Equations

  • Union Find
  • Medium
  • O(N)

Create connected components with equality. Then check all the inequality for violation.

834. Sum of Distances in Tree

  • Tree / DFS
  • Hard
  • O(N)

If we pick a node as root. f(node) = sum of distances in tree rooted at node. s(node) = number of nodes in tree rooted at node. s(node) = sum(s(child)) + 1 f(node) = sum(f(child) + s(child)) Can solve for this selected root in O(N) time. If we apply this repeatedly will be O(N^2) time. Instead try figure out relationship to reuse the calculated quantities.

Consider node a and node a’s parent p(a). If we figured out f(p(a)). Can we calculate f(a)?

f(a) = f(p(a)) - s(a)  + (n - s(a))
                  ^           ^
                  |           |           
                  |           for the nodes not in a's subtree but in p(a)'s subtree, 
                  |           a is 1 distance greater than p(a) to them
                  for nodes in a's subtree, a is 1 distance closer to them than p(a) 

Thus two dfs, first time to get s(x) and f(0). Then from f(0) dfs to figure out all f(x)

837. New 21 Game

  • DP / Math / Sliding Window
  • Medium
  • O(N)

Pr(i) probability see total of i points during all sequences: Pr(1) = 1/w, Pr(2) = 1 / w(draw a 2) + Pr(1) * 1 / w (from a 1 draw then draw another 1)
Generally: Pr(i) = 1 / w * Sum { Pr(j) for j in range(max(0, i-w), min(i, k)) } use a sliding window for this sum.

407. Trapping Rain Water II

  • Union Find
  • Hard
  • O(MN)

Keep track of area of sroundeded low grounds through time. Iterate over time, update area and accumulate. Use Union Find to keep track of connected components, each corresponds to a srounded low grounds. Use a sink point for anything touching the boundry. Total area of srounded low grounds = total size of connected components - size of sink.

1296. Divide Array in Sets of K Consecutive Numbers

  • Greedy / Sorted HashMap / Sort + HashMap
  • Medium
  • O(NlogN)

Count number -> frequency. Start with minimal, build consecutive of k. Repeat until violation or used up all numbers.

200. Number of Islands

  • DFS / BFS
  • Medium
  • O(MN)

Count the number of connected components.

562. Longest Line of Consecutive One in Matrix

  • DP
  • Medium
  • O(MN)

dp[r][c] is tuple (h, v, md, od) that is length of consecutive ones from left, top, main diagonal, off diagonal.

593. Valid Square

  • Math
  • Medium
  • O(1)

Calculate pairwise distances. Square will only have two lengths, side or diagonal.

679. 24 Game

  • Permutation / Combination
  • Hard
  • O(N!)

GO through all permutation of 4 numbers, try all combinations of 3 operators, consider all 3 arrangements with 4 numbers and 3 operators, that is: op3(op2(op1(x, y), z), w) op3(w, op2(z, op1(x, y))) op3(op1(x, y), op2(z, w)) To check if we can get 24.

1618. Maximum Font to Fit a Sentence in a Screen

  • Binary
  • Medium
  • O(NlogF)

Given a font size, it take O(N) time to verify whether it is possible. Apply binary search on font sizes to figure out maximum.

1554. Strings Differ by One Character

  • Rabin Karp / HashMap
  • Medium
  • O(NM^2) worst case or O(MN) without collision

Rabin Karp hash all words h[i] = hash of word[i] = sum(26^j * word[i][j]) % m. Iterrate over positions j, create wildcard hash by (h[i] - word[i][j] * 26 ^ j) % m. check words with same hash to verify differ by one.

354. Russian Doll Envelopes

  • LIS
  • Hard
  • O(NlogN)

If we have distinct widths for envelopes, sort by widths, then problem reduced to LIS. With duplicated widths, if within the same widths, we sort by heights in reverse, it will still be a LIS problem. Thus sort by (w, -h) then LIS.

857. Minimum Cost to Hire K Workers

  • Greedy / Priority Queue
  • Hard
  • O(NlogN)

If we form a team, everyone will be paid at max(wage_i/quality_i for all i) within the team. Thus sort workers in increasing order of this ratio. Introduce worker to team means increasing ratio of the team. Be greedy and getting rid of worker with higest quality to see if it counters the rate increase and produce a lower overall team cost.

778. Swim in Rising Water

  • Union Find
  • Hard
  • O(N^2\alpha(N^2))

Iterate over cells sorting by time. Union find cell with neighboring cells that were already in set. Check if top left and bottom right is connected or not.

2092. Find All People With Secret

  • Graph
  • Hard
  • O(N^2)

Use a set to keep track of people who know the secret. Iterate over meetings grouped by time in time order. Make undirected graph, put people in the meeting that know the secret on to a queue. Go over the people on the queue, update the people linked to this one to the set and push on to queue. (DFS or BFS both are fine)

233. Number of Digit One

  • Math
  • Hard
  • O(N)

f(n) = number of digit one from number up to (10 ** n) inclusive. f(0) = 0, f(1) = 1, f(2) = 20, f(3) = 300, f(4) = 4000 etc f(i) = 10 * f(i-1) + 10 ** i 0 to 9 + all numbers of length(i-1) + add one to all numbers from 0 to 10 ** i - 1

232 -> enumerate over digits from least significant to most significant. If d and d == 1: total += f(i) + remainder + 1 (f(i) from add 1 to all numbers with length i - 1) If d and d > 1: total += f(i) * d + 10 ** i

1272. Remove Interval

  • Sweep Line
  • Medium
  • O(N)

Go through intervals, compare l with l’, if l < l’ take min(l’, r) as r. compare r with r’ if r > r’ take max(l, r’) as l.

284. Peeking Iterator

  • Design
  • Medium
  • O(1)

Cache next value. When called next or hasNext, check if cache exist or not first. When next, clear cache. In case the underlying iterator can return Null pointers, use a boolean flag to indicate whether we have cache.

835. Image Overlap

  • Sliding Window / HashMap
  • Medium
  • O(N^4)

Can count (x2-x1, y2-y1) if A[x1][y1] == B[x2][y2] == 1. i.e. the shifts that will cause a match. Or do sliding window convolution, which the code will be messy.

329. Longest Increasing Path in a Matrix

  • Topological Sort / BFS
  • Hard
  • O(MN)

Make directed graph where cell with lower value has out edge to neighboring cells with higher value. Start from cells with 0 in degree. Do BFS and decrease in_degrees of the cell moved to. Once a cell’s in degree decreased to 0, on queue the cell location. Count the depth for the BFS search tree.

2096. Step-By-Step Directions From a Binary Tree Node to Another

  • Tree / LCA / Postorder
  • Medium
  • O(N)

Traverse the tree postorder to find LCA and two nodes, build parent pointers. Form paths, from startNode up to LCA and from LCA down to distNode.

1096. Brace Expansion II

  • Stack
  • Hard
  • O(N!?)

Push { , and set(char) on to stack. Whenever encounter }, means we need to evaluate the operations. If stack[-2] is , we should set union stack[-1] and stack[-3] and replace all three with a single element the union. Finally replace the { by the last union Whenever the last two elements on stack are sets, we need to do cartesian product.

539. Minimum Time Difference

  • Sort / Circular Array
  • Medium
  • O(NlogN)

Conver all time to minutes since midnight then sort, add time_0 + 24 * 60 to the end, so that the min difference with time wrap can be evaluated. Compare adjacent time points and record the minimum difference.

772. Basic Calculator III

  • Stack
  • Hard
  • O(N)

Extension of 227 with parenthese. When encounter (, put it on stack and reset operand and operator. When encounter ), evaluate what is on the stack util (.

class Solution:
    def calculate(self, s: str) -> int:
        def operation():
            if operator == '+': stack.append(operand)
            if operator == '-': stack.append(-operand)
            if operator == '*': stack.append(stack.pop() * operand)
            if operator == '/': stack.append(int(stack.pop() / operand))
        
        stack = []
        operand, operator = 0, '+'
        for c in s:
            if c.isdigit():
                operand = operand * 10 + int(c)
            if c == '(':
                stack.append(operator)
                operand, operator = 0, '+'
            if c in '+-*/)':
                operation()
                if c == ')':
                    operand = 0
                    while isinstance(stack[-1], int):
                        operand += stack.pop() 
                    operator = stack.pop()
                    operation()
                operand, operator = 0, c
                
        operation()
        return sum(stack)

1240. Tiling a Rectangle with the Fewest Squares

  • Backtracking
  • Hard
  • O(MN*N^M) where we sort N, M such that M < N
  1. Key: fill the rectangle with squares bottom up. thus we can use 1D array to represent the state.
    • i.e. [2,2,4,4,4,4,1] means bottom left is a 2 x 2 square, on its right is a 4 x 4 and then a 1 x 1 on the right.
    • i.e. [2,2,4,7,7,7,1] means bottom left is a 2 x 2 square, on its right is a 4 x 4, but on the top of the 4 x 4 shifted to right by 1, there is a 3 x 3 square. And finally a 1 x 1 on the bottom right.
  2. Do backtrack
class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        if n > m: return self.tilingRectangle(m, n)
        self.total = n * m

        h = [0] * n
        
        def backtrack(curr):
            if curr >= self.total: return 
            
            min_height = min(h)
            if min_height == m: self.total = curr; return
            
            l = r = h.index(min_height)
            while r < n and h[r] == h[l] and (r - l + 1 + min_height) <= m: r += 1

            for j in range(r-1, l-1, -1):
                for k in range(l, j+1): h[k] += j - l + 1
                backtrack(curr + 1)
                for k in range(l, j+1): h[k] -= j - l + 1
        
        backtrack(0)
        return self.total

158. Read N Characters Given read4 II - Call Multiple Times

  • Design
  • Hard
  • O(N)

Use two integers indicated the number of chars read in buff and the index of the char to read in buff. For read, while haven’t read all, if buff is not exausted use it, otherwise fetch more on to buff reset the two integers. If fetch nothing or read enough don.

1592. Rearrange Spaces Between Words

  • Array
  • Easy / Hard
  • O(N)

Regular spaces and trailing spaces are divmod(# total spaces, # words - 1). Split and reform is Easy. If given char array and asking inplace swaps, we shift all words to one side leave 1 space in between, and then work from opposite side shift words with proper spaces.

class Solution:
    def reorderSpaces(self, text: str) -> str:
        num_spaces = text.count(" ")
        words = text.split()
        num_words = len(words)
        if num_words == 1: return words[0] + " " * num_spaces
        
        space, trailing = divmod(num_spaces, num_words - 1)
        result = []
        for word in words:
            result.append(word)
            result.append(" " * space)
        result[-1] = " " * trailing
        return "".join(result)


def l_shift(A, l, s, e):
    """shift A[s:e] to A[l:l + e-s]"""
    stride = e - s
    i, j = l, s
    while j < e:
        A[i], A[j] = A[j], A[i]
        i += 1 ; j += 1
    return l + stride + 1, e + 1

def r_shift(A, r, s, e):
    """shift A[s:e] to A[r-e-s:r]"""
    stride = e - s
    i, j = r, e
    while j > s:
        A[i], A[j] = A[j], A[i]
        j -= 1 ; i -= 1
    return r - stride, s

class Solution:
    def reorderSpaces(self, text: str) -> str:
        A = list(text)
        n = len(A)

        # shift words to left, leave one space in between count number of spaces
        l = s = 0
        num_words = 0
        while s < n:
            if A[s] == " ": s += 1; continue
            num_words += 1
            e = s
            while e <n and A[e] != ' ': e += 1
            l, s = l_shift(A, l, s, e)
        
        if num_words == 1: return "".join(A)
        num_spaces = A.count(" ")
        space, trailing = divmod(num_spaces, num_words - 1)
        
        # work from back ward
        r = n - 1 - trailing
        e = n - 1
        while e > 0:
            if A[e] == " ": e -= 1; continue
            s = e
            while s >=0 and A[s] != ' ': s -= 1
            r, e = r_shift(A, r, s, e)
            r -= space
        return "".join(A)

1255. Maximum Score Words Formed by Letters

  • Backtrack
  • Hard
  • O(2^N)

TODO: use counter instead of the state array?

class State:
    def __init__(self, scores, seq=None):
        self.state = [0] * len(scores)
        self.scores = scores
        self.score = 0
        if seq:
            for c in seq: 
                i = ord(c) - ord('a')
                self.state[i] += 1
                self.score += self.scores[i]
        
    def __iadd__(self, other):
        for i in range(len(self.state)):
            self.state[i] += other.state[i]
        self.score += other.score
        return self
            
    def __isub__(self, other):
        for i in range(len(self.state)):
            self.state[i] -= other.state[i]
        self.score -= other.score
        return self
    
    def __le__(self, other):
        return all(self.state[i] <= other.state[i] for i in range(len(self.state)))
    

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], scores: List[int]) -> int:
        word_to_state = {word: State(scores, word) for word in words}
        full_state = State(scores, letters)
        null_state = State(scores)
        
        self.max_score = 0
        
        def backtrack(state, i):
            if not state <= full_state: return
            self.max_score = max(self.max_score, state.score)        
            for j, word in enumerate(words[i:], i+1):
                state += word_to_state[word]
                backtrack(state, j)
                state -= word_to_state[word]
                    
        backtrack(null_state, 0)
        return self.max_score

2030. Smallest K-Length Subsequence With Occurrences of a Letter

  • Monotonic Stack / Greedy
  • Hard
  • O(N)

Scan from left to right, notice whenever we encounter a lexicographically smallest character, as long as we are sure there are enough letter to the right to fullfill the required repetition and we have enough letter to fullfill the window size. It is better off to ignore all the stuff so far and start from this one. This is also true for second / third and in general any subsequent postition. After one pass to fill this stack, go through the stack a second time to find the window. Grab characters as we see them, stop when we only had space for the required letter.

[1642]

417. Pacific Atlantic Water Flow

  • BFS / DFS
  • Medium
  • O(MN)

Find reachable locations from two oceans seperately. Find the intersection among the two sets.

class Solution:
    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
        nrow, ncol = len(matrix), len(matrix[0])

        def dfs(stack):
            reachable = set()
            while stack:
                node = stack.pop()
                r, c = node
                reachable.add(node)
                for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
                    if (nr, nc) in reachable: continue
                    if 0 <= nr < nrow and 0 <= nc < ncol and matrix[nr][nc] >= matrix[r][c]: 
                        stack.append((nr, nc))
            return reachable

        p_reachable = dfs(
            [(r, 0) for r in range(nrow)] + 
            [(0, c) for c in range(ncol)]
        )
        a_reachable = dfs(
            [(r, ncol - 1) for r in range(nrow)] + 
            [(nrow - 1, c) for c in range(ncol)]
        )

        reachable = p_reachable.intersection(a_reachable)
        return reachable

[732]

[542]

[729]

[1254]

[715]

1509. Minimum Difference Between Largest and Smallest Value in Three Moves

  • Greedy
  • Medium
  • O(1)

Exam the extreme cases only. sort then take min of (a[~3] - a[0], a[~2] - a[1], a[~1] - a[2], a[~0] - a[3])

[920]

[1376]

[632]

[939]

[1166]

[794]

[1706]

[788]

[149]

[1138]

[380]

[846]

[850]

[801]

[1477]

[1]

[2018]

[1110]

[564]

[720]

[307]

[1263]

[1377]

[1102]

253. Meeting Rooms II

  • Priority Queue
  • Medium
  • O(NlogN)

Sort meetings by starting time. Push end time onto a min priority queue. Going through the rest of meetings, if priority is not empty and the top item(end time) is less than the starting time, that means a previous occupied room can be used, pop it off the priority queue and push on the new end time. The size of the priority queue is the max number of rooms needed. Follow up: to out put each room’s schedule. Push (endtime, roomid) on the queue, when we reuse room, use the same roomid, when we ran out of rooms, use size(queue) as new room’s id. Use a HashMap mapping room_id to its events.

[1066]

[1088]

[1531]

1231. Divide Chocolate

  • Binary Search
  • Hard
  • O(NlogN)

write a greedy function to verify if target sweetness can be achived. Binary search between 0 and average sweetness + 1. Find the largest value where the function is still true.

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def can_divide(amt):
            num_chunks, accum = 0, 0
            for num in sweetness:
                accum += num
                if accum >= amt:
                    num_chunks += 1
                    accum = 0
            return num_chunks >= k + 1
        
        lo, hi = 0, sum(sweetness) // (k + 1) + 1
        while lo < hi:
            mid = (lo + hi) >> 1
            if not can_divide(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo - 1

1345. Jump Game IV

  • BFS
  • Hard
  • O(N)

Save a mapping from number to list of positions with the number. Since we are looking at shortest path, apply BFS with element (pos, step) on the queue. When pos == last, return step. Otherwise, collect all jumpable positions if haven’t visited those yet(ie, if we jump there, it will be shortest path to jump over there), on queue (next_pos, step + 1).

[996]

[1553]

[1864]

[300]

[1230]

[403]

[62]

[1494]

[708]

[951]

[695]

[731]

[588]

2083. Substrings That Begin and End With the Same Letter

  • Count
  • Medium
  • O(N)

Each character, let it appears n times in the string, each pair contributes to 1 substring, thus, n * (n + 1) // 2 from this character. Aggregate over all unique characters.

[1275]

[4]

[1162]

[889]

[363]

[1888]

[1227]

[1091]

[317]

[1514]

[1882]

[10]

[1807]

[2115]

[549]

[721]

[85]

[1007]

[847]

[1153]

[222]

[787]

[1490]

[336]

[621]

[261]

[1855]

[37]

[642]

[1055]

[1406]

[1547]

[676]

[726]

[56]

[1624]

[34]

[1740]

[767]

[616]

[7]

[1631]

[894]

[560]

[433]

[400]

[710]

[316]

[886]

[315]

[91]

[360]

[1438]

[324]

[1024]

[298]

[919]

[1270]

[280]

[1325]

[505]

[353]

[1042]

[64]

[780]

[93]

1044. Longest Duplicate Substring

  • Rolling Hash / Binary Search
  • Hard
  • O(NlogN)
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        D = [ord(c) - ord('a') for c in S]
        P = 26
        MOD = 10 ** 9 + 7
        
        def rolling_hash(L):
            # initial window
            h = 0
            for c in D[:L]: h = (h * P + c) % MOD
            seen = defaultdict(list)
            seen[h].append(0)
            
            PP = P ** L % MOD
            # sliding window
            for r, c in enumerate(D[L:], L):
                l = r - L + 1
                # update hash
                #  shift left    emit the old left    adding the new right    
                h = (h * P    -   D[r - L] * PP     +   c) % MOD
                # collision detection
                if h in seen: 
                    if any(S[ll:ll+L] == S[l:l+L] for ll in seen[h]): return l
                seen[h].append(l)
            return False
        
        # use binary search to find the max length of duplicated windows
        l, h = 0, len(S)
        while l < h:
            m = (l + h) >> 1
            if rolling_hash(m) != False: 
                l = m + 1
            else: 
                h = m
        start = rolling_hash(l-1)
        return S[start: start + l - 1]

[1996]

[41]

2103. Rings and Rods

  • Bit
  • Easy
  • O(N)

Use bit mask to indicate color, use a integer indicating the state for each rod. Use or operatior to update state.

[161]

[130]

[759]

[71]

[399]

[525]

[236]

[218]

[773]

[809]

[174]

[852]

[582]

[210]

[362]

[1244]

[460]

[677]

[1525]

[719]

224. Basic Calculator

  • Stack
  • Hard
  • O(N)

Initialize operator to “+”, operand to 0, partial result to 0. Whenever encountering digit, update operand Whenever encountering +-, do partial = op(partial, operator, operand), reset operator and operand Whenever encountering (, put partial result and operator on to stack, and reset operator and partial Whenever encountering ), do operand = op(partial, operator, operand), then pop previous partial result and operator do partial = op(partial, operator, operand)

class BasicCalculatorI:
    def calculate(self, s: str) -> int:
        stack = []
        operator, partial, operand = "+", 0, 0
        
        def operation(a, o, b):
            if o == "+": return a + b
            if o == "-": return a - b
        
        for c in s:
            if c.isdigit():
                operand = operand * 10 + int(c)
            if c in '+-':
                partial = operation(partial, operator, operand)
                operator = c
                operand = 0
            if c == ")":
                operand = operation(partial, operator, operand)
                operator, partial = stack.pop()
                partial = operation(partial, operator, operand)
                operand = 0
            if c == '(':
                stack.append((operator, partial))
                operator, partial = "+", 0
        return operation(partial, operator, operand)

[437]

[1252]

[968]

[1770]

[334]

[1092]

239. Sliding Window Maximum

  • Sliding Window / Monotonic Deque
  • Hard
  • O(N)

Use a deque to keep track of the indices of strickly decreasing items in the window. Once a new element enter the window from the right, anything smaller than it becomes irrelavant to window maximum. Keep track of indices instead of actual value, thus we can check using i - k to see if leftmost element should be poped to matain window valid.

class Solution:
    def solution_pq(self, nums: List[int], k: int) -> List[int]:
        result, pq = [], []
        for r, num in enumerate(nums):
            heapq.heappush(pq, (-num, r))
            while pq and pq[0][1] <= r - k: heapq.heappop(pq)
            if r >= k - 1: result.append(-pq[0][0])
        return result
            
    
    def solution_mono_queue(self, nums: List[int], k: int) -> List[int]:
        result, dq = [], deque()
        for i, n in enumerate(nums):
            while deque and nums[dq[~0]] < n:  dq.pop()
            dq.append(i)
            if dq[0] == i - k:  dq.popleft()
            if i >= k - 1: result.append(nums[dq[0]])
        return result   

[1049]

[1136]

[313]

[983]

[1352]

[43]

1235. Maximum Profit in Job Scheduling

  • DP + Binary Search / Priority Queue
  • Hard
  • O(NlogN)

map distinct event end time to integer 1 to n. dp[i] is the maximum profit including event ended on i_to_time[i].

dp[i] = max(dp[j] + profit_of_event_i) where j is the indices in i_to_time such that i_to_time[j] is the largest time before this event ended on i started.

dp here is a monotonic stack, with key be profit! We can apply binary_search(dp, start_time)

INF = 2 ** 32 


class Solution:
    def solution_dp(self, startTime, endTime, profit):
        jobs = sorted([(e,s,p) for s, e, p in zip(startTime, endTime, profit)])
        dp = [[0, 0]]  # end time and max_profit 
        for e, s, p in jobs:            
            prev = bisect.bisect_right(dp, [s, INF]) - 1
            if dp[prev][1] + p > dp[-1][1]:
                dp.append([e, dp[prev][1] + p])
        return dp[-1][1]

    def solution_pq(self, startTime, endTime, profit):
        jobs = sorted([(s,e,p) for s, e, p in zip(startTime, endTime, profit)])
        pq = []
        max_profit = 0
        for s, e, p in jobs:
            while pq and s >= pq[0][0]:
                max_profit = max(max_profit, pq[0][1])
                heapq.heappop(pq)
            heapq.heappush(pq, (e, p + max_profit))
        return max([q[1] for q in pq], default=max_profit)

    jobScheduling = solution_dp

[1859]

[2]

[1641]

[856]

[18]

[1971]

[1101]

[368]

[877]

[23]

[947]

[1436]

[1730]

[17]

[29]

[349]

[205]

[337]

[909]

[662]

[246]

286. Walls and Gates

  • BFS / DFS
  • Medium
  • O(MN)

Instead find closest gate to each room, do the opposite, from gate visit and mark room.

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        INF = 2147483647
        nrow, ncol = len(rooms), len(rooms[0])
        queue = deque([[r, c, 0] for r in range(nrow) for c in range(ncol) if rooms[r][c] == 0])
        
        while queue:
            r, c, d = queue.popleft()
            for nr, nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):
                if not (0 <= nr < nrow and 0 <= nc < ncol and rooms[nr][nc] > d + 1): continue
                rooms[nr][nc] = d + 1
                queue.append((nr, nc, d + 1))

849. Maximize Distance to Closest Person

  • Two Pointers
  • Medium
  • O(N)

Find the maximum distance among(neightboring 1, left boundry and left most 1, right boundry and right most 1)

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        max_dist, last, n = 0, -1, len(seats)
        for curr, seat in enumerate(seats):
            if not seat: continue
            dist = curr if last < 0 else (curr - last) / 2
            max_dist = max(max_dist, dist)
            last = curr
        max_dist = max(max_dist, n - last - 1)
        return int(max_dist)

[345]

[259]

[127]

[173]

115. Distinct Subsequences

  • DP
  • Hard
  • O(MN)
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]
        dp[0] = [1] * (len(s) + 1)
        for i in range(1, len(t) + 1):
            for j in range(i, len(s) + 1):
                dp[i][j] = dp[i][j-1] + int(bool(t[i-1] == s[j-1])) * dp[i-1][j-1]
        return dp[-1][-1]

[416]

[207]

[934]

[128]

[1910]

[103]

[1636]

[295]

[66]

[1446]

[53]

[377]

[250]

[925]

[338]

[836]

[1472]

[25]

[278]

[124]

[692]

134. Gas Station

  • Greedy
  • Medium
  • O(N)

Iterate over the stations, keep track of fuels. If ever fuels go below 0, it means any station between start and current will not be a valid starting station. To tell if it is possible, check the overall gain > loss.

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total, tank, candidate = 0, 0, 0
        for i, (gain, loss) in enumerate(zip(gas, cost)):
            total += gain - loss
            tank += gain - loss
        
            if tank < 0: # reset
                tank = 0
                candidate = i + 1
        
        if total < 0: # not possible
            return -1
        return candidate 

[198]

[387]

[1335]

[57]

[532]

[815]

42. Trapping Rain Water

  • Two Pointers / Sweep Line
  • Hard
  • O(N)

Scan simutenausly form both side to the center, maintain a horizontal level, such that any pit below that level line will be fill. The level will be updated with level = max(level, min(h[l], h[r])), thus it never goes down, and only goes up if both side is at least that high, guarantee the above. Always move the shorter side towards center.

class Solution:
    def trap(self, heights: List[int]) -> int:        
        accum = level = 0
        l, r = 0, len(heights) - 1
        while l <= r :
            level = max(min(heights[l], heights[r]), level)    
            if heights[l] < heights[r]:
                accum += level - heights[l]
                l += 1
            else:
                accum += level - heights[r]
                r -= 1
        return accum

[658]

[241]

[77]

[543]

[965]

[221]

[260]

[79]

[135]

[673]

[684]

[1570]

[15]

[228]

[1650]

[733]

[459]

[78]

[12]

72. Edit Distance

  • DP
  • Hard
  • O(MN)
f(i, j) = edit distance s[:i] and t[:j].
           1. f(i-1, j) + 1   delete
f(i, j) =  2. f(i, j-1) + 1   insert
           3. f(i-1,j-1)      s[i] == t[j] do nothing
           4. f(i-1,j-1) + 1  s[i] != t[j] replace s[i]
class Solution:
    def top_down(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        @cache
        def f(i, j):
            if i == 0: return j
            if j == 0: return i
            
            return min(
                f(i,j-1) + 1,
                f(i-1,j) + 1,
                f(i-1,j-1)+int(word1[i-1] != word2[j-1])
            )
        return f(n, m)
    
    def bottom_up(self, word1, word2):
        n1, n2 = len(word1), len(word2)
        dp = list(range(n2+1))
        for r, char1 in enumerate(word1, 1):
            ndp = [r] + [0] * n2
            for c, char2 in enumerate(word2, 1):
                ndp[c] = min(
                    dp[c] + 1,
                    ndp[c-1] + 1,
                    dp[c-1] + int(char1 != char2)
                )
            dp = ndp
        return dp[-1]
    
    minDistance = bottom_up

[348]

[11]

[986]

[282]

[226]

[92]

[2089]

[220]

[797]

[84]

[322]

[155]

[70]

[3]

[461]

[827]

[50]

[332]

[114]

[54]

[208]

[1209]

[188]

[785]

[766]

[1539]

[98]

[415]

[146]

[408]

287. Find the Duplicate Number

  • Two Pointers
  • Medium
  • O(N)

  • Floyd’s algorithm for cycle detection.
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = nums[0], nums[0]
        while True:
            slow, fast = nums[slow], nums[nums[fast]]
            if slow == fast: break
        
        slow = nums[0]
        while slow != fast:
            slow, fast = nums[slow], nums[fast]
        return slow

[503]

[162]

[540]

[22]

[99]

[743]

[209]

[110]

[498]

76. Minimum Window Substring

  • Sliding Window / HashMap
  • Hard
  • O(N)

Brute force HashMap will be O(MN). Use a window to keep track of unmatched char frequencies in the window. Use a single counter to indicate whether the window is valid or not.

INF = 2 ** 32

class CharCounter(Counter):
    def __ge__(self, other):
        for k in other:
            if self.get(k, 0) < other.get(k):
                return False
        return True

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        target = CharCounter(t)
        l = 0
        min_size, min_l, min_r = INF, None, None
        window = CharCounter()
        for r, c in enumerate(s):
            window.update(c)
            while window >= target:
                if r - l + 1 < min_size:
                    min_size, min_l, min_r = r - l + 1, l, r
                window.subtract(s[l])
                l += 1
                
        return "" if min_l is None else s[min_l:min_r+ 1]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        min_size, min_l, min_r = INF, None, None
        target = Counter(t)
        to_match = len(target)
        l = 0
        for r, c in enumerate(s):
            if c not in target: continue
            target[c] -= 1
            if target[c] == 0: to_match -= 1
            
            while to_match == 0:
                if s[l] in target:
                    if target[s[l]] == 0: break
                    target[s[l]] += 1
                l += 1
            
            if to_match == 0 and r - l + 1 < min_size:
                min_size, min_l, min_r = r - l + 1, l, r
        return "" if min_l is None else s[min_l:min_r+ 1]

[104]

44. Wildcard Matching

  • Backtrack
  • Hard
  • O(MN)

Greedy match, when encounter *, keep track of its location in p and use it to match only one char in s. Continue matching, when match fails, try to backtrack to most recent star in p, use it to match this char in s. Then resume from there.

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        pi = si = 0
        p_star = s_star = -1
        while si < len(s):
            if pi < len(p) and p[pi] in ['?', s[si]]:  # match single
                pi += 1; si += 1
            elif pi < len(p) and p[pi] == '*':         # use star and continue
                p_star = pi; s_star = si                     
                pi += 1
            elif p_star == -1:                         # not match, no star to backtrack to 
                return False
            else:                                      # not match, backtrack to most recent *
                pi = p_star + 1                   
                si = s_star + 1
                s_star = si 
        return all(x == '*' for x in p[pi:])

[1929]

[16]

[1011]

[46]

1004. Max Consecutive Ones III

  • Sliding Window
  • Medium
  • O(N)

Slide window through the arry, keep track of window size with at most k 0s in the window.

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        max_length = count = 0
        l = 0
        for r, num in enumerate(nums):
            count += int(num == 0)
            while count == k + 1:
                count -= int(nums[l] == 0)
                l += 1
            max_length = max(max_length, r - l + 1)
        return max_length

[450]

[252]

[215]

[21]

[8]

[100]

[140]

[133]

[14]

[1143]

[217]

[5]

[442]

[905]

[414]

[739]

[392]

[26]

[1512]

[1094]

[973]

[32]

[212]

[27]

[167]

[647]

[1047]

[347]

[312]

[844]

[438]

[219]

[152]

[350]

[48]

[176]

[121]

[69]

227. Basic Calculator II

  • Stack
  • Medium
  • O(N)

Two types of operators, */ has precedence over +- thus we are actually evaluating */ first in one pass, then evaluate +- in a second pass. First pass: when operator is +-, put +-operand on stack. When operator is */, replace stack[-1] with stac[-1] */ operand. Second pass: sum the stack.

class Solution:
    def calculate(self, s: str) -> int:
        operators = set("+-*/")
        operand, operator = 0, "+"
        stack = []
        
        def operation():
            if operator == "+": stack.append(operand)
            if operator == "-": stack.append(-operand)
            if operator == "*": stack.append(stack.pop() * operand)
            if operator == "/": stack.append(int(stack.pop() / operand))
 
        for c in s:
            if c.isdigit(): 
                operand = operand * 10 + int(c)
            if c in operators:
                operation()
                operand, operator = 0, c
            
        operation()
        return sum(stack)

[297]

[49]

[238]

[28]

[242]

[35]

[131]

[105]

[213]

[9]

[997]

[36]

[191]

[45]

[310]

[160]

[19]

[122]

[231]

[67]

[234]

[139]

[31]

[268]

[74]

[55]

[1200]

[118]

[101]

[1041]

[20]

[143]

[141]

[189]

[977]