419. Battleships in a Board

The key to solve this problem is the following two conditions:

- Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.

- At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

So the problem becomes something similar to counting islands where islands here is 'X's surrounded by '.'.

1:  class Solution {  
2:  public:  
3:    int countBattleships(vector<vector<char>>& board) {  
4:      int count = 0;  
5:      for (int i = 0; i < board.size(); i++) {  
6:        for (int j = 0; j < board[0].size(); j++) {  
7:          if (board[i][j] == 'X' && (i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X')) count++;  
8:        }  
9:      }  
10:      return count;  
11:    }  
12:  };  

403. Frog Jump

In first place, the solution can be done by recursion and is very straightforward. The tricky part is in line 9 because when gap is less than k, the frog has to jump over the stone as it only has choices of k-1, k and k+1.

1:  class Solution {  
2:  public:  
3:    bool canCross(vector<int>& stones) {  
4:      return canJump(stones, 0, 0);  
5:    }  
6:    bool canJump(vector<int> &stones, int pos, int k) {  
7:      for (int i = pos+1; i < stones.size(); i++) {  
8:        int gap = stones[i] - stones[pos];  
9:        if (gap < k - 1) continue; // the frog has to jump over the stone.  
10:        if (gap > k + 1) return false;  
11:        if (canJump(stones, i, gap, dp)) return true;  
12:      }  
13:      return pos == stones.size()-1;  
14:    }  
15:  };  

However, this solution gets TLE. So the memorization is used.

1:  class Solution {  
2:  public:  
3:    bool canCross(vector<int>& stones) {  
4:      set<pair<int,int>> dp;  
5:      return canJump(stones, 0, 0, dp);  
6:    }  
7:    bool canJump(vector<int> &stones, int pos, int k, set<pair<int,int>> &dp) {  
8:      if (dp.count(make_pair(pos, k))) return false;  
9:      for (int i = pos+1; i < stones.size(); i++) {  
10:        int gap = stones[i] - stones[pos];  
11:        if (gap < k - 1) continue; // the frog has to jump over the stone.  
12:        if (gap > k + 1) { dp.insert(make_pair(pos, k)); return false; }  
13:        if (canJump(stones, i, gap, dp)) { dp.insert(make_pair(pos, k)); return true; }  
14:      }  
15:      return pos == stones.size()-1;  
16:    }  
17:  };  

410. Split Array Largest Sum

I don't have clue in the first place, so I followed the top rated solution.
The idea is the minimized maximum sum among the subarrays must between the largest number in the array and the sum of the total array. So we should think of the binary search.
Once we think about the binary search, we need to find the validation condition. Given the mid number, the condition is invalid if there are more than m subarrays that have sum larger than mid number.

1:  class Solution {  
2:  public:  
3:    int splitArray(vector<int>& nums, int m) {  
4:      long long left = 0, right = 0;  
5:      for (n : nums) {  
6:        left = max(left, (long long)n);  
7:        right += n;  
8:      }  
9:      while (left < right) {  
10:        long long mid = (left + right) / 2;  
11:        if (isValid(nums, m, mid)) right = mid;  
12:        else left = mid + 1;  
13:      }  
14:      return left;  
15:    }  
16:    bool isValid(vector<int> &nums, int m, int maxSum) {  
17:      long long cur = 0;  
18:      int count = 0;  
19:      for (n : nums) {  
20:        cur += n;  
21:        if (cur > maxSum) {  
22:          cur = n, count++;  
23:          // you've got m subarrays that have sum larger than maxSum,  
24:          // so maxSum isn't a minimized sum among these subarrays.  
25:          if (count == m) return false;  
26:        }  
27:      }  
28:      return true;  
29:    }  
30:  };  

404. Sum of Left Leaves

Well, very straightforward solution.

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:    int sumOfLeftLeaves(TreeNode* root) {  
13:      if (root == NULL) return 0;  
14:      int sum = 0;  
15:      if (isLeaf(root->left)) sum += root->left->val + sumOfLeftLeaves(root->right);  
16:      else sum = sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);  
17:      return sum;  
18:    }  
19:    bool isLeaf(TreeNode *root) {  
20:      if (root == NULL) return false;  
21:      if (root->left == NULL && root->right == NULL) return true;  
22:      return false;  
23:    }  
24:  };  

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

417. Pacific Atlantic Water Flow

We should start from the boundary of the matrix to see if they can reach the other ocean. So it is a typical DSF problem. For DSF problem, we need to have a visited matrix. The trick here is right on the visited matrix. The value in visited matrix is no long bool now. It should use bit to represent the ocean. We can have 0b01 to be pacific and 0b10 to be atlantic. So only when visited becomes 0b11, we know the element is able to reach both oceans.

1:  class Solution {  
2:  private:  
3:    int rows, cols;  
4:    vector<pair<int,int>> res;  
5:    vector<vector<int>> visited;  
6:    vector<pair<int,int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
7:  public:  
8:    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {  
9:      if (matrix.empty()) return res;  
10:      rows = matrix.size(), cols = matrix[0].size();  
11:      visited = vector<vector<int>>(rows, vector<int>(cols, 0));  
12:      for (int i = 0; i < rows; i++) {  
13:        dfs(matrix, i, 0, INT_MIN, 1); // 1 is pacific  
14:        dfs(matrix, i, cols-1, INT_MIN, 2); // 2 is atlatic  
15:      }  
16:      for (int j = 0; j < cols; j++) {  
17:        dfs(matrix, 0, j, INT_MIN, 1);  
18:        dfs(matrix, rows-1, j, INT_MIN, 2);  
19:      }  
20:      return res;  
21:    }  
22:    void dfs(vector<vector<int>> &matrix, int i, int j, int prev, int ocean) {  
23:      if (i<0||j<0||i==rows||j==cols||matrix[i][j]<prev||(visited[i][j]&ocean)==ocean) return;  
24:      visited[i][j] |= ocean;  
25:      if (visited[i][j] == 3) res.push_back(make_pair(i, j));  
26:      for (int d = 0; d < dir.size(); d++) {  
27:        int ii = i + dir[d].first;  
28:        int jj = j + dir[d].second;  
29:        dfs(matrix, ii, jj, matrix[i][j], visited[i][j]);  
30:      }  
31:    }  
32:  };  

407. Trapping Rain Water II

