153. Find Minimum in Rotated Sorted Array

Modified binary search. Instead of checking nums[mid] == target, we check if nums[lo] < nums[hi]. If so, the minimum is nums[lo]. Otherwise, we just need to keep looking for the rotated pivot. There are two cases:

Case 1: nums[mid] < nums[lo]
[7,6,1,2,3,4,5], the pivot must be on the left of mid. Since pivot is on the left, the mid itself could be the minimum too, so the high boundary will be mid.

Case 2: nums[mid] >= nums[lo]
[4,5,6,7,0,1,2], the pivot must be on the right of mid. So the low boundary will be mid+1.

1:  class Solution {  
2:  public:  
3:    int findMin(vector<int>& nums) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo < hi) {  
6:        if (nums[lo] < nums[hi]) {  
7:          return nums[lo];  
8:        }  
9:        int mid = lo + (hi - lo) / 2;  
10:        // [4,5,6,7,0,1,2]  
11:        if (nums[mid] >= nums[lo]) {  
12:          lo = mid + 1;  
13:        } else {  
14:          // [7,6,1,2,3,4,5]  
15:          hi = mid;  
16:        }  
17:      }  
18:      return nums[lo];  
19:    }  
20:  };  

89. Gray Code

I solved this problem by observing some examples. For gray code that has 4 bits,
0 0 0 0
0 0 0 1
=====
0 0 1 1
0 0 1 0
=====
0 1 1 0
0 1 1 1
0 1 0 1
0 1 0 0
=====
1 1 0 0
1 1 0 1
1 1 1 1
1 1 1 0
1 0 1 0
1 0 1 1
1 0 0 1
1 0 0 0
From the example above, I find that the gray code can be generated one bit by one bit. For a new significant bit, the gray code can be generated by the previous result in reverse order.

1:  class Solution {  
2:  public:  
3:    vector<int> grayCode(int n) {  
4:      vector<int> res(1, 0);  
5:      for (int i = 0, bit = 1; i < n; i++, bit <<= 1) {  
6:        for (int j = res.size()-1; j >= 0; j--) {  
7:          res.push_back(res[j]+bit);  
8:        }  
9:      }  
10:      return res;  
11:    }  
12:  };  

98. Validate Binary Search Tree

In first place, I made a mistake that I only recursively compare the parent with its left and right child. This is incorrect. Note for a BST, all the nodes left child subtree are less than the root and on the other hand, all the nodes in right child subtree are larger than the root. Therefore, when doing the recursive call, we need to compare the current node with a minimal node and a maximal node. For the left subtree, the maximal node is the current node and for the right subtree, the minimal node is the current node. Also, the recursive function follows inorder traversal.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    bool isValidBST(TreeNode* root) {  
13:      return helper(root, NULL, NULL);  
14:    }  
15:    bool helper(TreeNode *root, TreeNode *minNode, TreeNode *maxNode) {  
16:      if (root == NULL) return true;  
17:      if (minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val) {  
18:        return false;  
19:      }  
20:      return helper(root->left, minNode, root) && helper(root->right, root, maxNode);  
21:    }  
22:  };  

216. Combination Sum III

This is a combination problem so the intuition is to use backtracking algorithm. A trick here is for the for loop, the start will be the last number from the result of last iteration and the end will be 9 because duplicated number is not allowed. Let's see an example why we do this way.

Input k = 3, n = 9
R1,  R2,    R3
[1], [1, 2], [1, 2, 6]
       [1, 3], [1, 3, 5]
       [1, 4...9]
[2], [2, 3], [2, 3, 4]
       [2, 4...9]
[3...9]

From the example we can see, that we should start from the last number from the result of last iteration. If we don't, then we'll introduce duplicated solutions.

1:  class Solution {  
2:  private:  
3:    vector<vector<int>> res;  
4:  public:  
5:    vector<vector<int>> combinationSum3(int k, int n) {  
6:      vector<int> sol;  
7:      helper(k, n, sol);  
8:      return res;  
9:    }  
10:    void helper(int k, int n, vector<int> &sol) {  
11:      if (k > n || (k == 0 && n != 0)) return;  
12:      if (k == 0 && n == 0) {  
13:        res.push_back(sol);  
14:        return;  
15:      }  
16:      for (int i = sol.empty() ? 1 : sol.back()+1; i < 10; i++) {  
17:        sol.push_back(i);  
18:        helper(k-1, n-i, sol);  
19:        sol.pop_back();  
20:      }  
21:      return;  
22:    }  
23:  };  

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:  };  

50. Pow(x, n)

In first place, I'm thinking of calling the function twice with x and n/2 each. It is working but it gets TLE because of too many of recursions.

1:  class Solution {  
2:  public:  
3:    double myPow(double x, int n) {  
4:      if (n == 0) return 1.0;  
5:      x = n < 0 ? 1/x : x;  
6:      return helper(x, abs(n));  
7:    }  
8:    double helper(double x, int n) {  
9:      if (n == 1) return x;  
10:      if (n & 1) return x * helper(x, (n-1)/2) * helper(x, (n-1)/2);  
11:      else return helper(x, n/2) * helper(x, n/2);  
12:    }  
13:  };  

Another way is to call the function once as following. Need to deal with two cases where n is even or n is odd. Particularly, be careful about the case where n < 0.

1:  class Solution {  
2:  public:  
3:    double myPow(double x, int n) {  
4:      if (n == 0) return 1;  
5:      double res = myPow(x, n/2);  
6:      if (n % 2 == 0) {  
7:        return res*res;  
8:      } else {  
9:        return n < 0 ? 1/x*res*res : x*res*res;  
10:      }  
11:    }  
12:  };  

228. Summary Ranges

Just be careful to handle the case where the range only contains one element.

1:  class Solution {  
2:  public:  
3:    vector<string> summaryRanges(vector<int>& nums) {  
4:      int i = 0, j = 0;  
5:      vector<string> res;  
6:      while (i < nums.size()) {  
7:        int count = 1;  
8:        string s = to_string(nums[i]);  
9:        for (++i; i < nums.size(); i++) {  
10:          if (nums[i] - nums[i-1] != 1) break;  
11:          count++;  
12:        }  
13:        if (count > 1) s += "->" + to_string(nums[i-1]);  
14:        res.push_back(s);  
15:      }  
16:      return res;  
17:    }  
18:  };  

Following is what I did when I revisited this problem. I made a mistake in line 8 in red.

1:  class Solution {  
2:  public:  
3:    vector<string> summaryRanges(vector<int>& nums) {  
4:      vector<string> res;  
5:      int i = 0, j = 0;  
6:      while (i < nums.size()) {  
7:        for (j = i; j < nums.size(); j++) {  
8:          if (j + 1 == nums.size() || nums[j] + 1 != nums[j+1]) {  
9:            if (j-i == 0) res.push_back(to_string(nums[i]));  
10:            else res.push_back(to_string(nums[i])+"->"+to_string(nums[j]));  
11:            break;  
12:          }  
13:        }  
14:        i = j+1;  
15:      }  
16:      return res;  
17:    }  
18:  };  

207. Course Schedule

A typical topology sort problem. The following youtube is a very good material explaining topology sort.
https://www.youtube.com/watch?v=XPM9Q2LMxFk&list=PLqD_OdMOd_6YixsHkd9f4sNdof4IhIima&index=11

In this problem, there are three points.
1. use adjacent-list to represent the graph. In c++, the representation can be vector<unordered_set<int>>.
2. To make a successful topology sort, we need to make sure there is no cycle in the graph. This can be done by DFS.
3. We need two vectors to keep track of visited vertex. The visited vector keeps global graph vertex status. The path vector keeps the vertex status in one dfs function, i.e. vertices connected directly or remotely with one particular vertex.

1:  class Solution {  
2:  public:  
3:    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {  
4:      vector<unordered_set<int>> graph(numCourses);  
5:      construct_graph(graph, prerequisites);  
6:      vector<bool> visited(numCourses, false);  
7:      vector<bool> path(numCourses, false);  
8:      for (int i = 0; i < numCourses; i++) {  
9:        if (!visited[i] && dfs(graph, i, path, visited))  
10:          return false;  
11:      }  
12:      return true;  
13:    }  
14:    void construct_graph(vector<unordered_set<int>> &graph, vector<pair<int, int>> &prerequisites) {  
15:      for (int i = 0; i < prerequisites.size(); i++) {  
16:        graph[prerequisites[i].first].insert(prerequisites[i].second);  
17:      }  
18:    }  
19:    bool dfs(vector<unordered_set<int>> &graph, int vertex, vector<bool> &path, vector<bool> &visited) {  
20:      if (visited[vertex]) return false;  
21:      path[vertex] = visited[vertex] = true;  
22:      for (auto v: graph[vertex]) {  
23:        if (path[v] || dfs(graph, v, path, visited)) {  
24:          return true;  
25:        }  
26:      }  
27:      path[vertex] = false;  
28:      return false;  
29:    }  
30:  };   

