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

asteroid-collision(medium)

Monotonous stack: each negative asteroid will make positive asteroids with less size explode until it meet a larger positive asteroid.

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

design-tic-tac-toe(easy)

There are only n + n + 2 ways to win the tic tac toe: n rows, n columns, and 2 diagonals.

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

mencode-and-decode-tinyurl(easy)

Map url to a number and then convert the number to a string with the length of 6 consisting of ‘a’-‘z’, ‘A’-‘Z’ and ‘0’-‘9’. Thus, it can store 62^6 mappings.

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

find-the-celebrity(medium)

The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.
Thus, the celebrity must be the last node in any one of the paths.

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

guess-the-word(medium)

Because words are generated randomly, there should be many pairs matching 0 letters and much less pairs matching word.length()-1 letters.
For a word, if the return value of guess() is 0, we cannot exclude any other words.
So, we should select the word with least matching-0 pairs to guess to reduce the probability of getting 0 from guess().

  • Time complexity: in worst case, such as {‘a’, ‘b’, … , ‘z’}, O(n).
  • Space complexity: O(n).

reverse-linked-list-ii(easy)

One pass solution.

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

robot-room-cleaner(medium)

Use relative coordinates to DFS with backtracking.

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

serialize-and-deserialize-bst(medium)

Use DFS to encode and decode the tree. When come to a NULL node, backtrack.

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

subarray-product-less-than-k(medium)

Two pointers and maintain the product of numbers between left and right pointers.
When left pointer moves back, the product will not increase. Thus, the right pointer never moves forward.
And there is a brilliant idea that to use binary search by converting the problem from subarray products to subarray sums using log.

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

super-egg-drop(hard)

First, my intuition is to binary search. However, it is correct only when K is large enough.
Then, I thought a dp solution: dp[i][j] = min(max(dp[i - 1][k], dp[i][j - k - 1])), O(k*n^2). However, it is O(n) for each state transition.
Finally, I saw a elegant dp solution: dp[i][j] = 1 + dp[i - 1][j - 1] + dp[i][j - 1], where dp[i][j] means given i moves and j eggs, how many floors can be excluded.
1 means current floor, dp[i - 1][j - 1] means the egg is broken and move downstairs, dp[i][j - 1] means the egg is not broken and move upstairs.

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

top-k-frequent-words(medium)

Use a priority_queue to maintain the top k frequent words. The trick is to keep the least frequent words at the top.
If the output order is not required, we can use the similar methods as finding the k-th largest number in O(n).

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

valid-anagram(easy)

Count the frequency of all letters.

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