I don't have any clue to solve the problem. I have to follow the top rated solution. The idea behind is
(1) Use minimum heap to store the height for most outer boarder and scan from the lowest height.
(2) For the top height in the heap (h1), we need to record the lowest height (it's the maxH in the code). (Why? Because it is the lowest height in the most out boundary, we expect it to grow only. If there is any height lower than current lowest height, it has trapped water.) If it has neighbor with lower height (h2), then the neighbor must be able to hold water (maxH - h2). Why? Because at this time the boundary has been updated and maxH is the lowest height so far, please see step (3).
(3) Mark the neighbor as visited and push it to the heap. Since the neighbor has been visited, the boundary is updated.
(4) repeat (2) - (3) until heap becomes empty.

1:  class Solution {  
2:  public:  
3:    int trapRainWater(vector<vector<int>>& heightMap) {  
4:      if (heightMap.empty()) return 0;  
5:      int rows = heightMap.size(), cols = heightMap[0].size();  
6:      priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;  
7:      vector<vector<bool>> visited(rows, vector<bool>(cols, false));  
8:      for (int i = 0; i < rows; i++) {  
9:        for (int j = 0; j < cols; j++) {  
10:          if (i == 0 || i == rows-1 || j == 0 || j == cols-1) {  
11:            q.push(make_pair(heightMap[i][j], i*cols+j));  
12:            visited[i][j] = true;  
13:          }  
14:        }  
15:      }  
16:      vector<pair<int,int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
17:      int res = 0, maxH = INT_MIN;  
18:      while (!q.empty()) {  
19:        int height = q.top().first;  
20:        int i = q.top().second / cols, j = q.top().second % cols;  
21:        q.pop();  
22:        maxH = max(maxH, height);  
23:        for (int d = 0; d < dir.size(); d++) {  
24:          int ii = i + dir[d].first;  
25:          int jj = j + dir[d].second;  
26:          if (ii < 0 || jj < 0 || ii == rows || jj == cols || visited[ii][jj]) continue;  
27:          visited[ii][jj] = true;  
28:          if (heightMap[ii][jj] < maxH) res += maxH - heightMap[ii][jj];  
29:          q.push(make_pair(heightMap[ii][jj], ii*cols+jj));  
30:        }  
31:      }  
32:      return res;  
33:    }  
34:  };  

409. Longest Palindrome

Very straightforward solution. Count the frequency for characters in the input string. If a character appears even times, it must be a part of palindrome. On the other hand, if a character appears odd times, then we want to add (odd times - 1). In the end, if there is odd time character, the return value should be added one.

1:  class Solution {  
2:  public:  
3:    int longestPalindrome(string s) {  
4:      unordered_map<char, int> mp;  
5:      for (c : s) mp[c]++;  
6:      int res = 0, odd = 0;  
7:      for (auto it : mp) {  
8:        if (it.second & 1) { res += it.second - 1, odd = 1; }  
9:        else res += it.second;  
10:      }  
11:      return res + odd;  
12:    }  
13:  };  

408. Valid Word Abbreviation

No trick. Pretty straightforward solution. Note when return, we need to check if we've reached both ends of word and it abbreviation.

1:  class Solution {  
2:  public:  
3:    bool validWordAbbreviation(string word, string abbr) {  
4:      int i = 0, j = 0;  
5:      while (i < word.size() && j < abbr.size()) {  
6:        if (!isNum(abbr[j])) {  
7:          if (word[i++] != abbr[j++]) return false;  
8:        } else {  
9:          if (abbr[j] == '0') return false;  
10:          int l = 0;  
11:          while (j < abbr.size() && isNum(abbr[j])) {  
12:            l = l * 10 + abbr[j++] - '0';  
13:          }  
14:          i += l;  
15:        }  
16:      }  
17:      return i == word.size() && j == abbr.size();  
18:    }  
19:    bool isNum(char c) {  
20:      return c >= '0' && c <= '9';  
21:    }  
22:  };  

399. Evaluate Division

I don't have clue to solve the problem. I followed one of the top rated solutions.
The idea is that each equation is a link of graph with value as weight on the link. Note the graph should be directed because given a/b=x it's easy to get b/a=1/x. Therefore, for a query a/c, it is to find a valid path that connects node a and c.

For example, a / b = 3.0, b / c = 2.0, the graph looks like:
a <==> b <==> c. So for query, a/c, the path exists and the value is 3.0 * 2.0 = 6.0. On the other hand, for query c/a, the path also exists and the value is 1 / 3* 1 / 2 = 1 / 6.

The path can be find by DFS. Note, to avoid loop, i.e. a / b * b / a = 1, we need to have a set to cache the visited node.

1:  class Solution {  
2:  public:  
3:    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {  
4:      unordered_map<string, unordered_map<string, double>> mp;  
5:      for (int i = 0; i < equations.size(); i++) {  
6:        mp[equations[i].first].insert(make_pair(equations[i].second, values[i]));  
7:        mp[equations[i].second].insert(make_pair(equations[i].first, 1 / values[i]));  
8:      }  
9:      vector<double> res;  
10:      for (auto q : queries) {  
11:        unordered_set<string> s;  
12:        double tmp = check(mp, q.first, q.second, s);  
13:        if (tmp) res.push_back(tmp);  
14:        else res.push_back(-1);  
15:      }  
16:      return res;  
17:    }  
18:    double check(unordered_map<string, unordered_map<string, double>> &mp, string up, string down, unordered_set<string> &s) {  
19:      if (mp[up].find(down) != mp[up].end()) return mp[up][down];  
20:      for (auto it : mp[up]) {  
21:        if (s.find(it.first) == s.end()) {  
22:          s.insert(it.first);  
23:          double tmp = check(mp, it.first, down, s);  
24:          if (tmp) return it.second * tmp;  
25:        }  
26:      }  
27:      return 0;  
28:    }  
29:  };  

400. Nth Digit

The solution consists of three steps:
- find the length of number that the Nth digit comes from
- find the number that contains Nth digit
- find the Nth digit

Note the variable "count" must be long because "count *= 10" could make it overflow.

1:  class Solution {  
2:  public:  
3:    int findNthDigit(int n) {  
4:      int len = 1;  
5:      long count = 9;  
6:      int start = 1;  
7:      while (n > len * count) {  
8:        n -= len * count;  
9:        len++;  
10:        count *= 10;  
11:        start *= 10;  
12:      }  
13:      start += (n - 1) / len;  
14:      string s = to_string(start);  
15:      return s[(n-1) % len] - '0';  
16:    }  
17:  };  

389. Find the Difference

The naive way is to sort the two strings and find the different character. The code is very straightforward.

1:  class Solution {  
2:  public:  
3:    char findTheDifference(string s, string t) {  
4:      sort(s.begin(), s.end());  
5:      sort(t.begin(), t.end());  
6:      int i = 0;  
7:      for (; i < s.size(); i++) {  
8:        if (s[i] != t[i]) break;  
9:      }  
10:      return t[i];  
11:    }  
12:  };  

However, this problem is actually equivalent to the problem of "136. Single Number".

1:  class Solution {  
2:  public:  
3:    char findTheDifference(string s, string t) {  
4:      char res = 0;  
5:      for (c : s) res ^= c;  
6:      for (c : t) res ^= c;  
7:      return res;  
8:    }  
9:  };  

401. Binary Watch

The idea behind is to enumerate all possible combinations and count the bit of 1. If the bits number matches the input, then output the time.

1:  class Solution {  
2:  public:  
3:    vector<string> readBinaryWatch(int num) {  
4:      vector<string> res;  
5:      for (int h = 0; h < 12; h++) {  
6:        for (int m = 0; m < 60; m++) {  
7:          if (countBits((h << 6) | m) == num) {  
8:            res.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));  
9:          }  
10:        }  
11:      }  
12:      return res;  
13:    }  
14:    int countBits(int n) {  
15:      int count = 0;  
16:      while (n) {  
17:        n &= n-1;  
18:        count++;  
19:      }  
20:      return count;  
21:    }  
22:  };  

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

394. Decode String

One way to solve the problem is DFS. But the trick is the input index. The index must be reference (or pointer) because it should be continuous to the function call in the stack.

1:  class Solution {  
2:  public:  
3:    string decodeString(string s) {  
4:      int i = 0;  
5:      return helper(s, i);  
6:    }  
7:    string helper(string s, int &i) {  
8:      string res;  
9:      while (i < s.size() && s[i] != ']') {  
10:        if (!isDigit(s[i])) res += s[i++];  
11:        else {  
12:          int n = 0;  
13:          while (i < s.size() && isDigit(s[i])) n = n * 10 + s[i++] - '0';  
14:          i++; // '['  
15:          string t = helper(s, i);  
16:          i++; // ']'  
17:          for (int j = 0; j < n; j++) res += t;  
18:        }  
19:      }  
20:      return res;  
21:    }  
22:    bool isDigit(char c) {  
23:      return c >= '0' && c <= '9';  
24:    }  
25:  };  

393. UTF-8 Validation

The idea is count bytes first and validate the following bytes.

1:  class Solution {  
2:  public:  
3:    bool validUtf8(vector<int>& data) {  
4:      int c = 0;  
5:      for (int d : data) {  
6:        if (c == 0) {  
7:          if ((d >> 7) == 0) c = 0;  
8:          else if ((d >> 5) == 0b110) c = 1;  
9:          else if ((d >> 4) == 0b1110) c = 2;  
10:          else if ((d >> 3) == 0b11110) c = 3;  
11:          else return false;  
12:        } else {  
13:          if ((d >> 6) != 0b10) return false;  
14:          c--;  
15:        }  
16:      }  
17:      return c == 0;  
18:    }  
19:  };  

388. Longest Absolute File Path

This problem has long long description and the file path is very confusing at the first glance. However, if you read the path carefully, you'll find that '\t' indicates the depth of a directory or file and '\n' indicates the end of the directory or file. Also you should notice that the file in the path appears one by one, so the solution becomes to have an array to store the length for each depth and once reaches a file, compute the total length to the file. After computing a file, everything can be reset to start finding a new file.

