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

minimum-cost-for-tickets(medium)

The straightforward way is dp day by day.
dp[i]: the minimum cost for tickets before day i.
The state transfer is:

1
2
3
4

if (!mp[i]) dp[i] = dp[i - 1];
dp[i] = min(dp[i], dp[i - 1] + costs[0]);
if (i >= 7) dp[i] = min(dp[i], dp[i - 7] + costs[1]);
if (i >= 30) dp[i] = min(dp[i], dp[i - 30] + costs[2]);

However, here is a trick: the result could not be dp[365].
Another solution is much brighter and faster: dp[i] indicates the minimum cost for tickets from day[i] to the last day.
The state transfer is:

1
2
3
4
5
6
7
8
9
10

int n1 = n - 1, n7 = n - 1, n30 = n - 1;
for (int i = n - 1; i >= 0; i --) {
    while (days[n1] >= days[i] + 1) n1 --;
    while (days[n7] >= days[i] + 7) n7 --;
    while (days[n30] >= days[i] + 30) n30 --;

    dp[i] = min(dp[i], dp[n1 + 1] + costs[0]);
    dp[i] = min(dp[i], dp[n7 + 1] + costs[1]);
    dp[i] = min(dp[i], dp[n30 + 1] + costs[2]);
}

• Time complexity: O(400), or O(n).
• Space complexity: O(400), or O(n).

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

subarray-sums-divisible-by-k(medium)

I have to admit that it’s a good problem and it seems pretty hard at first glance. However, if you know:

1. a little about congruence group, the solution will be very straightforward;
2. sum of a subarray can be represented using two the difference between two prefix sums.

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

interval-list-intersections(easy)

It’s a quite common interval merge problem. The solution is:

1. sort if it’s out of order;
2. use a pointer to indicate the next candidate which can contribute to the results.

THere are two lists, so we’ll use two pointers for them respectively.

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

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

robot-return-to-origin(easy)

Use dx++/-- and dy++/-- to indicate the move of the robot.

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

reverse-vowels-of-a-string(easy)

Scan the string from left to right and save all vowels in order in an array. Then, replace the vowels from right to left according to the array. Another way is to use two pointers to walk the string from left and right respectively and swap the vowels.

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

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

find-leaves-of-binary-tree(easy)

Compute the maximum distance to the leaves using Bottom-Up DFS.

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

friends-of-appropriate-ages(easy)

People with the same age have no difference to each other. So, we can just save how many people are of this age.
Then, use the constraints to find the available age range.

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

graph-valid-tree(easy)

Use DSU to check whether a graph is a tree.

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

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

1-bit-and-2-bit-characters(easy)

Check from left to right.

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

construct-binary-tree-from-inorder-and-postorder-traversal(easy)

The same as construct BST from inorder and preorder traversal.

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

construct-quad-tree(easy)

Just be careful to coordinates.

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

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

beautiful-array(hard)

It is hard because the first time I see this problem, I didn’t have any idea of how to solve it.
Then, it the discuss, I found a quite brilliant way which is kind of like a reversion divide and conquer.
Divide the range to the odd part and the even part. Combining with the two properties, we can scale down the problem.
Link.

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

expressive-words(easy)

O(n) for enumerating groups, O(n) for checking if one group can extend to another.

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

logger-rate-limiter(easy)

Use a map to save the timestamp.

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

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

arranging-coins(easy)

Math.

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

combination-sum-iv(medium)

Knapsack problem. Just note the order of the loops and which loop is the outer one.
As for the follow-up, I think we should add the limitation that we can only use a negative number at most once, or there could be infinite combinations. And then to solve this new problem, my idea is run 01-knapsack problem to initialize the array dp. This is just what I think about, and I cannot guarantee it is correct.

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

generate-random-point-in-a-circle(medium)

A simplest way is to use rejection sampling, which I have mentioned before.
However, my intuition is to pick a radius and a radian randomly, which seems like quite easy. However, there exists a pitfall that the probability of a point with a larger radius should be larger than that with a smaller radius.

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

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

boundary-of-binary-tree(easy)

The top is the root, the left or right boundary is the “leftmost” or “rightmost” nodes. The remaining leaves are the bottom.
Use dfs to get the left boundary and leaves in the left subtree. And do the same thing for right boundary and leaves in the right subtree.

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