Note line 21 and line 27, we revert the path[vertex] status to false in the end because path is a reference and we don't find any cycle. The reason we don't have to worry about if dfs() changes the path[v] to false is once we find a cycle we return true all the way up to the top of stack and we don't have to worry about the path again. On the other hand, if no cycle is found, each dfs() will revert the path[vertex] status.

131. Palindrome Partitioning

Typical backtracking (or DFS) problem. In each DFS function, we'll check the substring of length [1, s.size()-start+1]. The termination condition will be start == s.size().

1:  class Solution {  
2:  public:  
3:    vector<vector<string>> partition(string s) {  
4:      vector<vector<string>> res;  
5:      vector<string> sol;  
6:      helper(0, s, sol, res);  
7:      return res;  
8:    }  
9:    bool isPalindrome(string s) {  
10:      int i = 0, j = s.size()-1;  
11:      while (i < j) {  
12:        if (s[i] != s[j]) return false;  
13:        i++; j--;  
14:      }  
15:      return true;  
16:    }  
17:    void helper(int start, string s, vector<string> &sol, vector<vector<string>> &res) {  
18:      if (start == s.size()) {  
19:        res.push_back(sol);  
20:        return;  
21:      }  
22:      for (int i = start; i < s.size(); i++) {  
23:        string ss = s.substr(start, i-start+1);  
24:        if (isPalindrome(ss)) {  
25:          sol.push_back(ss);  
26:          helper(i+1, s, sol, res);  
27:          sol.pop_back();  
28:        }  
29:      }  
30:      return;  
31:    }  
32:  };  

40. Combination Sum II

Same idea as "39. Combination Sum". The only difference is to kick out duplicates.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {  
4:      sort(candidates.begin(), candidates.end());  
5:      vector<vector<int>> res;  
6:      vector<int> sol;  
7:      helper(candidates, sol, res, 0, target);  
8:      return res;  
9:    }  
10:    void helper(vector<int> &candidates, vector<int> &sol, vector<vector<int>> &res, int start, int target) {  
11:      if (target == 0) {  
12:        res.push_back(sol);  
13:        return;  
14:      }  
15:      if (target < 0) return;  
16:      for (int i = start; i < candidates.size(); i++) {  
17:        if (i > start && candidates[i] == candidates[i-1]) continue;  
18:        sol.push_back(candidates[i]);  
19:        helper(candidates, sol, res, i+1, target-candidates[i]);  
20:        sol.pop_back();  
21:      }  
22:    }  
23:  };  

When I revisited this problem, I did following way. I missed line 13 and made mistakes in
Line 22-23: I was trying to push candidates[start] to sol and call “helper(candidates, start+1, sum+candidates[start], target, sol, res)”.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {  
4:      vector<int> sol;  
5:      vector<vector<int>> res;  
6:      sort(candidates.begin(), candidates.end());  
7:      helper(candidates, 0, 0, target, sol, res);  
8:      return res;  
9:    }  
10:    void helper(vector<int> &candidates, int start, int sum, int target, vector<int> &sol, vector<vector<int>> &res) {  
11:      if (start == candidates.size()) return;  
12:      for (int i = start; i < candidates.size(); i++) {  
13:        if (i > start && candidates[i-1] == candidates[i]) continue;  
14:        if (candidates[i] + sum == target) {  
15:          sol.push_back(candidates[i]);  
16:          res.push_back(sol);  
17:          sol.pop_back();  
18:          return;  
19:        } else if (candidates[i] + sum > target) {  
20:          return;  
21:        } else {  
22:          sol.push_back(candidates[i]);  
23:          helper(candidates, i+1, sum+candidates[i], target, sol, res);  
24:          sol.pop_back();  
25:        }  
26:      }  
27:    }  
28:  };  

92. Reverse Linked List II

This problem can be done in two parts.
(1) move pointer to position m.
(2) reverse sublist from m to n. Note, the first node in the sublist will be the tail in the reversed list so we just need to move the node behind it to the head of the sublist by insertion. Also note prev->next will always be the head of the sublist no matter it is done with the reverse.

I made several mistakes here.
(1) In line 23, I was trying to link p->next to cur. This is true for the first round but it is wrong since then because cur is moved forward by inserting a tail node before it. Instead, we are inserting tail node before head which is actually prev->next.
(2) I was trying to move prev to next. Note, prev is always fixed here as in the sublist, we try to insert tail node before head which is right after prev.
(3) I was trying to compute n after line 17. Note after line 17, m has become 0.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* reverseBetween(ListNode* head, int m, int n) {  
12:      if (m == n) return head;  
13:      n -= m;  
14:      ListNode *dummy = new ListNode(-1);  
15:      dummy->next = head;  
16:      ListNode *prev = dummy;  
17:      while (--m) prev = prev->next;  
18:      ListNode *cur = prev->next;  
19:      // we don't need to move prev.  
20:      while (n--) {  
21:        ListNode *p = cur->next;  
22:        cur->next = p->next;  
23:        p->next = prev->next;  
24:        prev->next = p;  
25:      }  
26:      return dummy->next;  
27:    }  
28:  };  

200. Number of Islands

This problem can be solved by DFS. The idea is once we encounter a '1', we must have an island. Then we make it "water" (i.e. flip '1' to '0') and scan the surrounding areas. As a result, the island becomes sea in the end and we scan the matrix again until we find a new island again.

1:  class Solution {  
2:  private:  
3:    vector<pair<int, int>> dir;  
4:    int row;  
5:    int col;  
6:  public:  
7:    int numIslands(vector<vector<char>>& grid) {  
8:      row = grid.size();  
9:      if (row == 0) return 0;  
10:      col = grid[0].size();  
11:      int count = 0;  
12:      dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
13:      for (int i = 0; i < row; i++) {  
14:        for (int j = 0; j < col; j++) {  
15:          if (grid[i][j] == '1') {  
16:            count++;  
17:            dfs(grid, i, j);  
18:          }  
19:        }  
20:      }  
21:      return count;  
22:    }  
23:    void dfs(vector<vector<char>> &grid, int i, int j) {  
24:      grid[i][j] = '0';  
25:      for (int k = 0; k < dir.size(); k++) {  
26:        int ii = i + dir[k].first;  
27:        int jj = j + dir[k].second;  
28:        if (ii < 0 || ii == row || jj < 0 || jj == col || grid[ii][jj] == '0') continue;  
29:        dfs(grid, ii, jj);  
30:      }  
31:    }  
32:  };  

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:  };  

47. Permutations II

My solution modifies the input nums which costs a lot of performance (only beats 14%).

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> permuteUnique(vector<int>& nums) {  
4:      vector<vector<int>> res;  
5:      vector<int> sol;  
6:      sort(nums.begin(), nums.end());  
7:      helper(nums, sol, res);  
8:      return res;  
9:    }  
10:    void helper(vector<int> &nums, vector<int> &sol, vector<vector<int>> &res) {  
11:      if (nums.size() == 0) {  
12:        res.push_back(sol);  
13:        return;  
14:      }  
15:      for (int i = 0; i < nums.size(); i++) {  
16:        if (i > 0 && nums[i] == nums[i-1]) continue;  
17:        int tmp = nums[i];  
18:        sol.push_back(nums[i]);  
19:        nums.erase(nums.begin()+i);  
20:        helper(nums, sol, res);  
21:        nums.insert(nums.begin()+i, tmp);  
22:        sol.pop_back();  
23:      }  
24:    }  
25:  };  

The top voted algorithm uses swap. Node it is not passing nums as reference as recursive calls keeps swapping the elements so nums[i] is changed by the following recursive calls and you can't simply play swap again to get it nums[i] back to its original position.

When I revisited this problem, I made a mistake in
Line 5: I forget sorting the array in first place.
Line 9: I pass in a reference and I swap back after line 17. However, this generate duplicates. For example, a = [1,1,2,2]. After you swap a[0] and a[2], you get a = [2,1,1,2] and then you’ll get subsequent permutation like [2,1,2,1]. However, if you swap back a[0] and a[2], and then you’ll swap a[0] and a[3], this time you’ll get [2,1,2,1] which is a duplicate. Then the question is why just one swapping works. Because it prevent you from swapping the same number again since you have check “i != start && nums[start] == nums[i]”.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> permuteUnique(vector<int>& nums) {  
4:      vector<vector<int>> res;  
5:      sort(nums.begin(), nums.end());  
6:      helper(nums, 0, res);  
7:      return res;  
8:    }  
9:    void helper(vector<int> nums, int start, vector<vector<int>> &res) {  
10:      if (start == nums.size()) {  
11:        res.push_back(nums);  
12:        return;  
13:      }  
14:      for (int i = start; i < nums.size(); i++) {  
15:        if (i > start && nums[start] == nums[i]) continue;  
16:        swap(nums[start], nums[i]);  
17:        helper(nums, start+1, res);  
18:      }  
19:    }  
20:  };  

