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

cheapest-flights-within-k-stops(medium)

Shortest path problem with an additional dimension to denote steps: dis[i][j] means shortest path from src to i, passing j nodes. It is an O(mk) solution, where m is number of edges.
Another brilliant way is floyd + fast power. However, it takes O(n^3logk) time, which is much larger than former solution.

  • Time complexity: O(n^3logk) or O(mk).
  • Space complexity: O(n^2) or O(nk).

continuous-subarray-sum(easy)

Because the subarray should contains at least two elements, we should apply delay insertion to map.

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

design-hashmap(medium)

Self-designed map.

  • Time complexity: O(1) if no conflicts.
  • Space complexity: it depends.

24-game(hard)

Use stack to simulate ( and ), then we do not to consider brackets when running dfs. Enumerate the order of four numbers, then enumerate three operators. When running dfs, use stack to determine calculation order.
However, it is a stupid method. A smarter way is to enumerate the order of four numbers according to calculation order.

  • Time complexity: O(4^3*4!*2), where 2 means for - and / we should consider which number is put at the front and which number is put at the back.
  • Space complexity: O(4).

add-and-search-word-data-structure-design(medium)

DFS on trie.

  • Time complexity: O(length) for addWord, O(#nodes) for search in the worst case.
  • Space complexity: O(n*length) in the worst case.

coin-change-2(medium)

Complete knapsack problem.

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

count-univalue-subtrees(easy)

DFS(recursion): the left child and right child should be univalue if a subtree is univalue.

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

first-bad-version(easy)

Binary search.

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

flatten-2d-vector(easy)

Just be care of empty vector.

  • Time complexity: O(1) on average.
  • Space complexity: O(1).

intersection-of-two-arrays-ii(easy)

Count how many times each element appears in these two arrays respectively.

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

kth-smallest-element-in-a-sorted-matrix(medium)

Binary search the result, then we should count how many numbers less than the result. For counting, we can enumerate the rows and binary search each row.

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

maximum-sum-of-3-non-overlapping-subarrays(medium)

DP with storing paths(decisions). dp[i][j] denotes the maximum sum of j subarrays for the first i elements.

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

minimum-time-difference(easy)

Convert the string of time to a number of minutes.

  • Time complexity: O(n).
  • Space complexity: O(24*60).

missing-number(easy)

Sum of 1 to n.

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

moving-average-from-data-stream(easy)

Sliding window and maintaining sum of elements in the window.

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

permutation-in-string(easy)

Sliding window. Reduce time complexity from O(26n) to O(n) by counting how many times letters appears.

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

range-sum-query-2d-immutable(easy)

Prefix sum of 2d array.

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

shortest-distance-from-all-buildings(medium)

BFS from all buildings and add distance to empty land for each BFS.

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

shortest-word-distance-ii(medium)

Merge two ordered array because the shortest distance must be two adjacent positions.

  • Time complexity: O(n) in the worst case.
  • Space complexity: O(n).

sudoku-solver(medium)

DFS with accelerating checking availability: maintaining number available for 9 rows, 9 cols and 9 sub-boxes.
Dancing links are too complicated.

  • Time complexity: O(9^#empty_position) although in practical it never reach this complexity.
  • Space complexity: O((9+9+9)*9).

triangle(easy)

DP. Space can be compressed because current state only depends on states in the upper layer.

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

two-sum-iii-data-structure-design(easy)

The testcase mostly consists of add rather than find, so we should mainly consider the time complexity of add function.

  • Time complexity: O(1) for add, O(n) for find.
  • Space complexity: O(n).

wiggle-sort(medium)

It is much easier than wiggle-sort-ii.
It can be solved using double sorts, although it can also be solved using the same method of wiggle-sort-ii.

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