My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.
bricks-falling-when-hit(hard)
Reverse thinking and DSU to solve it offline.
- Time complexity: O(row*col).
- Space complexity: O(row*col).
closest-binary-search-tree-value-ii(medium)
Size of a subtree is a quite useful property for BST.
Binary search the radius of the result range. Then get the number of elements less than a certain value can be solved in O(logn) by using the size property.
If k is much smaller than n, then we can find k predecessors and k successors using stack.
- Time complexity: O(n) for initialization of size, O(logn*log(MAX_DIFF)) for binary searching and checking.
- Space complexity: O(n).
delete-and-earn(medium)
DP. Note that the range of numbers’ values are small.
dp[0][i]: maximum earn after delete numbers less than i, and i is deleted for earning.
dp[1][i]: delete numbers less than i, and i is not deleted for earning. It should be deleted by deleting (i - 1) to guarantee no aftereffect.
- Time complexity: O(range) + O(n).
- Space complexity: O(range).
design-phone-directory(easy)
unordered_set.
- Time complexity: O(1).
- Space complexity: O(n).
excel-sheet-column-title(easy)
It can be a little bit awkward, because the numbers do not start with 0.
- Time complexity: O(logn).
- Space complexity: O(logn).
house-robber-ii(easy)
DP. There are two cases: rob the first, then you cannot rob the last and not rob the first, then you can rob the last house or not rob.
- Time complexity: O(n).
- Space complexity: O(n).
kth-smallest-element-in-a-bst(easy)
Use size property.
Follow-up: maintain the size of each subtree, then each query will be O(logn).
- Time complexity: O(n) for initialization, O(logn) for query.
- Space complexity: O(n).
longest-palindromic-subsequence(medium)
DP if intervals implemented by dfs with cache.
- Time complexity: O(length^2).
- Space complexity: O(length^2).
next-greater-element-i(easy)
First greater element on the right using mono-stack in O(n).
- Time complexity: O(n).
- Space complexity: O(n).
number-of-atoms(medium)
DFS of intervals and keep track of the outer scale. However, it could be annoying to numbers, letters and parentheses.
- Time complexity: O(length^2).
- Space complexity: O(length).
pacific-atlantic-water-flow(medium)
BFS. Add all points out of the range to the queue.
- Time complexity: O(row*col).
- Space complexity: O(row*col).
read-n-characters-given-read4(easy)
Bad description.
- Time complexity: O(n).
- Space complexity: O(1).
reverse-pairs(medium)
Reverse pairs using BIT with discretization.
1 | sort(v.begin(), v.end()); |
- Time complexity: O(nlogn).
- Space complexity: O(n).
strobogrammatic-number(easy)
- Time complexity: O(length).
- Space complexity: O(1).
sum-of-subsequence-widths(medium)
I misunderstood the meaning of subsequence as subarray which should be continuous. Then, my solution is to convert sum of widths to: sum(max) - sum(min).
I found the problem with this meaning.
For A[i], if we want it to be the maximum in the subarray, then only need to know there are how many such subarrays which can be solved using the first larger element on its left and the first larger element on its right.
However, subsequence here means subset. Then, we can use the same conversion and the problem gets much easier using fast power.
- Time complexity: O(n*logn).
- Space complexity: O(n).
walls-and-gates(medium)
It is a typical usage of BFS of multi-bfs in one. For these kind of BFS, we will add many start states to the queue.
- Time complexity: O(row*col).
- Space complexity: O(row*col).