236. Lowest Common Ancestor of a Binary Tree

The key is to check if any one of the two target node is in left tree or right tree. The recursive function terminates at whenever encountering a target node. With this termination, it is clear that if left child subtree doesn't contain any of them, the first target is encountered in right tree will be the LCA of the other node. Therefore, we need to traverse the left subtree and the right subtree and check the result coming from the left and right subtrees.

(WRONG: I was trying to terminate one a target is found in the left subtree or in the right subtree. It is wrong because with the termination condition, you don't know if the other target node is in the same subtree or in the other.)

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {  
13:      if (root == NULL || root == p || root == q) return root;  
14:      TreeNode *left = lowestCommonAncestor(root->left, p, q);  
15:      TreeNode *right = lowestCommonAncestor(root->right, p, q);  
16:      return !left ? right : !right ? left : root;  
17:    }  
18:  };  

105. Construct Binary Tree from Preorder and Inorder Traversal

Same idea as "106. Construct Binary Tree from Inorder and Postorder Traversal".

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {  
13:      if (preorder.empty() || preorder.size() != inorder.size()) return NULL;  
14:      return helper (preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);  
15:    }  
16:    TreeNode *helper(vector<int> &preorder, int ps, int pe, vector<int> &inorder, int is, int ie) {  
17:      if (ps > pe || is > ie) return NULL;  
18:      int i = is;  
19:      for (; i <= ie; i++) {  
20:        if (preorder[ps] == inorder[i]) break;  
21:      }  
22:      TreeNode *node = new TreeNode(preorder[ps]);  
23:      node->left = helper(preorder, ps+1, ps+i-is, inorder, is, is+i-1);  
24:      node->right = helper(preorder, ps+i-is+1, pe, inorder, i+1, ie);  
25:      return node;  
26:    }  
27:  };  

103. Binary Tree Zigzag Level Order Traversal

Typical level order traversal problem. We only need to keep a variable to know if we need to print from left to right or vice versa.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {  
13:      vector<vector<int>> res;  
14:      if (root == NULL) return res;  
15:      queue<TreeNode*> que;  
16:      bool ltor = true;  
17:      que.push(root);  
18:      while (!que.empty()) {  
19:        int n = que.size();  
20:        vector<int> row(n, 0);  
21:        for (int i = 0; i < n; i++) {  
22:          TreeNode *node = que.front();  
23:          que.pop();  
24:          int pos = ltor ? i : n-i-1;  
25:          row[pos] = node->val;  
26:          if (node->left) que.push(node->left);  
27:          if (node->right) que.push(node->right);  
28:        }  
29:        ltor = !ltor;  
30:        res.push_back(row);  
31:      }  
32:      return res;  
33:    }  
34:  };  

16. 3Sum Closest

First of all, sort the array. If you don't sort the array, the running time will be n!, i.e. approximately O(n^3). After sort, you can have one pointer scan from 0 to n-2 and inside the scanning loop, create two pointers j and k starting from i+1 and n-1 respectively. And then there will be three cases:
Case 1: nums[i] +  nums[j] + nums[k] == target. Then return immediately
Case 2: nums[i] + nums[j] + nums[k] < target. Since array is sorted, we just need to move j to right.
Case 3: nums[i] + nums[j] + nums[k] > target. Same idea as Case 2, we just need to move k to left.

1:  class Solution {  
2:  public:  
3:    int threeSumClosest(vector<int>& nums, int target) {  
4:      if (nums.size() < 3) return 0;  
5:      sort(nums.begin(), nums.end());  
6:      int closest = nums[0] + nums[1] + nums[2];  
7:      for (int i = 0; i < nums.size()-2; i++) {  
8:        if (i > 0 && nums[i] == nums[i-1]) continue;  
9:        int j = i+1;  
10:        int k = nums.size()-1;  
11:        while (j < k) {  
12:          int sum = nums[i] + nums[j] + nums[k];  
13:          if (sum == target) return sum;  
14:          if (abs(target-sum) < abs(target-closest)) {  
15:            closest = sum;  
16:          }  
17:          if (sum < target) j++;  
18:          else k--;  
19:        }  
20:      }  
21:      return closest;  
22:    }  
23:  };  

When I revisited this problem, I had a bit more concise solution.

1:  class Solution {  
2:  public:  
3:    int threeSumClosest(vector<int>& nums, int target) {  
4:      if (nums.size() < 3) return 0;  
5:      sort(nums.begin(), nums.end());  
6:      int minSum = nums[0]+nums[1]+nums[2];  
7:      for (int i = 0; i < nums.size()-2; i++) {  
8:        int l = i+1, r = nums.size()-1, t = target-nums[i];  
9:        while (l < r) {  
10:          if (abs(t-nums[l]-nums[r]) < abs(minSum-target)) minSum = nums[l]+nums[r]+nums[i];   
11:          if (nums[l]+nums[r] == t) return target;  
12:          else if (nums[l]+nums[r] > t) r--;  
13:          else l++;  
14:        }  
15:      }  
16:      return minSum;  
17:    }  
18:  };  

34. Search for a Range

Use binary search twice for left and right boundary respectively. Instead of checking nums[mid] == target, for left boundary, we only need to move the hi to mid. Note, we shouldn't move hi to mid-1 so that nums[hi] could be equal to target and hi will be the left boundary eventually. Then we can do the same thing to the right boundary but this time we move lo to mid. However, the mid needs to be computed as lo+(hi-lo)/2+1 such that the mid is biased to right. Otherwise, you'll get LTE if input is [2,2] as lo will stay at 0.

1:  class Solution {  
2:  public:  
3:    vector<int> searchRange(vector<int>& nums, int target) {  
4:      vector<int> res(2, -1);  
5:      int lo = 0, hi = nums.size()-1;  
6:      while (lo < hi) {  
7:        int mid = lo + (hi - lo) / 2;  
8:        if (nums[mid] < target) lo = mid + 1;  
9:        else hi = mid;  
10:      }  
11:      if (nums[hi] != target) return res;  
12:      res[0] = hi;  
13:      hi = nums.size()-1;  
14:      while (lo < hi) {  
15:        int mid = lo + (hi - lo) / 2+1;  
16:        if (nums[mid] > target) hi = mid - 1;  
17:        else lo = mid;  
18:      }  
19:      res[1] = lo;  
20:      return res;  
21:    }  
22:  };  

106. Construct Binary Tree from Inorder and Postorder Traversal

A typical recursive solution. Must be familiar with the property of inorder and postorder traversal.
(1) With postorder traversal, the root must be the last element in the array.
(2) With inorder traversal, the subarray on root's left forms the left child subtree and the subarray on root's right forms the right child subtree.
With the two properties above, we can solve the problem recursive.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {  
13:      if (inorder.empty()) return NULL;  
14:      return helper(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);  
15:    }  
16:    TreeNode *helper(vector<int> &inorder, int is, int ie, vector<int> &postorder, int ps, int pe) {  
17:      if (ie < is || pe < ps) return NULL;  
18:      int i = is;  
19:      for (;i < ie; i++) {  
20:        if (inorder[i] == postorder[pe]) break;  
21:      }  
22:      TreeNode *node = new TreeNode(postorder[pe]);  
23:      node->left = helper(inorder, is, i-1, postorder, ps, ps+i-is-1);  
24:      node->right = helper(inorder, i+1, ie, postorder, ps+i-is, pe-1);  
25:      return node;  
26:    }  
27:  };  

Note we have a loop to find the root position in inorder array. We can actually improve the algorithm by hashmap the value and its position first.

113. Path Sum II

Typical DFS problem. I was trying to prune the algorithm but it turns out I don't have to. The code is much concise without pruning and the performance isn't bad (16ms)

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    vector<vector<int>> pathSum(TreeNode* root, int sum) {  
13:      vector<vector<int>> res;  
14:      vector<int> sol;  
15:      helper(root, sum, sol, res);  
16:      return res;  
17:    }  
18:    void helper(TreeNode *root, int sum, vector<int> &sol, vector<vector<int>> &res) {  
19:      if (root == NULL) return;  
20:      sol.push_back(root->val);  
21:      if (!root->left && !root->right && sum == root->val)  
22:        res.push_back(sol);  
23:      helper(root->left, sum-root->val, sol, res);  
24:      helper(root->right, sum-root->val, sol, res);  
25:      sol.pop_back();  
26:      return;  
27:    }  
28:  };  