1:  class Solution {  
2:  public:  
3:    int lengthLongestPath(string input) {  
4:      int maxL = 0, l = 1, len = 0;  
5:      bool isFile = false;  
6:      vector<int> level(1, 0);  
7:      for (int i = 0; i < input.size(); i++) {  
8:        while (input[i] == '\t') {  
9:          l++, i++;  
10:        }  
11:        while (input[i] != '\n' && i < input.size()) {  
12:          if (input[i] == '.') isFile = true;  
13:          len++, i++;  
14:        }  
15:        if (isFile) {  
16:          maxL = max(maxL, level[l-1]+len);  
17:        } else {  
18:          if (l == level.size()) level.push_back(level[l-1]+len+1);  
19:          else level[l] = level[l-1] + len + 1;  
20:        }  
21:        len = 0, l = 1, isFile = false;  
22:      }  
23:      return maxL;  
24:    }  
25:  };  

67. Add Binary

Very straightforward solution. I think the little challenge is the make the code clean and clever.

1:  class Solution {  
2:  public:  
3:    string addBinary(string a, string b) {  
4:      string s = "";  
5:      int c = 0, i = a.size()-1, j = b.size()-1;  
6:      while (i >= 0 || j >= 0 || c == 1) {  
7:        c += i >= 0 ? a[i--] - '0' : 0;  
8:        c += j >= 0 ? b[j--] - '0' : 0;  
9:        char t = c % 2 + '0';  
10:        s = t + s;  
11:        c /= 2;  
12:      }  
13:      return s;  
14:    }  
15:  };  

283. Move Zeroes

Simple two pointers problem. We can have two pointers i and j. i is pointing to the next element in the array to check and j is pointing to the first 0 position. So for example [0, 0, 0, 1, 2]
1st round, i = 0, j = 0: 0, 0, 0, 1, 2
2nd round, i = 1, j = 0: 0, 0, 0, 1, 2
3rd round, i = 2, j = 0: 0, 0, 0, 1, 2
4th round, i = 3, j = 0: 1, 0, 0, 0, 2
5th round, i = 4, j = 1, 1, 2, 0, 0, 0

Another example, [1, 0, 3]
1st round, i = 0, j = 0: 1, 0, 3
2nd round, i = 1, j = 1: 1, 0, 3
3rd round, i = 2, j = 1: 1, 3, 0

1:  class Solution {  
2:  public:  
3:    void moveZeroes(vector<int>& nums) {  
4:      int i = 0, j = 0;  
5:      while (i < nums.size()) {  
6:        if (nums[i] == 0) {  
7:          i++;  
8:        } else {  
9:          swap(nums[i++], nums[j++]);  
10:        }  
11:      }  
12:    }  
13:  };  

333. Largest BST Subtree

I can use the way that "98. Validate Binary Search Tree" does to validate if the root is a valid BST root. If it is, then just count the node in the BST. Otherwise, do the same to its left subtree and right subtree.

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:    int largestBSTSubtree(TreeNode* root) {  
13:      if (root == NULL) return 0;  
14:      if (root->left == NULL && root->right == NULL) return 1;  
15:      if (isValidBST(root, NULL, NULL)) return count(root);  
16:      return max(largestBSTSubtree(root->left), largestBSTSubtree(root->right));  
17:    }  
18:    bool isValidBST(TreeNode *root, TreeNode *pre, TreeNode *suc) {  
19:      if (root == NULL) return true;  
20:      if (pre && root->val <= pre->val) return false;  
21:      if (suc && root->val >= suc->val) return false;  
22:      return isValidBST(root->left, pre, root) && isValidBST(root->right, root, suc);  
23:    }  
24:    int count(TreeNode *root) {  
25:      if (root == NULL) return 0;  
26:      if (root->left == NULL && root->right == NULL) return 1;  
27:      return 1 + count(root->left) + count(root->right);  
28:    }  
29:  };  

The solution above is a top-down one. The top rated solution which follows a down-top way runs at O(n) time since each node only need to be visited once. Will investigate later.

372. Super Pow

I don’t have any clue. This is completely a math problem. I have to follow the top rated solution.

1:  class Solution {  
2:  private:  
3:    const int k = 1337;  
4:    int powmod(int a, int b) {  
5:      // (a^b)%k = (a^(b-1)*a)%k = (a^(b-1)%k)*(a%k)%k  
6:      int res = 1;  
7:      a %= k;  
8:      for (int i = 0; i < b; i++) {  
9:        res = res * a % k;  
10:      }  
11:      return res;  
12:    }  
13:  public:  
14:    int superPow(int a, vector<int>& b) {  
15:      // ab % k = (a%k)(b%k)%k  
16:      // a^123 % k = (a^120*a^3) % k = (a^120%k)(a^3%k)%k  
17:      if (b.empty()) return 1;  
18:      int last = b.back();  
19:      b.pop_back();  
20:      return powmod(superPow(a, b), 10) * powmod(a, last) % k;  
21:    }  
22:  };  

63. Unique Paths II

Same solution with problem “62. Unique Paths”. The only difference is the initial state.

1:  class Solution {  
2:  public:  
3:    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {  
4:      int rows = obstacleGrid.size();  
5:      if (rows == 0) return 0;  
6:      int cols = obstacleGrid[0].size();  
7:      vector<vector<int>> dp(rows, vector<int>(cols, 0));  
8:      for (int j = 0; j < cols; j++) {  
9:        if (obstacleGrid[0][j] == 1) break;  
10:        dp[0][j] = 1;  
11:      }  
12:      for (int i = 0; i < rows; i++) {  
13:        if (obstacleGrid[i][0] == 1) break;  
14:        dp[i][0] = 1;  
15:      }  
16:      for (int i = 1; i < rows; i++) {  
17:        for (int j = 1; j < cols; j++) {  
18:          if (obstacleGrid[i][j] == 0) {  
19:            dp[i][j] = dp[i-1][j]+dp[i][j-1];  
20:          }  
21:        }  
22:      }  
23:      return dp[rows-1][cols-1];  
24:    }  
25:  };  

267. Palindrome Permutation I

The trick here as the hint says is we only need to track the first half string. So we need to count the number for the first half string. Also, we need to keep the middle character if the string has an odd length. And finally, we need to use hashtable to store each character’s count. After that, the problem becomes a classic backtracking permutation problem.

I used vector as hash table in first place. But I got TLE. I guess it’s too cost to check for 256 characters every time. Also when doing unordered_map, the iterator it in the loop “for (auto it : mp)” is a copy not the real iterator itself. So if you update this copy, it doesn’t change the content of the unordered_map at all. So we need to do either “for (auto &it : mp)” or “for (auto it=mp.begin(); it != mp.end(); i++)”.

1:  class Solution {  
2:  public:  
3:    vector<string> generatePalindromes(string s) {  
4:      unordered_map<char, int> mp;  
5:      vector<string> res;  
6:      for (int i = 0; i < s.size(); i++) {  
7:        mp[s[i]]++;  
8:      }  
9:      int odd = 0, len = 0;  
10:      string mid = "";  
11:      for (auto it = mp.begin(); it != mp.end(); it++) {  
12:        if (it->second & 1) { odd++; mid += it->first; }  
13:        it->second /= 2;  
14:        len += it->second;  
15:      }  
16:      if (odd > 1) return res;  
17:      gen(mp, len, mid, "", res);  
18:      return res;  
19:    }  
20:    void gen(unordered_map<char, int> &mp, int len, string &mid, string s, vector<string> &res) {  
21:      if (s.size() == len) {  
22:        string r = s;  
23:        reverse(r.begin(), r.end());  
24:        res.push_back(s+mid+r);  
25:        return;  
26:      }  
27:      for (auto it = mp.begin(); it != mp.end(); it++) {  
28:        if (it->second > 0) {  
29:          it->second--;  
30:          gen(mp, len, mid, s+it->first, res);  
31:          it->second++;  
32:        }  
33:      }  
34:    }  
35:  };  

161. One Edit Distance

I was thinking of DP, but it turns out quite straightforward. See the comments in the code.

