My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

accounts-merge(medium)

We cannot merge accounts in one pass because of the cases such as

[[“David","David0@m.co”,"David1@m.co"],[“David","David3@m.co”,"David4@m.co"],[“David","David4@m.co”,"David5@m.co"],[“David","David2@m.co”,"David3@m.co"],[“David","David1@m.co”,"David2@m.co"]]

So we need to do union find first.

  • Time complexity: O(nlogn).
  • Space complexity: O(nlogn).

best-time-to-buy-and-sell-stock-iii(medium)

DP. dp[i]: max profit before i; sq[i]: max profit after i. And the result should be max(dp[i] + sq[i]).

  • Time complexity: O(n).
  • Space complexity: O(n).

cherry-pickup(hard)

DP. Similar to NOI-传纸条.
dp[steps][x1][x2]: how many cherries can be picked from (0, 0) to (x1, steps-x1) and from (x1, steps-x1) to (0, 0).

  • Time complexity: O(n^3).
  • Space complexity: O(n^3).

count-complete-tree-nodes(medium)

If left child’s left-most path is longer than right child’s left-most path, then the right subtree is a full binary tree. Otherwise, the left subtree is a full binary tree. And number of nodes in a full binary tree can be computed according to the depth.

  • Time complexity: O(logn*logn).
  • Space complexity: O(1).

find-pivot-index(easy)

Prefix sums.

  • Time complexity: O(n).
  • Space complexity: O(n).

happy-number(easy)

DFS.

  • Time complexity: hard to tell.
  • Space complexity: O(1) except for stack.

implement-queue-using-stacks(medium)

It is a typical problem.
Two stacks: one for pushing back and one for popping front.

  • Time complexity: O(1) for push and empty. Amortized O(1) for pop and peek.
  • Space complexity: O(n).

interleaving-string(hard)

We cannot do it using greedy algorithm.
DP. It is similar to longest common subsequence.
dp[i][j]: first i letters in s3 matching first j letters in s1 and first (i - j) letters in s2.

  • Time complexity: O(s1.length*s3.length).
  • Space complexity: O(s1.length*s3.length).

island-perimeter(easy)

Perimeter increases by 1 where 1 is adjacent to 0.

  • Time complexity: O(width*length).
  • Space complexity: O(1).

max-increase-to-keep-city-skyline(easy)

The maximum height of a building is min(max(height of the buildings in the row), max(height of the buildings in the column)).

  • Time complexity: O(row*col).
  • Space complexity: O(row*col).

number-of-distinct-islands(medium)

It is a typical problem.
Different islands have different dfs sequences.

  • Time complexity: O(width*length).
  • Space complexity: O(width*length).

populating-next-right-pointers-in-each-node-ii(medium)

BFS: right child comes first.

  • Time complexity: O(n).
  • Space complexity: O(n).

remove-duplicate-letters(hard)

Greedy algorithm.
We prefer a to be first letter. However, can a be the first letter? we can check this by finding if all other letters contain a position which is larger than current index of a.
And this is the basic idea. Then we can try all as from the left-most position to the right-most position, then all bs and so on.

  • Time complexity: O(n).
  • Space complexity: O(n).

search-insert-position(easy)

Binary search.

  • Time complexity: O(logn).
  • Space complexity: O(1).

sparse-matrix-multiplication(easy)

Compress the sparse matrix.

  • Time complexity: it depends on how sparse the matrix is.
  • Space complexity: O(#non-zero-number).

spiral-matrix-ii(easy)

Maintain a direction.

  • Time complexity: O(n^2).
  • Space complexity: O(n^2).

substring-with-concatenation-of-all-words(hard)

k sliding windows where k is the length of the word.

  • Time complexity: O(s.length*k).
  • Space complexity: (s.length*k).