147. Insertion Sort List

Similar to "86. Partition List", don't forget to process a special case where no insertion is needed.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* insertionSortList(ListNode* head) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      dummy->next = head;  
14:      ListNode *head_prev = dummy;  
15:      while (head) {  
16:        ListNode *prev = dummy, *cur = dummy->next;  
17:        while (cur->val < head->val) {  
18:          prev = cur;  
19:          cur = cur->next;  
20:        }  
21:        if (cur == head) {
22:          head_prev = head;  
23:          head = head->next;  
24:        } else {  
25:          head_prev->next = head->next;  
26:          head->next = cur;  
27:          prev->next = head;  
28:          head = head_prev->next;  
29:        }  
30:      }  
31:      return dummy->next;  
32:    }  
33:  };  

Then code above only beats 24%, so it can be improved to beat 80%

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* insertionSortList(ListNode* head) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      dummy->next = head;  
14:      ListNode *prev = dummy, *cur = head;  
15:      while (cur) {  
16:        if (cur->next && cur->next->val < cur->val) {  
17:          while (prev->next && prev->next->val < cur->next->val) {  
18:            prev = prev->next;  
19:          }  
20:          ListNode *tmp = cur->next->next;  
21:          cur->next->next = prev->next;  
22:          prev->next = cur->next;  
23:          cur->next = tmp;  
24:          prev = dummy;  
25:        } else {  
26:          cur = cur->next;  
27:        }  
28:      }  
29:      return dummy->next;  
30:    }  
31:  };  

When I revisited this problem, I had a more concise solution.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* insertionSortList(ListNode* head) {  
12:      if (head == NULL) return NULL;  
13:      ListNode *dummy = new ListNode(-1);  
14:      ListNode *cur = head->next;  
15:      dummy->next = head, head->next = NULL;  
16:      while (cur) {  
17:        ListNode *p = dummy, *q = dummy->next;  
18:        while (q && q->val < cur->val) { p = q; q = q->next; }  
19:        p->next = cur;  
20:        cur = cur->next;  
21:        p->next->next = q;  
22:      }  
23:      head = dummy->next;  
24:      delete dummy;  
25:      return head;  
26:    }  
27:  };  

86. Partition List

My solution is to keep one pointer as the tail of list that is less than x. It also can be interpreted as the position to insert for next element less than x. I forget to deal with a special case where the first element is less than x and got LTE.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* partition(ListNode* head, int x) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      ListNode *prev = dummy, *cur = head, *par = dummy;  
14:      dummy->next = head;  
15:      while (cur) {  
16:        if (cur->val < x) {  
17:          if (prev == par) {  
18:            cur = cur->next;  
19:            prev = prev->next;  
20:            par = par->next;  
21:          } else {  
22:            prev->next = cur->next;  
23:            cur->next = par->next;  
24:            par->next = cur;  
25:            cur = prev->next;  
26:            par = par->next;  
27:          }  
28:        } else {  
29:          prev = cur;  
30:          cur = cur->next;  
31:        }  
32:      }  
33:      return dummy->next;  
34:    }  
35:  };  

Another solution will be separate the list into two lists and combine them in the end.

When I revisited this problem, I had a bit more concise solution.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* partition(ListNode* head, int x) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      ListNode *small = dummy;  
14:      ListNode *large = head, *large_head = NULL, *large_prev = NULL;  
15:      while (large) {  
16:        if (large->val < x) {  
17:          small->next = large;  
18:          large = large->next;  
19:          if (large_prev) large_prev->next = large;  
20:          small = small->next;  
21:          small->next = NULL;  
22:        } else {  
23:          if (large_head == NULL) large_head = large;  
24:          large_prev = large;  
25:          large = large->next;  
26:        }  
27:      }  
28:      small->next = large_head;  
29:      head = dummy->next;  
30:      delete dummy;  
31:      return head;  
32:    }  
33:  };  

367. Valid Perfect Square

A classical binary search problem. I use integer for mid in first place but get LTE. The reason is mid*mid gets overflowed. So I have to declare mid as long long.

1:  class Solution {  
2:  public:  
3:    bool isPerfectSquare(int num) {  
4:      int lo = 1, hi = num;  
5:      while (lo <= hi) {  
6:        long long mid = lo + (hi - lo) / 2;  
7:        if (mid*mid == num) return true;  
8:        else if (mid*mid > num) hi = mid-1;  
9:        else lo = mid+1;  
10:      }  
11:      return false;  
12:    }  
13:  };  

341. Flatten Nested List Iterator

Since there could be a lot of nested list, the intuition is to use stack, i.e. stack up the nested list and deal with the most inner list first.
The idea is keep stacking up all the elements in the list until the top element in the stack is not a nested list any more.
So in the constructor, we stack up all the elements in the list. Since we call hasNext() before next(), we'll process the stack mainly in the hasNext() interface. We get the top element in the stack. There'll be two cases:

Case 1: top element is an integer.
This is the easiest case where we return true. Since the next() interface needs this element so we'll leave the pop action in next().

Case 2: top element is a list.
Now we need to get the list and pop out this element in the stack. And then push all the elements in the list into stack. And then go back and check the top element again.

1:  /**  
2:   * // This is the interface that allows for creating nested lists.  
3:   * // You should not implement it, or speculate about its implementation  
4:   * class NestedInteger {  
5:   *  public:  
6:   *   // Return true if this NestedInteger holds a single integer, rather than a nested list.  
7:   *   bool isInteger() const;  
8:   *  
9:   *   // Return the single integer that this NestedInteger holds, if it holds a single integer  
10:   *   // The result is undefined if this NestedInteger holds a nested list  
11:   *   int getInteger() const;  
12:   *  
13:   *   // Return the nested list that this NestedInteger holds, if it holds a nested list  
14:   *   // The result is undefined if this NestedInteger holds a single integer  
15:   *   const vector<NestedInteger> &getList() const;  
16:   * };  
17:   */  
18:  class NestedIterator {  
19:  private:  
20:    stack<NestedInteger> stk;  
21:  public:  
22:    NestedIterator(vector<NestedInteger> &nestedList) {  
23:      for (int i = nestedList.size()-1; i >= 0; i--) {  
24:        stk.push(nestedList[i]);  
25:      }  
26:    }  
27:    int next() {  
28:      int val = stk.top().getInteger();  
29:      stk.pop();  
30:      return val;  
31:    }  
32:    bool hasNext() {  
33:      while (!stk.empty()) {  
34:        NestedInteger cur = stk.top();  
35:        if (cur.isInteger()) return true;  
36:        stk.pop();  
37:        vector<NestedInteger> &list = cur.getList();  
38:        for (int i = list.size()-1; i >= 0; i--) {  
39:          stk.push(list[i]);  
40:        }  
41:      }  
42:      return false;  
43:    }  
44:  };  
45:  /**  
46:   * Your NestedIterator object will be instantiated and called as such:  
47:   * NestedIterator i(nestedList);  
48:   * while (i.hasNext()) cout << i.next();  
49:   */  

When I revisited this problem, I tried to flat the list in next() function as following. However, it will get a runtime error if the input is "[[]]". The reason is the hasNext() simply checks if the stack is empty and thus will return true here. But in fact, it should be false. So we must flat the list in hasNext() function. Also I made a syntax error in line 32.

1:  /**  
2:   * // This is the interface that allows for creating nested lists.  
3:   * // You should not implement it, or speculate about its implementation  
4:   * class NestedInteger {  
5:   *  public:  
6:   *   // Return true if this NestedInteger holds a single integer, rather than a nested list.  
7:   *   bool isInteger() const;  
8:   *  
9:   *   // Return the single integer that this NestedInteger holds, if it holds a single integer  
10:   *   // The result is undefined if this NestedInteger holds a nested list  
11:   *   int getInteger() const;  
12:   *  
13:   *   // Return the nested list that this NestedInteger holds, if it holds a nested list  
14:   *   // The result is undefined if this NestedInteger holds a single integer  
15:   *   const vector<NestedInteger> &getList() const;  
16:   * };  
17:   */  
18:  class NestedIterator {  
19:  private:  
20:    stack<NestedInteger> stk;  
21:  public:  
22:    NestedIterator(vector<NestedInteger> &nestedList) {  
23:      int n = nestedList.size();  
24:      for (int i = n-1; i >= 0; i--) {  
25:        stk.push(nestedList[i]);  
26:      }  
27:    }  
28:    int next() {  
29:      while (!stk.top().isInteger()) {  
30:        NestedInteger t = stk.top();  
31:        stk.pop();  
32:        vector<NestedInteger> &list = t.getList();  
33:        int n = list.size();  
34:        for (int i = n-1; i >= 0; i--) {  
35:          stk.push(list[i]);  
36:        }  
37:      }  
38:      int ret = stk.top().getInteger();  
39:      stk.pop();  
40:      return ret;  
41:    }  
42:    bool hasNext() {  
43:      return !stk.empty();  
44:    }  
45:  };  
46:  /**  
47:   * Your NestedIterator object will be instantiated and called as such:  
48:   * NestedIterator i(nestedList);  
49:   * while (i.hasNext()) cout << i.next();  
50:   */  