1:  class Solution {  
2:  public:  
3:    bool isOneEditDistance(string s, string t) {  
4:      int ns = s.size();  
5:      int nt = t.size();  
6:      int n = min(ns, nt);  
7:      for (int i = 0; i < n; i++) {  
8:        if (s[i] != t[i]) {  
9:          if (ns == nt) return s.substr(i+1) == t.substr(i+1); // replace s[i] with t[i]  
10:          else if (ns < nt) return s.substr(i) == t.substr(i+1); // delete t[i]  
11:          else return s.substr(i+1) == t.substr(i); // delete s[i]  
12:        }  
13:      }  
14:      return abs(ns-nt) == 1; // one character long otherwise two strings are equal.  
15:    }  
16:  };  

227. Basic Calculator II

The difference with problem "224. Basic Calculator" is that this problem contains '*' and '/' operator but no parenthesis. We can use stack to solve this problem. Stack stores all the numbers that need to sum up. So when we meet '+', we simply push the number into stack. When we meet '-', we simply push the negative number into the stack. When we meet '*' or '/' which has high priority, we only need to pop the top number out of the stack, operate on it and push it back to stack. With this operation, the stack will store all the numbers that need to sum up only.

1:  class Solution {  
2:  public:  
3:    int calculate(string s) {  
4:      char sign = '+';  
5:      int num = 0;  
6:      stack<int> stk;  
7:      for (int i = 0; i < s.size(); i++) {  
8:        if (s[i] >= '0' && s[i] <= '9') {  
9:          num = num*10+s[i]-'0';  
10:        }  
11:        if (((s[i] < '0' || s[i] > '9') && (s[i] != ' ')) || i == s.size()-1) {  
12:          if (sign == '+') stk.push(num);  
13:          else if (sign == '-') stk.push(-num);  
14:          else if (sign == '*') {num *= stk.top(); stk.pop(); stk.push(num);}  
15:          else if (sign == '/') {num = stk.top()/num; stk.pop(); stk.push(num);}  
16:          sign = s[i];  
17:          num = 0;  
18:        }  
19:      }  
20:      int res = 0;  
21:      while (!stk.empty()) {  
22:        res += stk.top();  
23:        stk.pop();  
24:      }  
25:      return res;  
26:    }  
27:  };  

88. Merge Sorted Array

The tricky part is we need to start from the end of arrays such that the largest will be allocated in the end.

1:  class Solution {  
2:  public:  
3:    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {  
4:      int i = m-1;  
5:      int j = n-1;  
6:      int k = m+n-1;  
7:      while (i >= 0 && j >= 0) {  
8:        if (nums1[i] > nums2[j]) {  
9:          nums1[k--] = nums1[i--];  
10:        } else {  
11:          nums1[k--] = nums2[j--];  
12:        }  
13:      }  
14:      while (j >= 0) nums1[k--] = nums2[j--];  
15:    }  
16:  };  

198. House Robber

Let dp[i] be the maximal treasure the thief can steel in house i. So the state transition is dp[i] = max(dp[i-1], nums[i-2]+nums[i]). The initial state will be dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

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

244. Shortest Word Distance II

My first impression is the hash table. The key value pair is (word, index). Since there could be duplicate words, the index should be a vector. Then the problem becomes to find shortest distance in two sorted vector. We can have two pointers. Everytime, we move the pointer who points to a smaller index.

1:  class WordDistance {  
2:  private:  
3:    unordered_map<string, vector<int>> mp;   
4:  public:  
5:    WordDistance(vector<string>& words) {  
6:      for (int i = 0; i < words.size(); i++) {  
7:        mp[words[i]].push_back(i);  
8:      }  
9:    }  
10:    int shortest(string word1, string word2) {  
11:      int i = 0, j = 0, dist = INT_MAX;  
12:      int sz1 = mp[word1].size(), sz2 = mp[word2].size();  
13:      while (i < sz1 && j < sz2) {  
14:        dist = min(dist, abs(mp[word1][i]-mp[word2][j]));  
15:        mp[word1][i] < mp[word2][j] ? i++ : j++;  
16:      }  
17:      return dist;  
18:    }  
19:  };  
20:  // Your WordDistance object will be instantiated and called as such:  
21:  // WordDistance wordDistance(words);  
22:  // wordDistance.shortest("word1", "word2");  
23:  // wordDistance.shortest("anotherWord1", "anotherWord2");  

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

376. Wiggle Subsequence

I was trapped in finding a DP solution that dp[i] means the longest wiggle subsequence so far at index i. However, I then realized two things: 1. The wiggle subsequence is not necessary to be consecutive; 2. [2,1] is a wiggle and [1,2] is a wiggle too. So I can’t solve it by something like Kadane’s algorithm. I followed the top rated solution which uses two dp arrays and runs at O(n^2) because subsequence is not required to be consecutive.

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

275. H-Index II

Same as problem "274. H-Index".

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

201. Bitwise AND of Numbers Range

I brute force the problem in first place but I got TLE. Then I had to look at the problem closely. Look at 7,8,9,10,11,12,13,14 which have binary representation 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110. You'll find that the smallest number cancels the largest number's more significant bits.  And also, the adjacent number cancels the least significant bits which means, as long as a number is larger than the other, the least significant bit will get cancelled. So we can keep moving the least significant bits out and recall the function itself recursively until the two numbers are equal. The rest bits that the two equal number shares will be the result.

1:  class Solution {  
2:  public:  
3:    int rangeBitwiseAnd(int m, int n) {  
4:      return n > m ? (rangeBitwiseAnd(m>>1, n>>1)<<1) : m;  
5:    }  
6:  };  

11. Container With Most Water

The idea is to compute the container from the widest to highest. Starting from two ends, we get the widest container's area. Then question is how we can get a container that has larger area? Since we are going to shrink the container's width, the only chance we can get a larger area is to have taller container such that height offsets the width. So we move the shorter end toward to the taller end with hoping to find a even taller end.

1:  class Solution {  
2:  public:  
3:    int maxArea(vector<int>& height) {  
4:      if (height.size() == 0) return 0;  
5:      int l = 0, r = height.size()-1, area = INT_MIN;  
6:      while (l < r) {  
7:        if (height[l] < height[r]) {  
8:          area = max(area, height[l] * (r-l));  
9:          l++;  
10:        } else {  
11:          area = max(area, height[r] * (r-l));  
12:          r--;  
13:        }  
14:      }  
15:      return area;  
16:    }  
17:  };  

64. Minimum Path Sum

Let dp[i][j] to be the minimum path sum at (i, j), then the transition state is dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

1:  class Solution {  
2:  public:  
3:    int minPathSum(vector<vector<int>>& grid) {  
4:      int row = grid.size();  
5:      if (row == 0) return 0;  
6:      int col = grid[0].size();  
7:      for (int j = 1; j < col; j++) {  
8:        grid[0][j] += grid[0][j-1];  
9:      }  
10:      for (int i = 1; i < row; i++) {  
11:        grid[i][0] += grid[i-1][0];  
12:      }  
13:      for (int i = 1; i < row; i++) {  
14:        for (int j = 1; j < col; j++) {  
15:          grid[i][j] += min(grid[i-1][j], grid[i][j-1]);  
16:        }  
17:      }  
18:      return grid[row-1][col-1];  
19:    }  
20:  };  

285. Inorder Successor in BST

It's very easy to miss the case that when we go into left subtree, current root become the successor.

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* inorderSuccessor(TreeNode* root, TreeNode* p) {  
13:      TreeNode *successor = NULL;  
14:      while (root) {  
15:        if (root->val == p->val) {  
16:          if (root->right == NULL) return successor;  
17:          else {  
18:            root = root->right;  
19:            while (root->left) root = root->left;  
20:            return root;  
21:          }  
22:        } else if (root->val < p->val) {  
23:          root = root->right;  
24:        } else {  
25:          successor = root;  
26:          root = root->left;  
27:        }  
28:      }  
29:      return NULL;  
30:    }  
31:  };  

254. Factor Combinations

Backtracking solution. A trick I played here is the scanning starts from last number of candidate solution to guarantee that the solution is in an ascending order and thus duplicate is avoided.

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

