402. Remove K Digits

I was thinking the K digits must be consecutive but it turns out it's not necessary. So the problem becomes easier. All I need to do is to discard the number that is larger than current number. Line 13 is very trick. Without this line, the code fails the case of ["9", 1]

1:  class Solution {  
2:  public:  
3:    string removeKdigits(string num, int k) {  
4:      string res = "";  
5:      int n = num.size(), sz = n-k;  
6:      for (c : num) {  
7:        while (k && !res.empty() && res.back() > c) {  
8:          res.pop_back();  
9:          k--;  
10:        }  
11:        res += c;  
12:      }  
13:      res.resize(sz);  
14:      int i = 0;  
15:      while (!res.empty() && res[i] == '0') i++;  
16:      res = res.substr(i);  
17:      return res.empty() ? "0" : res;  
18:    }  
19:  };  

406. Queue Reconstruction by Height

I don't have clue to solve the problem in first place. I followed the top rated solution.
- sort the array by the height in descending order and if heights are the same then sort by the k number in ascending order.
- create an empty array and insert into kth position the sorted people one by one.

1:  class Solution {  
2:  public:  
3:    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {  
4:      auto comp = [](pair<int, int> &p1, pair<int, int> &p2) {  
5:        return (p1.first > p2.first) || (p1.first == p2.first && p1.second < p2.second);  
6:      };  
7:      sort(people.begin(), people.end(), comp);  
8:      vector<pair<int, int>> res;  
9:      for (auto p : people) {  
10:        res.insert(res.begin() + p.second, p);  
11:      }  
12:      return res;  
13:    }  
14:  };  

277. Find the Celebrity

The idea is, first of all find the candidate first. And then verify the candidate. The key point here is the invariant that if everybody from [celebrity+1, n-1] must know the celebrity. If the invariant breaks, then the breaking one must be a candidate for the celebrity. And then in the second loop, we check whether the candidate is a valid celebrity.

1:  // Forward declaration of the knows API.  
2:  bool knows(int a, int b);  
3:  class Solution {  
4:  public:  
5:    int findCelebrity(int n) {  
6:      int candidate = 0;  
7:      for (int i = 1; i < n; i++) {  
8:        if (!knows(i, candidate)) candidate = i;  
9:      }  
10:      for (int i = 0; i < n; i++) {  
11:        if (candidate != i && (knows(candidate, i) || !knows(i, candidate))) return -1;  
12:      }  
13:      return candidate;  
14:    }  
15:  };  

122. Best Time to Buy and Sell Stock II

For this problem, we want to catch all the upside wave. So the problem becomes quite easy, i.e. as long as current price is larger than the last price we take the profit

1:  class Solution {  
2:  public:  
3:    int maxProfit(vector<int>& prices) {  
4:      int profit = 0;  
5:      for (int i = 1; i < prices.size(); i++) {  
6:        if (prices[i] > prices[i-1]) profit += prices[i]-prices[i-1];  
7:      }  
8:      return profit;  
9:    }  
10:  };  

316. Remove Duplicate Letters

The important point for this problem is that the result must keep the order of input string and also must be the smallest in lexicographical order among all possible results. To achieve this goal, the idea is to keep the smallest lexicographical order string so far. Whenever we meet a new letter that is smaller than the last letter in the result string, we check if the letter will appear later. If so, we can pop out the letter. We should keep popping out letters until there's no more letter later or the new letter becomes lager. And then we push the new letter to the back of result.

1:  class Solution {  
2:  public:  
3:    string removeDuplicateLetters(string s) {  
4:      vector<int> count(26, 0);  
5:      vector<bool> visited(26, false); // "cbacdcbc" 
6:      string res;  
7:      for (char c : s) {  
8:        count[c-'a']++;  
9:      }  
10:      for (char c : s) {  
11:        count[c-'a']--;  
12:        if (visited[c-'a']) continue;  
13:        while (!res.empty() && res.back() > c && count[res.back()-'a'] > 0) {  
14:          visited[res.back()-'a'] = false;  
15:          res.pop_back();  
16:        }  
17:        res += c;  
18:        visited[c-'a'] = true;  
19:      }  
20:      return res;  
21:    }  
22:  };  

330. Patching Array

I just follow the top voted solution. The idea is brilliant. The key is that assuming array [a1, a2, a3] can build [1,...,sum], where sum = a1+a2+a3, then for a new coming number a4, if a4 is less than or equal to sum, we definitely can build [1,...,sum+a4]. Otherwise, we need to patch a number and the right number patch is sum+1 such that the interval can be doubled. The reason is if you patch a number larger than sum, then you can’t cover (sum, p), and on the other hand, if you patch a number less than sum, your new covered interval is shorter than [1,...,2sum].

1:  class Solution {  
2:  public:  
3:    int minPatches(vector<int>& nums, int n) {  
4:      long long miss = 1;  
5:      int i = 0, patches = 0;  
6:      while (miss <= n) {  
7:        if (i < nums.size() && nums[i] <= miss) {  
8:          miss += nums[i++];  
9:        } else {  
10:          miss <<= 1;  
11:          patches++;  
12:        }  
13:      }  
14:      return patches;  
15:    }  
16:  };  