109. Convert Sorted List to Binary Search Tree

The intuitive idea is to recursively construct binary search tree. There are two ways. First solution is using a counter.

1:  class Solution {  
2:  public:  
3:    TreeNode* sortedListToBST(ListNode* head) {  
4:      int len = 0;  
5:      ListNode *cur = head;  
6:      while (cur) {  
7:        len++;  
8:        cur = cur->next;  
9:      }  
10:      return helper(head, len);  
11:    }  
12:    TreeNode *helper(ListNode* head, int len) {  
13:      if (len == 0) return NULL;  
14:      int half = len / 2;  
15:      ListNode *cur = head;  
16:      for (int i = 0; i < half; i++) {  
17:        cur = cur->next;  
18:      }  
19:      TreeNode *node = new TreeNode(cur->val);  
20:      TreeNode *left = helper(head, half);  
21:      TreeNode *right = helper(cur->next, len-half-1);  
22:      node->left = left;  
23:      node->right = right;  
24:      return node;  
25:    }  
26:  };  

The second solution uses slow and fast pointer to find the middle node. This is a little bit faster than the first one because it saves one entire list scan.

1:  class Solution {  
2:  public:  
3:    TreeNode* sortedListToBST(ListNode* head) {  
4:      if (head == NULL) return NULL;  
5:      ListNode *slow = head, *fast = head, *prev = NULL;  
6:      while (fast && fast->next) {  
7:        prev = slow;  
8:        slow = slow->next;  
9:        fast = fast->next->next;  
10:      }  
11:      if (prev == NULL) head = NULL;  
12:      else prev->next = NULL;  
13:      TreeNode *node = new TreeNode(slow->val);  
14:      node->left = sortedListToBST(head);  
15:      node->right = sortedListToBST(slow->next);  
16:      return node;  
17:    }  
18:  };  

90. Subsets II

Same as "78. Subsets" except checking whether a new element is a duplicate.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> subsetsWithDup(vector<int>& nums) {  
4:      sort(nums.begin(), nums.end());  
5:      vector<vector<int>> res;  
6:      vector<int> sol;  
7:      res.push_back(sol);  
8:      helper(nums, 0, sol, res);  
9:      return res;  
10:    }  
11:    void helper(vector<int> &nums, int start, vector<int> &sol, vector<vector<int>> &res) {  
12:      for (int i = start; i < nums.size(); i++) {  
13:        if (i == start || nums[i] != nums[i-1]) {  
14:          sol.push_back(nums[i]);  
15:          res.push_back(sol);  
16:          helper(nums, i+1, sol, res);  
17:          sol.pop_back();  
18:        }  
19:      }  
20:    }  
21:  };  

142. Linked List Cycle II

I'm inspired by this blog which has very detailed explanation.

1:  class Solution {  
2:  public:  
3:    ListNode *detectCycle(ListNode *head) {  
4:      ListNode *slow = head, *fast = head;  
5:      while (slow && fast) {  
6:        slow = slow->next;  
7:        if (fast->next == NULL) return NULL;  
8:        fast = fast->next->next;  
9:        if (slow == fast) break;  
10:      }  
11:      if (fast == NULL) return NULL;  
12:      fast = head;  
13:      while (slow != fast) {  
14:        slow = slow->next;  
15:        fast = fast->next;  
16:      }  
17:      return slow;  
18:    }  
19:  };  

114. Flatten Binary Tree to Linked List

My solution is create a helper function that intakes a root and return the last node in the flatten list. So the tree can be flatten by flattening left and right child respectively and move the left child to right and connect the right child to the last node in the left flatten child.

1:  class Solution {  
2:  public:  
3:    void flatten(TreeNode* root) {  
4:      if (root == NULL) return;  
5:      helper(root);  
6:    }  
7:    TreeNode *helper(TreeNode *root) {  
8:      if (root->left == NULL && root->right == NULL) return root;  
9:      TreeNode *left = NULL;  
10:      TreeNode *right = NULL;  
11:      if (root->left != NULL) {  
12:        left = helper(root->left);  
13:        left->right = root->right;  
14:        root->right = root->left;  
15:        root->left = NULL;  
16:        if (left->right != NULL) {  
17:          return helper(left->right);  
18:        } else {  
19:          return left;  
20:        }  
21:      } else {  
22:        return helper(root->right);  
23:      }  
24:    }  
25:  };  

Also, my solution is quite slow (only beats 12%). It can be improved as following:

1:  class Solution {  
2:  public:  
3:    void flatten(TreeNode* root) {  
4:      helper(root);  
5:    }  
6:    TreeNode *helper(TreeNode *root) {  
7:      if (root == NULL) return NULL;  
8:      TreeNode *l_end = helper(root->left);  
9:      TreeNode *r_end = helper(root->right);  
10:      if (l_end) {  
11:        TreeNode *tmp = root->right;  
12:        root->right = root->left;  
13:        root->left = NULL;  
14:        l_end->right = tmp;  
15:      }  
16:      return r_end ? r_end : (l_end ? l_end : root);  
17:    }  
18:  };  

39. Combination Sum

A classical backtracking solution.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {  
4:      vector<vector<int>> res;  
5:      vector<int> sol;  
6:      sort(candidates.begin(), candidates.end());  
7:      helper(candidates, 0, sol, res, target);  
8:      return res;  
9:    }  
10:    void helper(vector<int> &candidates, int start, vector<int> &sol, vector<vector<int>> &res, int target) {  
11:      if (target == 0) {  
12:        res.push_back(sol);  
13:        return;  
14:      }  
15:      if (candidates[start] > target) return;  
16:      for (int i = start; i < candidates.size(); i++) {  
17:        sol.push_back(candidates[i]);  
18:        helper(candidates, i, sol, res, target-candidates[i]);  
19:        sol.pop_back();  
20:      }  
21:    }  
22:  };  

81. Search in Rotated Sorted Array II

Same idea of "33. Search in Rotated Sorted Array" but with one more case since there are duplicates.

Case 1: nums[lo] > nums[mid]
In this case, the right part of nums[mid] must be sorted. If the target is in sorted part, we make the search interval to be the sorted part. Otherwise, we make the search interval to be the rotated part.

Case 2: nums[mid] > nums[hi]
In this case, the left part of nums[mid] must be sorted. Then do as Case 1.

Case 3: nums[lo] == num[hi]
After excluding case 1 and case 2, there remaining condition is:
nums[lo] <= nums[mid] && nums[mid] <= nums[hi]
Since there are duplicates, all we need to deal with is the special case where nums[lo] == nums[hi]. And in this case, we only need to move lo and hi one step toward each other.

1:  class Solution {  
2:  public:  
3:    bool search(vector<int>& nums, int target) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo <= hi) {  
6:        int mid = lo + (hi - lo) / 2;  
7:        if (nums[mid] == target) return true;  
8:        if (nums[lo] > nums[mid]) {  
9:          // there is rotation, the right part of mid is sorted  
10:          if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;  
11:          else hi = mid - 1;  
12:        } else if (nums[hi] < nums[mid]) {  
13:          // there is rotation, the left part of mid is sorted  
14:          if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;  
15:          else lo = mid + 1;  
16:        } else if (nums[lo] < nums[hi]) {  
17:          // there is no rotation  
18:          if (target > nums[mid]) lo = mid + 1;  
19:          else hi = mid - 1;  
20:        } else {  
21:          lo++;  
22:          hi--;  
23:        }  
24:      }  
25:      return false;  
26:    }  
27:  };  

33. Search in Rotated Sorted Array

The key here is to check is the interval [lo, hi] is rotated or not. If it is rotated, there are two cases:

Case 1: nums[lo] > nums[mid]
In this case, the right part of nums[mid] must be sorted. If the target is in sorted part, we make the search interval to be the sorted part. Otherwise, we make the search interval to be the rotated part.

