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

108. Convert Sorted Array to Binary Search Tree

Well, not much to say. 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:    TreeNode* sortedArrayToBST(vector<int>& nums) {  
13:      int n = nums.size();  
14:      return helper(nums, 0, n-1);  
15:    }  
16:    TreeNode *helper(vector<int> &nums, int s, int e) {  
17:      if (s > e) return NULL;  
18:      int mid = s + (e - s) / 2;  
19:      TreeNode *node = new TreeNode(nums[mid]);  
20:      node->left = helper(nums, s, mid-1);  
21:      node->right = helper(nums, mid+1, e);  
22:      return node;  
23:    }  
24:  };  

339. Nested List Weight Sum

The problem requires a depth so I intuitively think of DFS. And yes, DFS works fine with this problem. The idea is loop through the input list, check if it is an integer. If so, add the integer to the sum. If not, recursively call itself and add the returned value to the sum. After I'm done with the loop, return the sum.

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:  public:  
20:    int depthSum(vector<NestedInteger>& nestedList) {  
21:      return helper(nestedList, 1);  
22:    }  
23:    int helper(vector<NestedInteger> &nestedList, int d) {  
24:      int sum = 0;  
25:      for (int i = 0; i < nestedList.size(); i++) {  
26:        if (nestedList[i].isInteger()) sum += d * nestedList[i].getInteger();  
27:        else sum += helper(nestedList[i].getList(), d+1);  
28:      }  
29:      return sum;  
30:    }  
31:  };  

113. Path Sum II

Don't forget line 24.

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:      if (root->left == NULL && root->right == NULL) {  
21:        if (sum == root->val) {  
22:          sol.push_back(root->val);  
23:          res.push_back(sol);  
24:          sol.pop_back();  
25:        }  
26:        return;  
27:      }  
28:      sol.push_back(root->val);  
29:      helper(root->left, sum-root->val, sol, res);  
30:      helper(root->right, sum-root->val, sol, res);  
31:      sol.pop_back();  
32:    }  
33:  };  

124. Binary Tree Maximum Path Sum

The idea is very similar to maximum subarray sum problem where a dp array is used to store the local maximal subarray sum at position i, and a global maximal subarray sum variable is updated as the final result. For this problem, we also need to keep the local maximal path and the global maximal path. The following code is what I did in first place.

However, this piece of code is wrong. The helper function returns not the maximal sum on a path (i.e. left->root, or right->root) but the maximal sum for the whole 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:  private:  
12:    int maxSum = INT_MIN;  
13:  public:  
14:    int maxPathSum(TreeNode* root) {  
15:      helper(root);  
16:      return maxSum;  
17:    }  
18:    int helper(TreeNode *root) {  
19:      if (root == NULL) return 0;  
20:      int prevMax = helper(root->left);
21:      int postMax = helper(root->right);
22:      int val = max(root->val+prevMax, max(root->val+postMax, max(root->val+prevMax+postMax, root->val)));  
23:      if (root->val > val) val = root->val;  
24:      maxSum = max(val, maxSum);  
25:      return val;  
26:    }  
27:  };  

So I modified the code and eventually got the right 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:  private:  
12:    int maxSum = INT_MIN;  
13:  public:  
14:    int maxPathSum(TreeNode* root) {  
15:      helper(root);  
16:      return maxSum;  
17:    }  
18:    int helper(TreeNode *root) {  
19:      if (root == NULL) return 0;  
20:      int prevMax = helper(root->left);  
21:      int postMax = helper(root->right);  
22:      int val = max(root->val+prevMax, max(root->val+postMax, max(root->val+prevMax+postMax, root->val)));  
23:      maxSum = max(val, maxSum);  
24:      return max(root->val+prevMax, max(root->val+postMax, root->val));  
25:    }  
26:  };  

322. Coin Change

This is a classic dynamic programming problem. If you don't know the problem before, it will be tricky. Let dp[i] be the minimal change for amount i. We should try from 1 to the target amount such that should a coin amount be less or equal to i, dp[i] = min(dp[i], dp[i-coins[j]]+1), i.e. the minimal change for amount i will be the minimal change at i-coins[j] plus 1.