custom-sort-string(medium)

The easiest approach is to use quick sort and overwrite the compare function, which is O(nlogn).
However, there will only be at most 26 characters. Thus, we can use counting sort which is not based on comparison.

• Time complexity: O(s.length+t.length).
• Space complexity: extra O(26).

design-circular-queue(easy)

Circular queue’s size should be (1 + size of ordinary queue) in order to represent states of empty and full.

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

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

all-paths-from-source-to-target(easy)

DFS and keep track of current path.

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

convert-sorted-list-to-binary-search-tree(medium)

The same as building BST from sorted array. And the only difference is we should traverse the whole linked list to get its length is each round of DFS. So, the time complexity will be O(nlogn) rather than O(n).
Another smarter O(n) solution is using in-order traversal: Link, which is to keep track of current node pointer and build the tree from left to right using recursion of in-order traversal.

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

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

card-flipping-game(easy)

The description is kind of vague. Another description from discussion is:

Given an array of cards with numbers written on both sides and an infinite number of card flips, find the minimum number appearing on any card’s back which is not appearing on any card’s front.

And the solution is to find the smallest number which never appears on both sides of any card.

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

count-different-palindromic-subsequences(hard)

The most difficult point of this problem is how to deal with the duplicate subsequences.
dp[c][lt][rt]: number of different subsequences which start with c and end with c using letters in range [lt, rt].
The key point is when c == s[lt] == s[rt]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

if (s[lt] == 'a' + c && s[rt] == 'a' + c) {
    if (lt + 1 == rt) {
        res = 2; // c, cc
        return res;
    }

    res = 1; // cc
    res += dfs(dp, s, c, lt + 1, rt - 1);
    if (dfs(dp, s, c, lt + 1, rt - 1)) res ++; // there exists at least one c, then 1 for cc...cc or c...c...c
    else res ++; // there exists no c, then 1 for c
    res %= mod;
    for (int i = 0; i < 4; i ++)
        if (i != c) {
            res += dfs(dp, s, i, lt + 1, rt - 1);
            res %= mod;
        }
}

PS: Why I got MLE if I used the resize function???

• Time complexity: O(4*length^2).
• Space complexity: O(4*length^2).

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).

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

battleships-in-a-board(easy)

Because there is no two adjacent battleships, we can just count the top-left X in one pass.

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

best-meeting-point(medium)

Manhattan distance: x and y are independent.

Then we can just think about the problem of 1D, and the solution is quite direct: to find the median.

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

bulls-and-cows(easy)

Count using map. To avoid duplication, we can decrease the counter by one when there is a cow.

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

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

all-nodes-distance-k-in-binary-tree(medium)

ALL problem related to distance in trees can be solved using depth.
Find the depth of the target node. If it is in the left subtree, find all nodes which meet the requirement in the right subtree. And if it is in the right subtree, find all nodes in left subtree.
If the difference of depth between current node and the target node is K, push back current node to the results.

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

binary-tree-paths(easy)

DFS.

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

diagonal-traverse(easy)

There are 4 ways of going out of bounds in total.

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

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

balanced-binary-tree(easy)

DFS for depth.

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

best-time-to-buy-and-sell-stock-iv(hard)

DP.
Basic idea: dp[i][j] denotes maximum profit for first i days and at most j transactions. dp[i][j] = max(dp[p - 1][j - 1] + prices[i] - prices[p]), where p <= i.
However, it is an O(kn^2) method.
And the optimization is to keep track of the maximum value of (dp[p - 1][j - 1] - prices[p]) while looping through i.
And another optimization is to use rolling array.

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

design-linked-list(easy)

I did not implement linked list myself, but directly use stl list.

• Time complexity: O(1) for insert and delete, O(n) for indexing.
• Space complexity: O(n).

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

delete-node-in-a-bst(medium)

First, find the node which should be deleted.
(1) If the node is a leaf node, delete it directly.
(2) If the node has exactly one child, replace it with its child.
(3) If the node has two child, we will find the largest element in its left subtree, and replace it with that element. This can be implemented using recursion of deleting an element in its left subtree.

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

flatten-a-multilevel-doubly-linked-list(easy)

There are some pitfalls: (1) make nodes’ child pointers to NULL; (2) the same instance can be used for many times.

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

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).

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).