Case 2: nums[mid] > nums[hi]
In this case, the left part of nums[mid] must be sorted. Then do as Case 1.

By dealing with case 1 and case 2 above, we'll eventually make the target into a sorted search interval. And in this interval, we just search as normal binary search.

1:  class Solution {  
2:  public:  
3:    int search(vector<int>& nums, int target) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo <= hi) {  
6:        int mid = lo + (hi - lo) / 2;  
7:        if (nums[mid] == target) return mid;  
8:        if (nums[lo] > nums[mid]) {  
9:          // there is rotation, the right part of mid is sorted  
10:          if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;  
11:          else hi = mid - 1;  
12:        } else if (nums[hi] < nums[mid]) {  
13:          // there is rotation, the left part of mid is sorted  
14:          if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;  
15:          else lo = mid + 1;  
16:        } else {  
17:          // there is no rotation  
18:          if (target > nums[mid]) lo = mid + 1;  
19:          else hi = mid - 1;  
20:        }  
21:      }  
22:      return -1;  
23:    }  
24:  };  

78. Subsets

Classic backtracking solution.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> subsets(vector<int>& nums) {  
4:      vector<vector<int>> res;  
5:      vector<int> sol;  
6:      res.push_back(sol);  
7:      helper(nums, 0, sol, res);  
8:      return res;  
9:    }  
10:    void helper(vector<int>& nums, int start, vector<int> &sol, vector<vector<int>> &res) {  
11:      if (start == nums.size()) return;  
12:      for (int i = start; i< nums.size(); i++) {  
13:        sol.push_back(nums[i]);  
14:        res.push_back(sol);  
15:        helper(nums, i+1, sol, res);  
16:        sol.pop_back();  
17:      }  
18:    }  
19:  };  

331. Verify Preorder Serialization of a Binary Tree

The idea behind is, once we find a valid leaf node, we turn the leaf node into a NULL so that the problem becomes if its parent is a valid leaf node.  Since it's a bottom to top solution, we need stack for assistance. We keep searching for valid leaf node from bottom until the root becomes NULL and we are sure that it is a correct serialization. Otherwise, it is an incorrect serialization.

1:  class Solution {  
2:  public:  
3:    bool isValidSerialization(string preorder) {  
4:      stack<string> stk;  
5:      int i = 0;  
6:      preorder += ",";  
7:      while (i < preorder.size()) {  
8:        int j = i;  
9:        while (preorder[j] != ',') j++;  
10:        string val = preorder.substr(i, j-i);  
11:        i = j+1;  
12:        if (val != "#") {  
13:          stk.push(val);  
14:        } else {  
15:          while (!stk.empty() && stk.top() == "#") {  
16:            stk.pop();  
17:            if (stk.empty()) return false;  
18:            stk.pop();  
19:          }  
20:          stk.push(val);  
21:        }  
22:      }  
23:      return stk.size() == 1 && stk.top() == "#";  
24:    }  
25:  };  

When I revisited this problem, I found a more concise solution but a bit slower because of line 10. Also I missed line 14 in first place. It is important to check the stack before popping or topping anything from the stack.

1:  class Solution {  
2:  private:  
3:    stack<string> stk;  
4:  public:  
5:    bool isValidSerialization(string preorder) {  
6:      preorder += ',';  
7:      while (!preorder.empty()) {  
8:        int j = preorder.find(',');  
9:        string s = preorder.substr(0, j);  
10:        preorder = preorder.substr(++j);  
11:        if (s == "#") {  
12:          while (!stk.empty() && stk.top() == "#") {  
13:            stk.pop();  
14:            if (stk.empty()) return false;  
15:            stk.pop();  
16:          }  
17:        }  
18:        stk.push(s);  
19:      }  
20:      return stk.size() == 1 && stk.top() == "#";  
21:    }  
22:  };  

274. H-Index

I was thinking of scanning from the end and choose citations[i] if citations[i] >= n-i. However it turns out wrong. For example [100], the citation should be 1 instead of 100. The right way is to scan from the beginning and choose (n-i) as citation.

1:  class Solution {  
2:  public:  
3:    int hIndex(vector<int>& citations) {  
4:      sort(citations.begin(), citations.end());  
5:      int h = 0, n = citations.size();  
6:      for (int i = 0; i < n; i++) {  
7:        if (citations[i] >= n-i) {  
8:          h = n-i;  
9:          break;  
10:        }  
11:      }  
12:      return h;  
13:    }  
14:  };  

When I revisited this problem, I found a better explanation of the algorithm. If you sort the citations and put it into a graph, where x-axis represents the paper index and y-axis represents the citations. So, from the graph, the H-Index is length of the maximum square that in the histogram.

284. Peeking Iterator

This is a good problem to evaluate C++ knowledge.
A derived class can inherit public and protected member from base class except private member.
In this problem, PeekingIterator constructor calls Iterator constructor to store and initialize data. All the data will be stored in private member "data" of Iterator so I don't have to create a new member to hold the data but simply call the API from the base class.
To call the public member of base class, I need to use base::public_member.

1:  class PeekingIterator : public Iterator {  
2:  // Below is the interface for Iterator, which is already defined for you.  
3:  // **DO NOT** modify the interface for Iterator.  
4:      lass Iterator {  
5:    struct Data;  
6:        Data* data;  
7:  public:  
8:      Iterator(const vector<int>& nums);  
9:      Iterator(const Iterator& iter);  
10:      virtual ~Iterator();  
11:      // Returns the next element in the iteration.  
12:      int next();  
13:      // Returns true if the iteration has more elements.  
14:      bool hasNext() const;  
15:  };  
16:  public:  
17:      PeekingIterator(const vector<int>& nums) : Iterator(nums) {  
18:        // Initialize any member here.  
19:        // **DO NOT** save a copy of nums and manipulate it directly.  
20:        // You should only use the Iterator interface methods.  
21:      }  
22:    // Returns the next element in the iteration without advancing the iterator.  
23:      int peek() {  
24:      return Iterator(*this).next();  
25:      }  
26:      // hasNext() and next() should behave the same as in the Iterator interface.  
27:      // Override them if needed.  
28:      int next() {  
29:        return Iterator::next();  
30:      }  
31:      bool hasNext() const {  
32:        return Iterator::hasNext();  
33:      }  
34:  };  

When I revisited the code and found the solution above is actually not a good one in interview. Here is how Google Guava does.

1:  // Below is the interface for Iterator, which is already defined for you.  
2:  // **DO NOT** modify the interface for Iterator.  
3:  class Iterator {  
4:    struct Data;  
5:      Data* data;  
6:  public:  
7:      Iterator(const vector<int>& nums);  
8:      Iterator(const Iterator& iter);  
9:      virtual ~Iterator();  
10:      // Returns the next element in the iteration.  
11:      int next();  
12:      // Returns true if the iteration has more elements.  
13:      bool hasNext() const;  
14:  };  
15:  class PeekingIterator : public Iterator {  
16:  private:  
17:    bool peeked;  
18:    int peekedElement;  
19:  public:  
20:      PeekingIterator(const vector<int>& nums) : Iterator(nums) {  
21:        // Initialize any member here.  
22:        // **DO NOT** save a copy of nums and manipulate it directly.  
23:        // You should only use the Iterator interface methods.  
24:        peeked = false;  
25:      }  
26:    // Returns the next element in the iteration without advancing the iterator.  
27:      int peek() {  
28:      peekedElement = peeked ? peekedElement : Iterator::next();  
29:      peeked = true;  
30:      return peekedElement;  
31:      }  
32:      // hasNext() and next() should behave the same as in the Iterator interface.  
33:      // Override them if needed.  
34:      int next() {  
35:        peekedElement = peeked ? peekedElement : Iterator::next();  
36:        peeked = false;  
37:        return peekedElement;  
38:      }  
39:      bool hasNext() const {  
40:        return peeked || Iterator::hasNext();  
41:      }  
42:  };  

73. Set Matrix Zeroes

To solve it in place, I'll use the first row and first column to record the 0s.