154. Find Minimum in Rotated Sorted Array II

The key for this problem is still that the minimum number must fall into the rotated part. However, there are duplicates in the array, so for case nums[mid] == nums[hi] or nums[mid] == nums[lo] we only move upper bound one step backward. Why upper bound? Because we are turning lower bound as the result.

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

62. Unique Paths

Let dp[i][j] is the maximum path at grid[i][j], so the transition statement is quite easy to achieve:
dp[i][j] = dp[i-1][j] + dp[i][j-1]. For the initial state, the first row and first column are initialized to all 1s.

1:  class Solution {  
2:  public:  
3:    int uniquePaths(int m, int n) {  
4:      vector<vector<int>> grid(m, vector<int>(n, 1));  
5:      for (int i = 1; i < m; i++) {  
6:        for (int j = 1; j < n; j++) {  
7:          grid[i][j] = grid[i-1][j] + grid[i][j-1];  
8:        }  
9:      }  
10:      return grid[m-1][n-1];  
11:    }  
12:  };  

255. Verify Preorder Sequence in Binary Search Tree

I was trying divide and conquer solution as following but got TLE.

1:  class Solution {  
2:  public:  
3:    bool verifyPreorder(vector<int>& preorder) {  
4:      if (preorder.empty()) return true;  
5:      return helper(preorder, 0, preorder.size()-1);  
6:    }  
7:    bool helper(vector<int> &preorder, int s, int e) {  
8:      if (s >= e) return true;  
9:      int pivot = preorder[s];  
10:      int bigger = -1;  
11:      for (int i = s+1; i <= e; i++) {  
12:        if (bigger == -1 && preorder[i] > pivot) bigger = i;  
13:        if (bigger != -1 && preorder[i] < pivot) return false;  
14:      }  
15:      if (bigger == -1) {  
16:        return helper(preorder, s+1, e);  
17:      } else {  
18:        return helper(preorder, s+1, bigger-1) && helper(preorder, bigger, e);  
19:      }  
20:    }  
21:  };  

Then I have to follow the top rated solution which uses stack. The idea is to traverse the list and use a stack to store all predecessors. As long as the stack's top node is less than the current list node, we can assume that the current list node is a predecessor and push it to the stack. Once we meet a node that is larger than the top node, we know we are going to enter the right subtree and we need to pop out all the predecessors that are less than current list node but keep the last predecessor. And then we push the current list node into stack and we enters the right subtree. Note for the right subtree, all the node must be larger than the last predecessor, if not then we conclude that it is an invalid preorder sequence in BST.

1:  class Solution {  
2:  public:  
3:    bool verifyPreorder(vector<int>& preorder) {  
4:      if (preorder.size() < 2) return true;  
5:      stack<int> stk;  
6:      stk.push(preorder[0]);  
7:      int last = INT_MIN;  
8:      for (int i = 1; i < preorder.size(); i++) {  
9:        if (stk.empty() || preorder[i] < stk.top()) {  
10:          if (preorder[i] < last) return false;  
11:          stk.push(preorder[i]);  
12:        } else {  
13:          while (!stk.empty() && stk.top() < preorder[i]) {  
14:            last = stk.top();  
15:            stk.pop();  
16:          }  
17:          stk.push(preorder[i]);  
18:        }  
19:      }  
20:      return true;  
21:    }  
22:  };  

250. Count Univalue Subtrees

Note every leaf is a uni-value subtree. We can check from bottom to top. Check the left child subtree and then the right child subtree. If one of them is not a uni-value subtree, the root can't be a uni-value subtree. Must the root be a uni-value subtree when and only when both left and right child subtrees are uni-value subtree and the root value is equal to its children's value. It is very easy to make a mistake in line 23. If we do something like "helper(root->left) && helper(root->right)", then we probably miss checking the right subtree when the left subtree becomes false.

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:  private:  
12:    int res;  
13:  public:  
14:    int countUnivalSubtrees(TreeNode* root) {  
15:      res = 0;  
16:      helper(root);  
17:      return res;  
18:    }  
19:    bool helper(TreeNode *root) {  
20:      if (root == NULL) return true;  
21:      bool r1 = helper(root->left);  
22:      bool r2 = helper(root->right);  
23:      if (r1 && r2) {  
24:        if (root->left && root->left->val != root->val) return false;  
25:        if (root->right && root->right->val != root->val) return false;  
26:        res++;  
27:        return true;  
28:      } else {  
29:        return false;  
30:      }  
31:    }  
32:  };  

137. Single Number II

The comment in the code explains the solution clearly.

1:  class Solution {  
2:  public:  
3:    int singleNumber(vector<int>& nums) {  
4:      int one = 0, two = 0, three = 0;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        two |= one & nums[i]; // get the bits that appears twice  
7:        one ^= nums[i]; // cancel the bits that appears twice  
8:        three = one & two; // get the bits that appears three times  
9:        one ^= three; // cancel the bits that appears three times  
10:        two ^= three; // cancel the bits that appears three times  
11:      }  
12:      return one;  
13:    }  
14:  };  

156. Binary Tree Upside Down

Postorder traversal and then construct the tree from downside to upside.

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* upsideDownBinaryTree(TreeNode* root) {  
13:      if (root == NULL) return root;  
14:      TreeNode *res = root;  
15:      while (res->left) res = res->left;  
16:      helper(root);  
17:      return res;  
18:    }  
19:    TreeNode *helper(TreeNode *root) {  
20:      if (root->left == NULL && root->right == NULL) return root;  
21:      TreeNode *nr = helper(root->left);  
22:      nr->left = root->right;  
23:      nr->right = root;  
24:      root->left = NULL;  
25:      root->right = NULL;  
26:      return root;  
27:    }  
28:  };  

325. Maximum Size Subarray Sum Equals k

When I saw this problem, my first impression is that it is similar to maximum subarray sum which can be solved by Kadane's algorithm. But this problem requires sum to be k. So, if we have sum[i] to be the sum from [0, i], the problem becomes to find all pairs of sum[i] == k or sum[i]-sum[j] == k. For sum[i] == k, the len is i+1, for sum[i]-sum[j] == k, the length is j - i. If we can save all sums before i in a hash table whose (key, value) pair is (sum, index), to get j which sum[i]-sum[j] == k, we only need to look up the hash table to see if sum[i]-k exists in it.

Note, since we scan from 0 to n, if sum[i] == k, the max length so far must be i+1. Also to avoid duplicates, we only save (sum, i) when this pair isn't existing in hash table. Why we don't have to save the pair (sum, j) later? Because we want to get the maximum size, the first pair guarantees it.

1:  class Solution {  
2:  public:  
3:    int maxSubArrayLen(vector<int>& nums, int k) {  
4:      unordered_map<int, int> mp;  
5:      int sum = 0, maxLen = 0;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        sum += nums[i];  
8:        if (k == sum) maxLen = i+1;  
9:        else if (mp.find(sum-k) != mp.end()) maxLen = max(maxLen, i-mp[sum-k]);  
10:        if (mp.find(sum) == mp.end()) mp[sum] = i;  
11:      }  
12:      return maxLen;  
13:    }  
14:  };  

94. Binary Tree Inorder Traversal

The idea is to keep pushing left child nodes into the stack. And pop out the top one, move the pointer to its right and then keep pushing left child nodes again.

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<int> inorderTraversal(TreeNode* root) {  
13:      stack<TreeNode*> stk;  
14:      TreeNode *p = root;  
15:      vector<int> res;  
16:      while (p || !stk.empty()) {  
17:        while (p) {  
18:          stk.push(p);  
19:          p = p->left;  
20:        }  
21:        p = stk.top();  
22:        stk.pop();  
23:        res.push_back(p->val);  
24:        p = p->right;  
25:      }  
26:      return res;  
27:    }  
28:  };  

319. Bulb Switcher

For each bulb at position i, it is only switched if the round r divides i. For any integer, the divisor comes in pairs, for example, 8 has divisor pairs of (1, 8), (2, 4) and eventually, bulb 8 will be off. Another example, 16 has divisor pairs (1, 16), (2, 8), (4, 4) and eventually bulb 16 will be on. So bulb i will be on if and only if when i has an integer square root. So the problem becomes how many such integers in [1, n]. Since sqrt(n) is largest square root and 1 is the smallest square root, so you have total sqrt(n) square roots in [1, n].