1:  class Solution {  
2:  public:  
3:    int coinChange(vector<int>& coins, int amount) {  
4:      vector<int> dp(amount+1, INT_MAX-1);  
5:      dp[0] = 0;  
6:      for (int i = 1; i <= amount; i++) {  
7:        for (int j = 0; j < coins.size(); j++) {  
8:          if (coins[j] <= i) {  
9:            dp[i] = min(dp[i], dp[i-coins[j]]+1);  
10:          }  
11:        }  
12:      }  
13:      return dp[amount] == INT_MAX-1 ? -1 : dp[amount];  
14:    }  
15:  };  

167. Two Sum II - Input array is sorted

Not much to say. An easy two pointers solution with O(N) running time. Of course, it can be solved by binary search but it may cost NlogN running time.

1:  class Solution {  
2:  public:  
3:    vector<int> twoSum(vector<int>& numbers, int target) {  
4:      int l = 0, r = numbers.size()-1;  
5:      while (l < r) {  
6:        int sum = numbers[l] + numbers[r];  
7:        if (sum == target) break;  
8:        else if (sum < target) l++;  
9:        else r--;  
10:      }  
11:      return vector<int>{l+1, r+1};  
12:    }  
13:  };  

379. Design Phone Directory

I was thinking to build up a hash table for every number in the construction function. However, it turns out too costly. Actually, I only needs to have two arrays, with one storing numbers and another storing used tag. The idea behind is that we really don't have to care about the order of number that we dispensed and even who got the number. So don't think over too much. It's a very simple design.

1:  class PhoneDirectory {  
2:  private:  
3:    vector<int> numbers;  
4:    vector<bool> used;  
5:    int front;  
6:    int maxNumbers;  
7:  public:  
8:    /** Initialize your data structure here  
9:      @param maxNumbers - The maximum numbers that can be stored in the phone directory. */  
10:    PhoneDirectory(int maxNumbers) {  
11:      this->maxNumbers = maxNumbers;  
12:      numbers = vector<int>(maxNumbers, 0);  
13:      used = vector<bool>(maxNumbers, false);  
14:      front = 0;  
15:      for (int i = 0; i < maxNumbers; i++) {  
16:        numbers[i] = i;  
17:      }  
18:    }  
19:    /** Provide a number which is not assigned to anyone.  
20:      @return - Return an available number. Return -1 if none is available. */  
21:    int get() {  
22:      if (front == maxNumbers) return -1;  
23:      int ret = numbers[front++];  
24:      used[ret] = true;  
25:      return ret;  
26:    }  
27:    /** Check if a number is available or not. */  
28:    bool check(int number) {  
29:      if (number < 0 || number > maxNumbers-1) return false;  
30:      return !used[number];  
31:    }  
32:    /** Recycle or release a number. */  
33:    void release(int number) {  
34:      if (number >= 0 && number < maxNumbers && used[number]) {  
35:        numbers[--front] = number;  
36:        used[number] = false;  
37:      }  
38:    }  
39:  };  
40:  /**  
41:   * Your PhoneDirectory object will be instantiated and called as such:  
42:   * PhoneDirectory obj = new PhoneDirectory(maxNumbers);  
43:   * int param_1 = obj.get();  
44:   * bool param_2 = obj.check(number);  
45:   * obj.release(number);  
46:   */  

377. Combination Sum IV

I don’t have any clue when I first saw this problem. I followed the top rated solution. The solution has similary idea with problem "322. Coin Change". The idea is to let dp[i] to be the maximal combinations for target i. Note only when nums[j] <= target, nums[j] is a candidate for the combination and the number of combinations with this candidate nums[j] is dp[target-nums[j]]. And also for the target, we need to sum up all the combinations with candidates nums[j] less or equal than the target, so we have
dp[i] = sum of dp[i-nums[j]] where nums[j] <= i.

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

378. Kth Smallest Element in a Sorted Matrix