1:  class Solution {  
2:  public:  
3:    void setZeroes(vector<vector<int>>& matrix) {  
4:      int rows = matrix.size();  
5:      int cols = matrix[0].size();  
6:      bool col0 = true, row0 = true;  
7:      for (int i = 0; i < rows; i++) {  
8:        if (matrix[i][0] == 0) {  
9:          col0 = false;  
10:          break;  
11:        }  
12:      }  
13:      for (int j = 0; j < cols; j++) {  
14:        if (matrix[0][j] == 0) {  
15:          row0 = false;  
16:          break;  
17:        }  
18:      }  
19:      for (int i = 0; i < rows; i++) {  
20:        for (int j = 0; j < cols; j++) {  
21:          if (matrix[i][j] == 0) {  
22:            matrix[i][0] = 0;  
23:            matrix[0][j] = 0;  
24:          }  
25:        }  
26:      }  
27:      for (int i = 1; i < rows; i++) {  
28:        if (matrix[i][0] == 0) {  
29:          for (int j = 1; j < cols; j++) {  
30:            matrix[i][j] = 0;  
31:          }  
32:        }  
33:      }  
34:      for (int j = 1; j < cols; j++) {  
35:        if (matrix[0][j] == 0) {  
36:          for (int i = 1; i < rows; i++) {  
37:            matrix[i][j] = 0;  
38:          }  
39:        }  
40:      }  
41:      if (!col0) {  
42:        for (int i = 0; i < rows; i++) {  
43:          matrix[i][0] = 0;  
44:        }  
45:      }  
46:      if (!row0) {  
47:        for (int j = 0; j < cols; j++) {  
48:          matrix[0][j] = 0;  
49:        }  
50:      }  
51:    }  
52:  };  

80. Remove Duplicates from Sorted Array II

Maintain two pointers. One is to scan every elements from position 2 and the other keeps the end position for the valid array.

1:  class Solution {  
2:  public:  
3:    int removeDuplicates(vector<int>& nums) {  
4:      if (nums.size() < 3) return nums.size();  
5:      int end = 2;  
6:      for (int i = 2; i < nums.size(); i++) {  
7:        if (nums[i] != nums[end-1] || nums[i] != nums[end-2]) {  
8:          swap(nums[i], nums[end]);  
9:          end++;  
10:        }  
11:      }  
12:      return end;  
13:    }  
14:  };  

When I revisited this problem, I had a bit more concise way.

1:  class Solution {  
2:  public:  
3:    int removeDuplicates(vector<int>& nums) {  
4:      if (nums.size() < 3) return nums.size();  
5:      int i, j;  
6:      for (i = 2, j = 2; j < nums.size(); i++, j++) {  
7:        if (nums[i-2] != nums[j]) swap(nums[i], nums[j]);  
8:        else i--;   
9:      }  
10:      return i;  
11:    }  
12:  };  

35. Search Insert Position

A typical binary search solution. But need to be careful about the boundary.

1:  class Solution {  
2:  public:  
3:    int searchInsert(vector<int>& nums, int target) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo <= hi) {  
6:        int mid = lo + (hi - lo) / 2;  
7:        if (target == nums[mid]) return mid;  
8:        else if (target > nums[mid]) lo = mid + 1;  
9:        else hi = mid-1;  
10:      }  
11:      return lo;  
12:    }  
13:  };  

289. Game of Life

My naive way is to create a new matrix to compute the updated board. And then dump the values from the new matrix to the board.

1:  class Solution {  
2:  public:  
3:    void gameOfLife(vector<vector<int>>& board) {  
4:      int rows = board.size();  
5:      int cols = board[0].size();  
6:      vector<vector<int>> res(rows, vector<int>(cols, 0));  
7:      for (int i = 0; i < rows; i++) {  
8:        for (int j = 0; j < cols; j++) {  
9:          int lives = 0;  
10:          for (int ii = max(0, i-1); ii <= min(rows-1, i+1); ii++) {  
11:            for (int jj = max(0, j-1); jj <= min(cols-1, j+1); jj++) {  
12:              if ((ii != i || jj != j) && board[ii][jj] == 1) lives++;  
13:            }  
14:          }  
15:          if (lives < 2 || lives > 3) res[i][j] = 0;  
16:          else if (lives == 3) res[i][j] = 1;  
17:          else res[i][j] = board[i][j];  
18:        }  
19:      }  
20:      for (int i = 0; i < rows; i++) {  
21:        for (int j = 0; j < cols; j++) {  
22:          board[i][j] = res[i][j];  
23:        }  
24:      }  
25:    }  
26:  };  

The top voted solution updates the board in position. Since the life in the board is actually just one bit. We can use the second bit for the update state and make a one right shift to get the updated board.

1:  class Solution {  
2:  public:  
3:    void gameOfLife(vector<vector<int>>& board) {  
4:      int row = board.size();  
5:      if (row == 0) return;  
6:      int col = board[0].size();  
7:      if (col == 0) return;  
8:      vector<pair<int,int>> dir = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};  
9:      for (int i = 0; i < row; i++) {  
10:        for (int j = 0; j < col; j++) {  
11:          int lives = 0;  
12:          for (int d = 0; d < dir.size(); d++) {  
13:            int ii = i + dir[d].first;  
14:            int jj = j + dir[d].second;  
15:            if (ii < 0 || ii == row || jj < 0 || jj == col) continue;  
16:            if ((board[ii][jj] & 0x1) == 1) lives++;  
17:          }  
18:          if ((board[i][j] & 0x1)== 0 && lives == 3) {  
19:            board[i][j] |= 0x2;  
20:          } else if (lives == 2 || lives == 3) {  
21:            board[i][j] |= board[i][j] << 1;  
22:          }  
23:        }  
24:      }  
25:      for (int i = 0; i < row; i++) {  
26:        for (int j = 0; j < col; j++) {  
27:          board[i][j] >>= 1;  
28:        }  
29:      }  
30:    }  
31:  };  

74. Search a 2D Matrix

Binary search for candidate row first and binary search in that row.

1:  class Solution {  
2:  public:  
3:    bool searchMatrix(vector<vector<int>>& matrix, int target) {  
4:      int rows = matrix.size(), cols = matrix[0].size();  
5:      int row = 0, col = 0;  
6:      int lo = 0, hi = rows-1;  
7:      while (lo <= hi) {  
8:        int mid = lo + (hi - lo) / 2;  
9:        if (target == matrix[mid][0]) return true;  
10:        else if (target > matrix[mid][0]) {  
11:          lo = mid + 1;  
12:        } else {  
13:          hi = mid - 1;  
14:        }  
15:      }  
16:      if (lo == 0) return false;  
17:      row = lo-1;  
18:      lo = 0; hi = cols-1;  
19:      while (lo <= hi) {  
20:        int mid = lo + (hi - lo) / 2;  
21:        if (target == matrix[row][mid]) return true;  
22:        else if (target > matrix[row][mid]) {  
23:          lo = mid + 1;  
24:        } else {  
25:          hi = mid - 1;  
26:        }  
27:      }  
28:      return false;  
29:    }  
30:  };  

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:  };  

215. Kth Largest Element in an Array

A naive solution will be sort the array and return the (k-1)th number.
However, my intuition is the set up the heap for this array and pop out k-1 times.

1:  class Solution {  
2:  public:  
3:    int findKthLargest(vector<int>& nums, int k) {  
4:      priority_queue<int> pq(nums.begin(), nums.end());  
5:      for (int i = 0; i < k - 1; i++)  
6:        pq.pop();   
7:      return pq.top();  
8:    }  
9:  };  

I revisited the quicksort algorithm and found it is very useful for this problem. We just need to focus on the left partition which is less than the pivot. When the left partition size reaches nums.size()-k, the pivot is the kth largest number. Well. the OJ time seems slower than the heap algorithm. But I believe in general it is faster than the heap which is O(NlogN).

1:  class Solution {  
2:  public:  
3:    int findKthLargest(vector<int>& nums, int k) {  
4:      k = nums.size() - k;  
5:      int lo = 0;  
6:      int hi = nums.size()-1;  
7:      while (lo < hi) {  
8:        int j = partition(nums, lo, hi);  
9:        if (j == k) break;  
10:        else if (j < k) lo = j+1;  
11:        else hi = j-1;  
12:      }  
13:      return nums[k];  
14:    }  
15:    int partition(vector<int> &nums, int lo, int hi) {  
16:      int i = lo;  
17:      int j = hi+1;  
18:      while (1) {  
19:        while (i < hi && nums[++i] < nums[lo]);  
20:        while (j > lo && nums[--j] > nums[lo]);  
21:        if (i >= j) break;  
22:        swap(nums[i], nums[j]);  
23:      }  
24:      swap(nums[j], nums[lo]);  
25:      return j;  
26:    }  
27:  };  

129. Sum Root to Leaf Numbers

When I first saw this problem, I was thinking of constructing a DFS algorithm that every time I need to compute the depth of the left child and its sum as well as the depth of the right child and its sum. For current node, the sum will be the 10^left_depth + left_sum + 10^right_depth + right_sum. This is a bottom-to-top way and turns out not working well. Then I think of the top-to-bottom way. The function will take the sum from the parent and compute the sum at current node, pass the sum to its left and right children and sum up the sum of left and right children.

