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

candy-crush(medium)

Each round, we should crush all candies simultaneously and then we go for the next round.
My way is to mark horizontal candies as 1 and vertical candies as 2. It takes O(width*height) time.

  • Time complexity: O(#roundwidthheight).
  • Space complexity: O(width*height).

candy(medium)

Compute the longest consecutive ascending subarray both from left and right. Select the greater number as the number of candies the child is given.

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

degree-of-an-array(easy)

keep track of how many times a number occurs and its left-most and right-most index using three maps.

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

employee-free-time(medium)

My intuition is segments overlap(line sweep) which takes O(mlogm) time where m is the number of intervals.
Another method is to merge k ordered array and keep track of the latest end time, which is O(mlogn) where n is the number of employees.

  • Time complexity: O(mlogm) or O(mlogn).
  • Space complexity: O(m).

find-all-duplicates-in-an-array(medium)

It is a tricky but typical problem. Without using extra space, we should make a better use of the indexes by swapping nums[i] to the index of (nums[i] - 1).
Then, only duplicated numbers’ indexes will not be num - 1.

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

insert-delete-getrandom-o1-duplicates-allowed(hard)

GetRandom in O(1) time means we should use array as the fundamental data structure. To delete a number, we can use a map to save its index and move the last number of the array to its index if there is no duplicate.
When duplicates are allowed, we should build a doubly linked list on the array.

  • Time complexity: O(1) for each operation.
  • Space complexity: O(n).

partition-to-k-equal-sum-subsets(hard)

The straightforward way is DFS. However, I got TLE because I did not pass the start index as a parameter. Without it, we can run into cases which have been searched.
Another way is state-compressed DP. We should only consider the last number we have added to current subset.

  • Time complexity: O(NN!) for DFS and O(N2^N) for DP.
  • Space complexity: O(N) for DFS and O(2^N) for DP.

serialize-and-deserialize-n-ary-tree(medium)

DFS. The same as binary tree serialization and deserialization by using a special character to denote backtracking.

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

sliding-puzzle(medium)

BFS. We should compress the puzzle grids to a number when pushing into the queue and extract the number to the puzzle grid when searching.
A better but more complicated way is to bfs from source state and target state at the same time.

  • Time complexity: O(6!46).
  • Space complexity: O(6!46).

summary-ranges(easy)

Just scan from left to right.

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