1:  class Solution {  
2:  public:  
3:    int bulbSwitch(int n) {  
4:      return sqrt(n);  
5:    }  
6:  };  

144. Binary Tree Preorder Traversal

Not much to say. Pretty straightforward.

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<int> preorderTraversal(TreeNode* root) {  
13:      stack<TreeNode *> stk;  
14:      vector<int> res;  
15:      if (root == NULL) return res;  
16:      stk.push(root);  
17:      while (!stk.empty()) {  
18:        TreeNode *t = stk.top();  
19:        stk.pop();  
20:        res.push_back(t->val);  
21:        if (t->right) stk.push(t->right);  
22:        if (t->left) stk.push(t->left);  
23:      }  
24:      return res;  
25:    }  
26:  };  

268. Missing Number

This idea comes from the problem of "136. Single Number", i.e. xor cancels the same number. So we can xor all the numbers from 0 to n first. And then xor the numbers in the input array. The remaining number must be the missing number.

1:  class Solution {  
2:  public:  
3:    int missingNumber(vector<int>& nums) {  
4:      int n = nums.size();  
5:      int res = 0;  
6:      for (int i = 0; i <= n; i++) {  
7:        res ^= i;  
8:      }  
9:      for (int i = 0; i < nums.size(); i++) {  
10:        res ^= nums[i];  
11:      }  
12:      return res;  
13:    }  
14:  };  

343. Integer Break

Let's first look at the case where an integer can be broken into two integers, so the product  = x(N-x). The maximal product is at x=N/2. Now let's see what integers need to break in order to achieve the largest product, i.e. (N/2)*(N/2) >= N => N >= 4. So the product must consists of factors that can't be broken. The largest non-break number is 3. However, there is a special case where 4 should be broken into 2*2 not 1*3. So the solution is as following in which line 8 and 12 take care of the special case.

1:  class Solution {  
2:  public:  
3:    int integerBreak(int n) {  
4:      if (n == 1) return 1;  
5:      if (n == 2) return 1;  
6:      if (n == 3) return 2;  
7:      int product = 1;  
8:      while (n > 4) {  
9:        product *= 3;  
10:        n -= 3;  
11:      }  
12:      product *= n;  
13:      return product;  
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:  };  

347. Top K Frequent Elements

Whenever the problem asks for top k numbers, it's highly likely to consider heap. This is a typical heap problem plus hash map. The hash map is used to count the frequency for each number the (key, value) pair is (number, frequency). After completing the hash map build, we build the minimal heap according the frequency. The node in heap is also a pair but this time it is (frequency, number) pair. Since we know that we only need to keep k numbers in the heap, so when the heap size is larger than k we pop out the top number. Finally, we dump all the numbers in the heap to the vector.

1:  class Solution {  
2:  public:  
3:    vector<int> topKFrequent(vector<int>& nums, int k) {  
4:      unordered_map<int, int> mp;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        mp[nums[i]]++;  
7:      }  
8:      priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;  
9:      for (auto p : mp) {  
10:        minHeap.push(make_pair(p.second, p.first));  
11:        if (minHeap.size() > k) {  
12:          minHeap.pop();  
13:        }  
14:      }  
15:      vector<int> res(k, 0);  
16:      for (int i = k-1; i >= 0; i--) {  
17:        res[i] = minHeap.top().second;  
18:        minHeap.pop();  
19:      }  
20:      return res;  
21:    }  
22:  };  

256. Paint House

Let costs[i][0] be the minimal cost for painting house i red, so we have costs[i][0] += min(costs[i-1][1], costs[i-1][2]). Same to blue and green.

1:  class Solution {  
2:  public:  
3:    int minCost(vector<vector<int>>& costs) {  
4:      int n = costs.size();  
5:      for (int i = 1; i < n; i++) {  
6:        costs[i][0] += min(costs[i-1][1], costs[i-1][2]);  
7:        costs[i][1] += min(costs[i-1][0], costs[i-1][2]);  
8:        costs[i][2] += min(costs[i-1][0], costs[i-1][1]);  
9:      }  
10:      return n == 0 ? 0 : min(costs[n-1][0], min(costs[n-1][1], costs[n-1][2]));  
11:    }  
12:  };  

382. Linked List Random Node

In first place, I don't have any clue. Then I followed the top rated solution which uses "reservoir sampling". Here is the wiki page for this algorithm: https://en.wikipedia.org/wiki/Reservoir_sampling.

For example, the list is 1->2->3.
1. First of all , we keep 1st node. in the list. The probability is 1.

2. We reach the 2nd node. We have two choices:
(1). keep the current node. Then the probability is 1/2
(2). discard the current node, keep the 2nd node. Then the probability is 1/2.

3. We reach the 3rd node. We have two choices:
(1). keep the current node. So the probability for discarding the 3rd node is 2/3. Since the current node could be 1st node or 2nd node, the probability for keeping the current node is 1/2*2/3 = 1/3.
(2). keep the 3rd node. So the probability is simply 1/3.

By introduction, it is easy to prove that when there is n nodes, each node is kept for probability 1/n. With this in mind, here is the 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:  private:  
11:    ListNode *head = NULL;  
12:  public:  
13:    /** @param head The linked list's head.  
14:      Note that the head is guaranteed to be not null, so it contains at least one node. */  
15:    Solution(ListNode* head) {  
16:      this->head = head;  
17:    }  
18:    /** Returns a random node's value. */  
19:    int getRandom() {  
20:      ListNode *cur = head->next;  
21:      ListNode *res = head;  
22:      for (int n = 2; cur != NULL; n++) {  
23:        if (rand() % n == 0) res = cur;  
24:        cur = cur->next;  
25:      }  
26:      return res->val;;  
27:    }  
28:  };  
29:  /**  
30:   * Your Solution object will be instantiated and called as such:  
31:   * Solution obj = new Solution(head);  
32:   * int param_1 = obj.getRandom();  
33:   */  

384. Shuffle an Array

The idea is, first of all, we draw a number out of the array, the probability for this number is 1/n, then the rest numbers have probability of (n-1)/n. Then we draw another number out of the rest n-1 numbers, so its probability is (n-1)/n * 1/(n-1) = 1/n. And we repeat this procedure until all the numbers have been drawn.

1:  class Solution {  
2:  private:  
3:    vector<int> nums;  
4:  public:  
5:    Solution(vector<int> nums) {  
6:      this->nums = nums;  
7:    }  
8:    /** Resets the array to its original configuration and return it. */  
9:    vector<int> reset() {  
10:      return nums;  
11:    }  
12:    /** Returns a random shuffling of the array. */  
13:    vector<int> shuffle() {  
14:      vector<int> res = nums;  
15:      int size = nums.size();  
16:      int i = 0;  
17:      while (size) {  
18:        int j = rand() % size;  
19:        swap(res[i], res[i+j]);  
20:        i++, size--;  
21:      }  
22:      return res;  
23:    }  
24:  };  
25:  /**  
26:   * Your Solution object will be instantiated and called as such:  
27:   * Solution obj = new Solution(nums);  
28:   * vector<int> param_1 = obj.reset();  
29:   * vector<int> param_2 = obj.shuffle();  
30:   */  

260. Single Number III

The idea is to get a mixed one first by xor all numbers. Then get the first bit 1 from the right to left in the mixed number which means that single1 differs single2 in that bit. And then scan the array again using this bit to differentiate single1 and single2.

1:  class Solution {  
2:  public:  
3:    vector<int> singleNumber(vector<int>& nums) {  
4:      int mixed = 0, single1 = 0, single2 = 0;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        mixed ^= nums[i];  
7:      }  
8:      int j = 1;  
9:      while ((mixed & j) == 0) j <<= 1;  
10:      for (int i = 0; i < nums.size(); i++) {  
11:        if (nums[i] & j) single1 ^= nums[i];  
12:      }  
13:      single2 = mixed ^ single1;  
14:      return vector<int>{single1, single2};  
15:    }  
16:  };  