1:  class Solution {  
2:  public:  
3:    int sumNumbers(TreeNode* root) {  
4:      return helper(root, 0);  
5:    }  
6:    int helper(TreeNode* root, int val) {  
7:      if (root == NULL) return 0;  
8:      val = 10*val + root->val;  
9:      if (root->left == NULL && root->right == NULL) {  
10:        return val;  
11:      }  
12:      return helper(root->left, val)+helper(root->right, val);  
13:    }  
14:  };  

240. Search a 2D Matrix II

Let i be the row index starting from 0 and j be the column index starting from matrix[0].size()-1.
The invariant is if target is less than matrix[i][j], then it won't be in column j (because elements in column j following row i is larger than the target), so we can move j one backward. Similarly, if target is larger than matrix[i][j], then it won't be in row i, so we can move i one forward.

1:  class Solution {  
2:  public:  
3:    bool searchMatrix(vector<vector<int>>& matrix, int target) {  
4:      int i = 0, j = matrix[0].size() - 1;  
5:      while (i < matrix.size() && j >= 0) {  
6:        if (matrix[i][j] == target) return true;  
7:        else if (matrix[i][j] > target) j--;  
8:        else i++;  
9:      }  
10:      return false;  
11:    }  
12:  };  

75. Sort Colors

My intuition is to use count sort. The running time will be O(2n)

1:  class Solution {  
2:  public:  
3:    void sortColors(vector<int>& nums) {  
4:      vector<int> colors(3, 0);  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        colors[nums[i]]++;  
7:      }  
8:      int k = 0;  
9:      for (int i = 0; i < 3; i++) {  
10:        for (int j = 0; j < colors[i]; j++) {  
11:          nums[k++] = i;  
12:        }  
13:      }  
14:    }  
15:  };  

Top voted solution is as following. Do note while loops and their order.

1:  class Solution {  
2:  public:  
3:    void sortColors(vector<int>& nums) {  
4:      int blue = nums.size()-1, red = 0;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        while (nums[i] == 2 && i < blue) swap(nums[i], nums[blue--]);   
7:        while (nums[i] == 0 && i > red) swap(nums[i], nums[red++]);  
8:      }  
9:    }  
10:  };  

48. Rotate Image

Image clockwise 90 degree rotation can be done by two steps:
1. swap elements along right diagonal
2. swap elements in vertical symmetry.

1:  class Solution {  
2:  public:  
3:    void rotate(vector<vector<int>>& matrix) {  
4:      for (int i = 0; i < matrix.size(); i++) {  
5:        for (int j = i+1; j < matrix[0].size(); j++) {  
6:          swap(matrix[i][j], matrix[j][i]);  
7:        }  
8:      }  
9:      for (int i = 0; i < matrix.size(); i++) {  
10:        for (int j = 0; j < matrix[0].size()/2; j++) {  
11:          swap(matrix[i][j], matrix[i][matrix[0].size()-j-1]);  
12:        }  
13:      }  
14:    }  
15:  };  

199. Binary Tree Right Side View

First of all, my solution takes level-order traversal (BFS).

1:  class Solution {  
2:  public:  
3:    vector<int> rightSideView(TreeNode* root) {  
4:      vector<int> res;  
5:      vector<TreeNode*> cur;  
6:      if (root == NULL) return res;  
7:      cur.push_back(root);  
8:      while (!cur.empty()) {  
9:        vector<TreeNode*> next;  
10:        for (int i = 0; i < cur.size(); i++) {  
11:          if (cur[i]->left) next.push_back(cur[i]->left);  
12:          if (cur[i]->right) next.push_back(cur[i]->right);  
13:        }  
14:        res.push_back(cur[cur.size()-1]->val);  
15:        cur = next;  
16:      }  
17:      return res;  
18:    }  
19:  };  

Top voted uses DFS, i.e. traverse right child first and then left right. Save value only when current output size is less than level size.

1:  class Solution {  
2:  public:  
3:    vector<int> rightSideView(TreeNode* root) {  
4:      vector<int> res;  
5:      helper(root, 1, res);  
6:      return res;  
7:    }  
8:    void helper(TreeNode *root, int level, vector<int> &res) {  
9:      if (root == NULL) return;  
10:      if (res.size() < level) {  
11:        res.push_back(root->val);  
12:      }  
13:      helper(root->right, level+1, res);  
14:      helper(root->left, level+1, res);  
15:      return;  
16:    }  
17:  };  

59. Spiral Matrix II

Only need some math.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> generateMatrix(int n) {  
4:      int i = 0, k = 1;  
5:      vector<vector<int>> res(n, vector<int>(n, 0));  
6:      while (k <= n*n) {  
7:        int j = i;  
8:        while (j < n - i) {  
9:          res[i][j++] = k++;  
10:        }  
11:        j = i+1;  
12:        while (j < n - i) {  
13:          res[j++][n-i-1] = k++;  
14:        }  
15:        j = n - i - 2;  
16:        while (j > i) {  
17:          res[n-i-1][j--] = k++;  
18:        }  
19:        j = n - i - 1;  
20:        while (j > i) {  
21:          res[j--][i] = k++;  
22:        }  
23:        i++;  
24:      }  
25:      return res;  
26:    }  
27:  };  

There is a better way to solve this problem, same as problem "54. Spiral Matrix"

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> generateMatrix(int n) {  
4:      vector<vector<int>> res(n, vector<int>(n, 0));  
5:      int rowBegin = 0, colBegin = 0;  
6:      int rowEnd = n-1, colEnd = n-1;  
7:      int k = 1;  
8:      while (rowBegin <= rowEnd) {  
9:        for (int j = colBegin; j <= colEnd; j++) res[rowBegin][j] = k++;  
10:        rowBegin++;  
11:        for (int i = rowBegin; i <= rowEnd; i++) res[i][colEnd] = k++;  
12:        colEnd--;  
13:        if (rowBegin <= rowEnd) {  
14:          for (int j = colEnd; j >= colBegin; j--) res[rowEnd][j] = k++;  
15:        }  
16:        rowEnd--;  
17:        if (colBegin <= colEnd) {  
18:          for (int i = rowEnd; i >= rowBegin; i--) res[i][colBegin] = k++;  
19:        }  
20:        colBegin++;  
21:      }  
22:      return res;  
23:    }  
24:  };  

241. Different Ways to Add Parentheses

The key is to treat each operator as the last one to process, divide the problem into two problems, i.e. get the left and right results around the operator, and then iterate the left and right results to conquer the final solution. Also, don't forget if there is no operator, we need to atoi the string. This is a very important step to make the divide and conquer method work.

1:  class Solution {  
2:  public:  
3:    vector<int> diffWaysToCompute(string input) {  
4:      vector<int> res;  
5:      for (int i = 0; i < input[i]; i++) {  
6:        if (input[i] < '0' || input[i] > '9') {  
7:          vector<int> left = diffWaysToCompute(input.substr(0, i));  
8:          vector<int> right = diffWaysToCompute(input.substr(i+1));  
9:          for (int l = 0; l < left.size(); l++) {  
10:            for (int r = 0; r < right.size(); r++) {  
11:              if (input[i] == '+') res.push_back(left[l] + right[r]);  
12:              else if (input[i] == '-') res.push_back(left[l] - right[r]);  
13:              else if (input[i] == '*') res.push_back(left[l] * right[r]);  
14:            }  
15:          }  
16:        }  
17:      }  
18:      if (res.empty()) {  
19:        res.push_back(atoi(input.c_str()));  
20:      }  
21:      return res;  
22:    }  
23:  };  

116. Populating Next Right Pointers in Each Node

My simple solution as following:

1:  class Solution {  
2:  public:  
3:    void connect(TreeLinkNode *root) {  
4:      while (root) {  
5:        TreeLinkNode *q = root;  
6:        while (q && q->left) {  
7:          q->left->next = q->right;  
8:          if (q->next) q->right->next = q->next->left;  
9:          q = q->next;  
10:        }  
11:        root = root->left;  
12:      }  
13:      return;  
14:    }  
15:  };  

Here is the DFS solution which also meets the requirement of constant space.

1:  /**  
2:   * Definition for binary tree with next pointer.  
3:   * struct TreeLinkNode {  
4:   * int val;  
5:   * TreeLinkNode *left, *right, *next;  
6:   * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    void connect(TreeLinkNode *root) {  
12:      if (root == NULL || root->left == NULL) return;  
13:      TreeLinkNode *cur = root, *prev = NULL;  
14:      while (cur) {  
15:        cur->left->next = cur->right;  
16:        if (prev != NULL) prev->next = cur->left;  
17:        prev = cur->right;  
18:        cur = cur->next;  
19:      }  
20:      connect(root->left);  
21:    }  
22:  };