46. Permutations

My solution will erase and insert elements in arrays which is slow.

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

A better way is to use the invariant that nums[0...begin] has been permuted.

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

337. House Robber III

The first way I tried intuitively is the recursive way.

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

However, this solution hits TLE. By looking into the solution, you'll see that for each root, we'll compute root->left->left once but we'll compute it in rob(root->left) again. So there is overlapped subproblems. To reduce the overlapping, we can memorize the subproblems' result. So the problem becomes DP.

1:  class Solution {  
2:  private:  
3:    unordered_map<TreeNode*, int> map;  
4:  public:  
5:    int rob(TreeNode* root) {  
6:      if (root == NULL) return 0;  
7:      if (map.find(root) != map.end()) return map[root];  
8:      int val = root->val;  
9:      if (root->left != NULL) {  
10:        val += rob(root->left->left) + rob(root->left->right);  
11:      }  
12:      if (root->right != NULL) {  
13:        val += rob(root->right->left) + rob(root->right->right);  
14:      }  
15:      int ret = max(val, rob(root->left)+rob(root->right));  
16:      map[root] = ret;  
17:      return ret;  
18:    }  
19:  };  

94. Binary Tree Inorder Traversal

Use stack. If current node is not NULL, then push its left child into the stack. Keep doing this until current node becomes NULL and then pop out the top node from the stack, save the value into result and move to the right child of the popped node.

1:  class Solution {  
2:  public:  
3:    vector<int> inorderTraversal(TreeNode* root) {  
4:      vector<int> res;  
5:      stack<TreeNode *> stk;  
6:      TreeNode *cur = root;  
7:      while (cur || !stk.empty()) {  
8:        if (cur) {  
9:          stk.push(cur);  
10:          cur = cur->left;  
11:        } else {  
12:          TreeNode *p = stk.top();  
13:          res.push_back(p->val);  
14:          stk.pop();  
15:          cur = p->right;  
16:        }  
17:      }  
18:      return res;  
19:    }  
20:  };  

230. Kth Smallest Element in a BST

My original solution is to traverse the tree in preorder and save the result in an array. Return the k-th number in the array.

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

Another way is to count the left nodes and use binary search to get the k-th number. However, this is not an optimal solution whose running time is O(NlogN). If we can modify augment the TreeNode data structure and keep track its left child numbers when building the tree, we can achieve the search by O(logN).

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 kthSmallest(TreeNode* root, int k) {  
13:      int c = countNodes(root->left);  
14:      if (c == k-1) return root->val;   
15:      if (c < k-1) {  
16:        return kthSmallest(root->right, k-c-1);  
17:      } else {  
18:        return kthSmallest(root->left, k);  
19:      }  
20:    }  
21:    int countNodes(TreeNode *root) {  
22:      if (root == NULL) return 0;  
23:      return 1 + countNodes(root->left) + countNodes(root->right);  
24:    }  
25:  };  

318. Maximum Product of Word Lengths

I used bucket to hash the letters in first place but I got the TLE.

1:  class Solution {  
2:  public:  
3:    int maxProduct(vector<string>& words) {  
4:      unordered_map<string, vector<int>> mp;  
5:      for (int i = 0; i < words.size(); i++) {  
6:        vector<int> bucket(26, 0);  
7:        for (int j = 0; j < words[i].size(); j++) {  
8:          bucket[words[i][j]-'a'] = 1;  
9:        }  
10:        mp[words[i]] = bucket;  
11:      }  
12:      int res = 0;  
13:      for (int i = 0; i < words.size(); i++) {  
14:        for (int j = i+1; j < words.size(); j++) {  
15:          int k = 0;  
16:          for (; k < 26; k++) {  
17:            if (mp[words[i]][k] && mp[words[j]][k]) break;  
18:          }  
19:          if (k == 26) res = max(res, (int)words[i].size() * (int)words[j].size());  
20:        }  
21:      }  
22:      return res;  
23:    }  
24:  };  

A trick here is the problem explicitly says that all letters in the words will be low case. Since there are 26 letters, we can use integer which has 32bits as a letter mask for each word.

1:  class Solution {  
2:  public:  
3:    int maxProduct(vector<string>& words) {  
4:      vector<int> masks(words.size(), 0);  
5:      for (int i = 0; i < words.size(); i++) {  
6:        for (int j = 0; j < words[i].size(); j++) {  
7:          masks[i] |= 1 << (words[i][j]-'a');  
8:        }  
9:      }  
10:      int res = 0;  
11:      for (int i = 0; i < words.size(); i++) {  
12:        for (int j = 0; j < i; j++) {  
13:          if (!(masks[i] & masks[j])) {  
14:            res = max(res, (int)(words[i].size()*words[j].size()));  
15:          }  
16:        }  
17:      }  
18:      return res;  
19:    }  
20:  };  

328. Odd Even Linked List

My own solution:

1:  class Solution {  
2:  public:  
3:    ListNode* oddEvenList(ListNode* head) {  
4:      ListNode *oddDummy = new ListNode(-1);  
5:      ListNode *evenDummy = new ListNode(-1);  
6:      ListNode *cur = head, *oddCur = oddDummy, *evenCur = evenDummy;  
7:      int i = 1;  
8:      while (cur) {  
9:        if (i % 2 == 1) {  
10:          oddCur->next = cur;  
11:          oddCur = oddCur->next;  
12:        } else {  
13:          evenCur->next = cur;  
14:          evenCur = evenCur->next;  
15:        }  
16:        cur = cur->next;  
17:        i++;  
18:      }  
19:      if (oddCur) {  
20:        oddCur->next = evenDummy->next;  
21:      }  
22:      if (evenCur) {  
23:        evenCur->next = NULL;  
24:      }  
25:      return oddDummy->next;  
26:    }  
27:  };  

Top solution on Leetcode is much more concise.

1:  class Solution {  
2:  public:  
3:    ListNode* oddEvenList(ListNode* head) {  
4:      if (!head) return head;  
5:      ListNode *oddCur = head, *evenHead = oddCur->next, *evenCur = oddCur->next;  
6:      while (evenCur && evenCur->next) {  
7:        oddCur->next = oddCur->next->next;  
8:        evenCur->next = evenCur->next->next;  
9:        oddCur = oddCur->next;  
10:        evenCur = evenCur->next;  
11:      }  
12:      oddCur->next = evenHead;  
13:      return head;  
14:    }  
15:  };  

354. Russian Doll Envelopes

If we sort the envelopes by its width first, the problem becomes "Least Increasing Subsequences" which can be solved by dynamic programming.
Let dp[i] be the length of LIS until i.
So dp[i] = 1+dp[j] if envelope j can be fit into envelope i, where 0 <= j < i. Otherwise, dp[i] = 1.

1:  class Solution {  
2:  public:  
3:    int maxEnvelopes(vector<pair<int, int>>& envelopes) {  
4:      sort(envelopes.begin(), envelopes.end());  
5:      vector<int> dp(envelopes.size(), 1);  
6:      int ret = 0;  
7:      for (int i = 0; i < envelopes.size(); i++) {  
8:        for (int j = 0; j < i; j++) {  
9:          if (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second) {  
10:            dp[i] = max(dp[j]+1, dp[i]);  
11:          }  
12:        }  
13:        ret = max(ret, dp[i]);  
14:      }  
15:      return ret;  
16:    }  
17:  };