134. Gas Station

There are two important points:

1. if the total gas is larger or equal than cost, there must be a solution.

2. if the car starts from A but can't reach B, there mustn't be solution between A and B. This can be proved contradictorily. If there is K between A and B that the car can reach from A to K and reach from K to B, then the car must be able to reach B from A, which is contracting the assumption.

So, we can solve the problem by greedy, i.e., once we can't reach i' from i, then the start station must be i+1. If the total gas is larger or equal than the cost, the start station will be a valid solution.

1:  class Solution {  
2:  public:  
3:    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {  
4:      vector<int> diff(gas.size(), 0);  
5:      int totalGas = 0, start = 0, leftGas= 0;  
6:      for (int i = 0; i < gas.size(); i++) {  
7:        diff[i] = gas[i] - cost[i];  
8:      }  
9:      for (int i = 0; i < gas.size(); i++) {  
10:        totalGas += diff[i];  
11:        leftGas += diff[i];  
12:        if (leftGas < 0) {  
13:          start = i+1;  
14:          leftGas = 0;  
15:        }  
16:      }  
17:      return totalGas >= 0 ? start : -1;  
18:    }  
19:  };  

55. Jump Game

Let dp[i] be the maximum steps left on position i. So the dp state transition function is:

dp[i] = max(dp[i-1], nums[i-1])-1 (-1 means one step from previous position to current position)

Once dp[i] drops below 0, we are sure that we can't move forward and thus we can't reach the end.

1:  class Solution {  
2:  public:  
3:    bool canJump(vector<int>& nums) {  
4:      vector<int> dp(nums.size(), 0);  
5:      for (int i = 1; i < nums.size(); i++) {  
6:        dp[i] = max(dp[i-1], nums[i-1])-1;  
7:        if (dp[i] < 0) return false;  
8:      }  
9:      return true;  
10:    }  
11:  };  

This can be improved to be O(1) space as we only care about the previous state.

1:  class Solution {  
2:  public:  
3:    bool canJump(vector<int> &nums) {  
4:      int steps = 0;  
5:      for (int i = 1; i < nums.size(); i++) {  
6:        steps = max(steps, nums[i-1])-1;  
7:        if (steps < 0) return false;  
8:      }  
9:      return true;  
10:    }  
11:  };  

334. Increasing Triplet Subsequence

First of all, I'm thinking of solving the LIS and check if there is a subsequence that has length longer than 3. However, it requires time complexity of O(n) and space complexity of O(1) so obviously the DP solution for LIS won't work here. The top voted solution uses a very greedy algorithm, i.e. n1 keeps the smallest number, n2 keeps the second smallest number. Since it uses exclusive if condition, when n2 gets updated, there must be n1 updated too. Same for last clause.

1:  class Solution {  
2:  public:  
3:    bool increasingTriplet(vector<int>& nums) {  
4:      int n1 = INT_MAX, n2 = INT_MAX;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        if (nums[i] <= n1) {  
7:          n1 = nums[i];  
8:        } else if (nums[i] <= n2) {  
9:          n2 = nums[i];  
10:        } else {  
11:          return true;  
12:        }  
13:      }  
14:      return false;  
15:    }  
16:  };  

300. Longest Increasing Subsequence

Let dp[i] be the longest increasing subsequence till i. We need to move pointer from 1 to n-1 and for element i, we need to check from 0 to i-1, dp[i] = dp[j] + 1 if nums[i] > nums[j] and dp[j]+1 > dp[i].

1:  class Solution {  
2:  public:  
3:    int lengthOfLIS(vector<int>& nums) {  
4:      vector<int> dp(nums.size(), 1);  
5:      int maxLen = 0;  
6:      for (int i = 1; i < nums.size(); i++) {  
7:        for (int j = 0; j < i; j++) {  
8:          if (nums[j] < nums[i] && dp[i] < dp[j]+1) {  
9:            dp[i] = dp[j] + 1;  
10:          }  
11:        }  
12:      }  
13:      for (int i = 0; i < nums.size(); i++) {  
14:        maxLen = max(maxLen, dp[i]);  
15:      }  
16:      return maxLen;  
17:    }  
18:  };  

When I revisited this problem, the greedy algorithm seems working too. The idea is to keep an LIS vector, when the new number comes in, check it against the LIS, and replace the first number in LIS that is larger than the new number if any. Therefore the LIS always keeps the smallest increasing sequence and thus reaches the largest possibility to grow. With this algorithm, the searching can be modified to binary search in this algorithm so it can be improved to nlogn even faster than the DP.

1:  class Solution {  
2:  public:  
3:    int lengthOfLIS(vector<int>& nums) {  
4:      vector<int> lis;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        if (lis.empty() || nums[i] > lis[lis.size()-1]) lis.push_back(nums[i]);  
7:        else if (nums[i] > lis[0] || nums[i] < lis[lis.size()-1]) {  
8:          int j = 0;  
9:          while (nums[i] > lis[j]) j++;  
10:          lis[j] = nums[i];  
11:        }  
12:      }  
13:      return lis.size();  
14:    }  
15:  };