245. Shortest Word Distance III

This is a follow up problem for "243. Shortest Word Distance". I only added line 11-13 which means if the two words are the same, i1 becomes the last appearance, i2 becomes the current appearance. The trick here is i1 and i2 are both initialized to -1. So for case ["a", "a"], word1="a" and word2 = "a", int first round loop, dist become 1. Note for two same words, the minimal distance is 1. So it is fine to have 1 in first round loop.

1:  class Solution {  
2:  public:  
3:    int shortestWordDistance(vector<string>& words, string word1, string word2) {  
4:      int dist = INT_MAX, i1 = -1, i2 = -1;  
5:      for (int i = 0; i < words.size(); i++) {  
6:        if (words[i] == word1) {  
7:          i1 = i;  
8:          if (i2 != -1) dist = min(dist, abs(i2-i1));  
9:        }  
10:        if (words[i] == word2) {  
11:          if (word1 == word2) {  
12:            i1 = i2;  
13:          }  
14:          i2 = i;  
15:          if (i1 != -1) dist = min(dist, abs(i2-i1));  
16:        }  
17:      }  
18:      return dist;  
19:    }  
20:  };  

243. Shortest Word Distance

Well, not much to say, a pretty straightforward solution.

1:  class Solution {  
2:  public:  
3:    int shortestDistance(vector<string>& words, string word1, string word2) {  
4:      int i1 = -1, i2 = -1, dist = INT_MAX;  
5:      for (int i = 0; i < words.size(); i++) {  
6:        if (words[i] == word1) {  
7:          i1 = i;  
8:          if (i2 != -1) dist = min(dist, abs(i2-i1));  
9:        }  
10:        if (words[i] == word2) {  
11:          i2 = i;  
12:          if (i1 != -1) dist = min(dist, abs(i2-i1));  
13:        }  
14:      }  
15:      return dist;  
16:    }  
17:  };  

311. Sparse Matrix Multiplication

For sparse matrix multiplication, we only need to operate on non zero numbers so that we can save a lot of time on unnecessary multiplications. Other than this, do the multiplication straightforward. Here is a better way to represent the sparse matrix and do the multiplication on it. I'll investigate later: http://www.cs.cmu.edu/~scandal/cacm/node9.html.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {  
4:      int rowA = A.size(), colB = B[0].size(), colA = A[0].size();  
5:      vector<vector<int>> res(rowA, vector<int>(colB, 0));  
6:      for (int i = 0; i < rowA; i++) {  
7:        for (int k = 0; k < colA; k++) {  
8:          if (A[i][k] != 0) {  
9:            for (int j = 0; j < colB; j++) {  
10:              if (B[k][j] != 0) res[i][j] += A[i][k]*B[k][j];  
11:            }  
12:          }  
13:        }  
14:      }  
15:      return res;  
16:    }  
17:  };  

136. Single Number

1 xor 1 = 0, 1 xor 0 = 1. So XOR operator will cancel a number if it appears twice. So this problem can be solve by xor all the numbers and the one left will be the one that appears once.

1:  class Solution {  
2:  public:  
3:    int singleNumber(vector<int>& nums) {  
4:      int single = 0;  
5:      for (int n : nums) {  
6:        single ^= n;  
7:      }  
8:      return single;  
9:    }  
10:  };  

338. Counting Bits

My intuition is to count bits for each number. So the total run time is O(32*n). However, if we look at binary representation closely,  "0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111", we'll see that once we reach a multiple of 2 say 2^n, its right bits just repeat all the numbers from 0 to 2^n-1. So we can program dynamically.

1:  class Solution {  
2:  public:  
3:    vector<int> countBits(int num) {  
4:      int shift = 0;  
5:      vector<int> res(num+1, 0);  
6:      int i = 1, j = 0;  
7:      while (i <= num) {  
8:        for (int j = 0; i <= num && j <(1<<shift); i++,j++) {  
9:          res[i] = res[j]+1;  
10:        }  
11:        shift++;  
12:      }  
13:      return res;  
14:    }  
15:  };  

71. Simplify Path

I don't have a clue in first place. But after looking at the tag "stack", then I got an idea. We can store each directory into a stack. Then I'll have following case:

1. directory is empty (i.e. consecutive slashes "///")or directory is ".", then we don't have to do anything.
2. directory is "..", then we need to pop out one directory. Note we need to check the stack is empty or not. If it's empty, we don't have to do anything.
3. Otherwise, we push the directory into the stack.

Since we eventually need to pop out the directories to form a new path but the stack is in reverse order, so we can use a vector to replace the stack so that we can traverse the vector from the beginning to the end.

1:  class Solution {  
2:  public:  
3:    string simplifyPath(string path) {  
4:      vector<string> dirs;  
5:      int i = 0, j = 0;  
6:      while (i < path.size()) {  
7:        while (i < path.size() && path[i] != '/') i++;  
8:        string dir = path.substr(j, i-j);  
9:        j = ++i;  
10:        if (dir == "" || dir == ".") continue;  
11:        if (dir == ".." && !dirs.empty()) dirs.pop_back();  
12:        else if (dir != "..") dirs.push_back(dir);  
13:      }  
14:      string res;  
15:      for (int i = 0; i < dirs.size(); i++) {  
16:        res += "/" + dirs[i];  
17:      }  
18:      return res.empty() ? "/" : res;  
19:    }  
20:  };  

366. Find Leaves of Binary Tree

I used hash map and DFS to solve this problem. Hash map is used to tag visited node. So the leaf becomes:
1. node->left == NULL && node->left == RIGHT
2. node->left == NULL && mp[node->right] = true
3. node->right == NULL && mp[node->left] = true
4. mp[node->left] == true && mp[node->right] == true

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:  private:  
12:    unordered_map<TreeNode*, bool> mp;  
13:  public:  
14:    vector<vector<int>> findLeaves(TreeNode* root) {  
15:      vector<vector<int>> res;  
16:      if (root == NULL) return res;  
17:      while (!mp[root]) {  
18:        vector<int> leaves;  
19:        helper(root, leaves, res);  
20:        res.push_back(leaves);  
21:      }  
22:      return res;  
23:    }  
24:    void helper(TreeNode *root, vector<int> &leaves, vector<vector<int>> &res) {  
25:      if (root->left == NULL && root->right == NULL || mp[root->left] && mp[root->right] ||  
26:        root->left == NULL && mp[root->right] || mp[root->left] && root->right == NULL) {  
27:        leaves.push_back(root->val);  
28:        mp[root] = true;  
29:        return;  
30:      }  
31:      if (root->left && !mp[root->left]) helper(root->left, leaves, res);  
32:      if (root->right && !mp[root->right]) helper(root->right, leaves, res);  
33:      return;  
34:    }  
35:  };  

There is another concise way to solve this problem. We can basically save the node by levels if we know the level.

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>> findLeaves(TreeNode* root) {  
13:      vector<vector<int>> res;  
14:      dfs(root, res);  
15:      return res;  
16:    }  
17:    int dfs(TreeNode* root, vector<vector<int>> &res) {  
18:      if (root == NULL) return 0;  
19:      int level = max(dfs(root->left, res), dfs(root->right, res)) + 1;  
20:      if (level > res.size()) res.push_back(vector<int>());  
21:      res[level-1].push_back(root->val);  
22:      return level;  
23:    }  
24:  };  

364. Nested List Weight Sum II

I made a mistake in first place where I was trying to get the maximum level for each nested list. This will get sum -2 for case [[-1], [[-1]]], which is wrong. We actually only need to get the maximum level once and pass the maximum level decreasingly down along the nested list.

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 Solution {  
19:  private:  
20:    int max_depth = 0;  
21:  public:  
22:    int depthSumInverse(vector<NestedInteger>& nestedList) {  
23:      depth(nestedList, 1);  
24:      return helper(nestedList, max_depth);  
25:    }  
26:    void depth(vector<NestedInteger> &nestedList, int d) {  
27:      max_depth = max(d, max_depth);  
28:      for (int i = 0; i < nestedList.size(); i++) {  
29:        if (!nestedList[i].isInteger()) depth(nestedList[i].getList(), d+1);  
30:      }  
31:    }  
32:    int helper(vector<NestedInteger> &nestedList, int d) {  
33:      int sum = 0;  
34:      for (int i = 0; i < nestedList.size(); i++) {  
35:        if (nestedList[i].isInteger()) sum += d * nestedList[i].getInteger();  
36:        else sum += helper(nestedList[i].getList(), d-1);  
37:      }  
38:      return sum;  
39:    }  
40:  };  