I tried a way of moving two pointers from top left/bottom right corner but found it is not able to solve the problem. Then I followed the top rated solution to solve the problem by minimal heap.
The idea is to push the numbers of first row into the heap. The heap is ordered by the value of numbers. Once we pop out the top number, we need to find the next possible number. It will be  the number on next row in the same column with the popped number. Therefore, we need to append the position information to the number. So the code is as following:

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

266. Palindrome Permutation

I was thinking to traverse the buckets twice. First round is to count the number of each character. The second round is to count the number of odds. If odds is less than 2, return true. Otherwise, return false.
The top rated solution combine the two rounds into one round but actually the same running time.

1:  class Solution {  
2:  public:  
3:    bool canPermutePalindrome(string s) {  
4:      vector<int> chars(256, 0);  
5:      int odd = 0;  
6:      for (char c : s) {  
7:        odd += ++chars[c] & 1 ? 1 : -1;  
8:      }  
9:      return odd < 2;  
10:    }  
11:  };  

186. Reverse Words in a String II

This is similar to problem "151. Reverse Words in a String". The idea is the same, i.e. reverse all the string first and reverse each word in the string.

1:  class Solution {  
2:  public:  
3:    void reverseWords(string &s) {  
4:      reverse(s.begin(), s.end());  
5:      int i = 0, j = 0;  
6:      while (i < s.size()) {  
7:        while (i < s.size() && s[i] != ' ') i++;  
8:        reverse(s.begin()+j, s.begin()+i);  
9:        j = ++i;  
10:      }  
11:    }  
12:  };  

102. Binary Tree Level Order Traversal

Not much to say. BFS can be applied here. Here is the code.

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>> levelOrder(TreeNode* root) {  
13:      vector<vector<int>> res;  
14:      if (root == NULL) return res;  
15:      queue<TreeNode*> q;  
16:      q.push(root);  
17:      while (!q.empty()) {  
18:        int sz = q.size();  
19:        vector<int> level;  
20:        for (int i = 0; i < sz; i++) {  
21:          TreeNode *node = q.front();  
22:          q.pop();  
23:          level.push_back(node->val);  
24:          if (node->left) q.push(node->left);  
25:          if (node->right) q.push(node->right);  
26:        }  
27:        res.push_back(level);  
28:      }  
29:      return res;  
30:    }  
31:  };  

204. Count Primes

This is a dynamic problem. The minimal prime is 2. So we can start from 2 and we know that any multiple of 2 is a prime. So we mark off all multiple of 2. Then we check 3. Similarly, and multiple of 3 is not a prime so we mark off them. Now we come to 4. Since 4 is a multiple of 2 and has been marked off, we just ignore and continue to 5. Note, we don't have to start from 5*2 because 5*2, 5*3, 5*4 have all been marked off before. So we can start from 5*5. Therefore, the algorithm is as following:

1:  class Solution {  
2:  public:  
3:    int countPrimes(int n) {  
4:      vector<bool> isPrime(n, true);  
5:      for (int i = 2; i*i < n; i++) {  
6:        if (!isPrime[i]) continue;  
7:        for (int j = i*i; j < n; j += i) {  
8:          isPrime[j] = false;  
9:        }  
10:      }  
11:      int count = 0;  
12:      for (int i = 2; i < n; i++) {  
13:        if (isPrime[i]) count++;  
14:      }  
15:      return count;  
16:    }  
17:  };  

8. String to Integer (atoi)

This is "easy" for programming if you are clear about all possible cases. Need to get the requirment clarified from the interviewer. Anyway, here are the cases that OJ thinks of (I've added comments for the cases in the code).

1:  class Solution {  
2:  public:  
3:    int myAtoi(string str) {  
4:      int i = 0, n = str.size();  
5:      long long res = 0;  
6:      int sign = 1;  
7:      // ignore leading spaces  
8:      while (str[i] == ' ') i++;  
9:      // process leading sign  
10:      if (str[i] == '-') { sign = -1; i++; }  
11:      else if (str[i] == '+') { sign = 1; i++; }  
12:      while (i < n && isNum(str[i])) {  
13:        res = res*10 + str[i]-'0';  
14:        // process overflow;  
15:        if (sign == 1 && res > INT_MAX) return INT_MAX;  
16:        if (sign == -1 && -res < INT_MIN) return INT_MIN;  
17:        i++;  
18:      }  
19:      return res * sign;  
20:    }  
21:    bool isNum(char c) {  
22:      return c >= '0' && c <= '9';  
23:    }  
24:  };  

160. Intersection of Two Linked Lists

I count the number of the two lists first. And then I compute the offset and move the head pointer of the longer list to the offset. And from there compare the two lists and check the intersection.

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 *getIntersectionNode(ListNode *headA, ListNode *headB) {  
12:      int a = countList(headA);  
13:      int b = countList(headB);  
14:      int diff = 0;  
15:      if (a > b) {  
16:        diff = a - b;  
17:        while (diff) { headA = headA->next; diff--; }  
18:      } else {  
19:        diff = b - a;  
20:        while (diff) { headB = headB->next; diff--; }  
21:      }  
22:      while (headA != headB) {  
23:        headA = headA->next;  
24:        headB = headB->next;  
25:      }  
26:      return headA;  
27:    }  
28:    int countList(ListNode *head) {  
29:      int count = 0;  
30:      while (head) {  
31:        head = head->next;  
32:        count++;  
33:      }  
34:      return count;  
35:    }  
36:  };  

234. Palindrome Linked List

I count the total nodes first and then find the middle node. To cover both cases of odd/even number, the middle node should be the ceiling of n / 2. And then reverse the sublist starting from the middle node. After that, compare the first half list with the reversed second half list to see if any discrepancy.

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:    bool isPalindrome(ListNode* head) {  
12:      int count = countList(head);  
13:      if (count < 2) return true;  
14:      int mid = (count+1)/2;  
15:      ListNode *l2 = head;  
16:      while (mid) {  
17:        l2 = l2->next;  
18:        mid--;  
19:      }  
20:      l2 = reverseList(l2);  
21:      while (l2) {  
22:        if (head->val != l2->val) return false;  
23:        head = head->next;  
24:        l2 = l2->next;  
25:      }  
26:      return true;  
27:    }  
28:    int countList(ListNode *head) {  
29:      int count = 0;  
30:      while(head) {  
31:        count++;  
32:        head = head->next;  
33:      }  
34:      return count;  
35:    }  
36:    ListNode *reverseList(ListNode *head) {  
37:      ListNode *pre = NULL;  
38:      while (head) {  
39:        ListNode *next = head->next;  
40:        head->next = pre;  
41:        pre = head;  
42:        head = next;  
43:      }  
44:      return pre;  
45:    }  
46:  };  

21. Merge Two Sorted Lists

Well, this is a real easy one.

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* mergeTwoLists(ListNode* l1, ListNode* l2) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      ListNode *cur = dummy;  
14:      while (l1 && l2) {  
15:        if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; }  
16:        else { cur->next = l2; l2 = l2->next; }  
17:        cur = cur->next;  
18:      }  
19:      if (l1) cur->next = l1;  
20:      if (l2) cur->next = l2;  
21:      cur = dummy->next;  
22:      delete dummy;  
23:      return cur;  
24:    }  
25:  };  

141. Linked List Cycle

To find a cycle in the linked list, we can have two pointers, one of which moves one steps once and the other moves two steps once. If the fast pointer reaches NULL, it means there is no cycle, otherwise, the fast pointer will capture the slow pointer again.

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:    bool hasCycle(ListNode *head) {  
12:      if (head == NULL || head->next == NULL) return false;  
13:      ListNode *slow = head;  
14:      ListNode *fast = head->next;  
15:      while (fast && fast->next) {  
16:        slow = slow->next;  
17:        fast = fast->next->next;  
18:        if (slow == fast) return true;  
19:      }  
20:      return false;  
21:    }  
22:  };  

121. Best Time to Buy and Sell Stock

This is actually a maximum subarray sum problem which can be solved by Kadane’s Algorithm.
Here is a very good video explaining this algorithm:
https://www.youtube.com/watch?v=86CQq3pKSUw

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