Memory Allocator

This question is asked in one of my phone interview. The question is "To  implement a memory allocator that allows multiple clients to allocate and free memory from a buffer". My initial thought is the maintain a front and rear pointer and make the buffer as a ring. However, such design doesn't satisfy the requirement because there are multiple users for example, user1 has requested buffer[0-3], user2 has requested buffer[4-6] and user3 has requested buffer[7]. When user2 releases his buffer before user3, you'll get a problem because of memory fragmentation. You can't simply move the front pointer back to 4 because it'll release user3's buffer which is being used currently. So I thought of the way how Linux kernel maintains the memory.  I'll need a pointer that maintains a list of free memory chunk. Yes, it is a linked list because of the memory fragmentation. When you request a piece of memory, you'll check the list to see if there is any memory fragment that has enough space for the request. If so, update the offset pointer for that node. Otherwise, return NULL pointer.

 #include <stdio.h>  
 #include <stdlib.h>  
 // To execute C, please define "int main()"  
 static char buffer[256];  
 struct LinkNode {  
  int start;  
  int end;  
  struct LinkNode *next;  
 };  
 static struct LinkNode *free_header = NULL;  
 void initFreeMemory();  
 void *allocate(int size);  
 int main() {  
  initFreeMemory();  
  printf("%p\n", buffer);  
  void *addr1 = allocate(3);  
  printf("%p\n", addr1);  
  void *addr2 = allocate(128);  
  printf("%p\n", addr2);  
  printf("%p\n", buffer+free_header->start);  
  return 0;  
 }  
 void initFreeMemory() {  
  free_header = (struct LinkNode *)malloc(sizeof(struct LinkNode));  
  free_header->start = 0;  
  free_header->end = 256;  
  free_header->next = NULL;  
 }  
 void *allocate(int size) {  
  struct LinkNode *p = free_header;  
  while (p) {  
   if (p->end - p->start >= size) break;  
   p = p->next;  
  }  
  if (p == NULL) return NULL;  
  void *ret = buffer+p->start;  
  p->start += size;  
  return ret;  
 }  
 /*void free(void *object) {  
  int size = sizeof(object);  
  struct LinkNode *node = malloc(sizeof(struct LinkNode));  
  node->start = object;  
  node->end = node->start + size;  
  free_header->next = node;  
 }*/  

269. Alien Dictionary

I didn't have any clue in first place. So I followed the top rated solution which uses a topology sort algorithm. I made mistakes in
line 12: I was thinking that all the words should follow the same rule pair by pair. So I did two for loops in first place. However, it seems not. This is a typical question that need to be clarified in an interview.
line 13-14: I didn't have these two rows in first place. However, it turns out to be critical otherwise you'll miss those isolated vertices nodes in the graph. For example "wrf" "e". If you don't have these two line, you'll miss "r" and "f" these two nodes.
line 11 & 15: the found variable is really needed. I broke out the second for loop once I found the first different letter in two words. However, that’ll miss the other present letters in the rest of two words.

1:  class Solution {  
2:  public:  
3:    string alienOrder(vector<string>& words) {  
4:      if (words.size() == 0) return "";  
5:      if (words.size() == 1) return words[0];  
6:      // build graph  
7:      unordered_map<char, set<char>> graph;  
8:      for (int i = 0; i+1 < words.size(); i++) {  
9:        string word1 = words[i];  
10:        string word2 = words[i+1];  
11:        bool found = false;  
12:        for (int j = 0; j < max(word1.size(), word2.size()); j++) {  
13:          if (j < word1.size() && graph.find(word1[j]) == graph.end()) graph[word1[j]] = set<char>();  
14:          if (j < word2.size() && graph.find(word2[j]) == graph.end()) graph[word2[j]] = set<char>();  
15:          if (j < word1.size() && j < word2.size() && word1[j] != word2[j] && !found) {  
16:            graph[word1[j]].insert(word2[j]);  
17:            found = true;  
18:          }  
19:        }  
20:      }  
21:      // start topology sort  
22:      vector<bool> visited(26, false);  
23:      vector<bool> path(26, false);  
24:      string res;  
25:      for (auto it = graph.begin(); it != graph.end(); it++) {  
26:        if (!visited[it->first-'a'] && hasCycle(graph, it->first, visited, path, res)) return "";  
27:      }  
28:      reverse(res.begin(), res.end());  
29:      return res;  
30:    }  
31:    bool hasCycle(unordered_map<char, set<char>> &graph, char c, vector<bool> &visited, vector<bool> &path, string &res) {  
32:      if (visited[c-'a']) return false;  
33:      visited[c-'a'] = path[c-'a'] = true;  
34:      for (auto it = graph[c].begin(); it != graph[c].end(); it++) {  
35:        if (path[*it-'a'] || hasCycle(graph, *it, visited, path, res)) return true;  
36:      }  
37:      path[c-'a'] = false;  
38:      res += c;  
39:      return false;  
40:    }  
41:  };  

104. Maximum Depth of Binary Tree

A classic DFS solution on tree again.

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:    int maxDepth(TreeNode* root) {  
13:      if (root == NULL) return 0;  
14:      return 1 + max(maxDepth(root->left), maxDepth(root->right));  
15:    }  
16:  };  

100. Same Tree

Well, very straightforward DFS solution.

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 isSameTree(TreeNode* p, TreeNode* q) {  
13:      if (p == NULL && q== NULL) return true;  
14:      if (p == NULL && q != NULL || p != NULL && q == NULL || p->val != q->val) return false;  
15:      return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);  
16:    }  
17:  };  

110. Balanced Binary Tree

Not much to say, a classic DFS solution on tree.

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 isBalanced(TreeNode* root) {  
13:      if (root == NULL) return true;  
14:      if (abs(depth(root->left) - depth(root->right)) > 1) return false;  
15:      return isBalanced(root->left) && isBalanced(root->right);  
16:    }  
17:    int depth(TreeNode *root) {  
18:      if (root == NULL) return 0;  
19:      return 1 + max(depth(root->left), depth(root->right));  
20:    }  
21:  };  

101. Symmetric Tree

Well, pretty straightforward DFS solution.

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 isSymmetric(TreeNode* root) {  
13:      if (root == NULL) return true;  
14:      return helper(root->left, root->right);  
15:    }  
16:    bool helper(TreeNode *p, TreeNode *q) {  
17:      if (p == NULL && q == NULL) return true;  
18:      if (p == NULL && q != NULL || p != NULL && q == NULL || p->val != q->val) return false;  
19:      return helper(p->left, q->right) && helper(p->right, q->left);  
20:    }  
21:  };  

112. Path Sum

Well, pretty straightforward DFS solution

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 hasPathSum(TreeNode* root, int sum) {  
13:      if (root == NULL) return false;  
14:      if (root->left == NULL && root->right == NULL) return sum == root->val;  
15:      return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);  
16:    }  
17:  };  

111. Minimum Depth of Binary Tree

I was computing the depth from bottom to top which means you’ll have many redundant calls because you call h times from the root to get the depth and you’ll call h-1 times again from the left child to a leaf. Actually the h-1 times can be avoided if we compute the depth from top to bottom.

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:  private:  
12:    int minD = INT_MAX;  
13:  public:  
14:    int minDepth(TreeNode* root) {  
15:      if (root == NULL) return 0;  
16:      helper(root, 1);  
17:      return minD;  
18:    }  
19:    void helper(TreeNode *root, int depth) {  
20:      if (root->left == NULL && root->right == NULL) { minD = min(minD, depth); return; }  
21:      if (root->left) helper(root->left, depth+1);  
22:      if (root->right) helper(root->right, depth+1);  
23:    }  
24:  };