357. Count Numbers with Unique Digits

This is a combinatorial problem. Once you placed a number, this number can’t be placed in following positions. So for next position the total number that can be placed is one less than the current position. A trick here is for the first position, there is 9 numbers that can be placed because 0 cannot be placed in the first position, and then in second position there is still 9 numbers available including 0. Also, a special case is n is 0 where there 0<=x.

1:  class Solution {  
2:  public:  
3:    int countNumbersWithUniqueDigits(int n) {  
4:      if (n == 0) return 1;  
5:      if (n == 1) return 10;  
6:      int count = 10;  
7:      for (int i = 2; i <= n; i++) {  
8:        int tmp = 9;  
9:        for (int j = 1, k = 9; j < i && k >= 0; j++, k--) {  
10:          tmp *= k;  
11:        }  
12:        count += tmp;  
13:      }  
14:      return count;  
15:    }  
16:  };  

326. Power of Three

I think for the interview, the recursive version is good enough. Don’t forget that n == 1 is a valid case.

1:  class Solution {  
2:  public:  
3:    bool isPowerOfThree(int n) {  
4:      return n > 0 && (n == 1 || (n % 3 == 0 && isPowerOfThree(n / 3)));  
5:    }  
6:  };  

Anyway, there is a mathematical version.

1:  class Solution {  
2:  public:  
3:    bool isPowerOfThree(int n) {  
4:      int maxThrees = (int) pow(3, (int)(log(0x7FFFFFFF)/log(3)));  
5:      return n > 0 && maxThrees % n == 0;  
6:    }  
7:  };  

302. Smallest Rectangle Enclosing Black Pixels

Similar solution to the problem of "Number of Islands". Use DFS and flip 1 to 0 after visiting a position. I have no idea about how to use binary search to solve the problem.

1:  class Solution {  
2:  private:  
3:    int minI, minJ, maxI, maxJ;  
4:    int row, col;  
5:    vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
6:  public:  
7:    int minArea(vector<vector<char>>& image, int x, int y) {  
8:      minI = minJ = INT_MAX;  
9:      maxI = maxJ = INT_MIN;  
10:      row = image.size();  
11:      if (row == 0) return 0;  
12:      col = image[0].size();  
13:      dfs(image, x, y);  
14:      return (maxI - minI+1) * (maxJ - minJ+1);  
15:    }  
16:    void dfs(vector<vector<char>> &image, int i, int j) {  
17:      image[i][j] = '0';  
18:      minI = min(minI, i);  
19:      minJ = min(minJ, j);  
20:      maxI = max(maxI, i);  
21:      maxJ = max(maxJ, j);  
22:      for (int d = 0; d < dir.size(); d++) {  
23:        int ii = i + dir[d].first;  
24:        int jj = j + dir[d].second;  
25:        if (ii < 0 || ii == row || jj < 0 || jj == col || image[ii][jj] == '0') continue;  
26:        dfs(image, ii, jj);  
27:      }  
28:    }  
29:  };  

214. Shortest Palindrome

I have to follow the top rated solution. The top one uses the KMP algorithm.
Here are two good links explaining this algorithm.
https://www.youtube.com/watch?v=GTJr8OvyEVQ
https://www.youtube.com/watch?v=KG44VoDtsAA
After preprocessing the pattern, the kmp[i] is the longest length of the suffix that matches prefix at ith character in pattern string. So if we concatenate input string s and its reversed string r, and process the concatenated string by KMP algorithm, we know that the longest length that the suffix of string r matches prefix of string s is kmp[kmp.size()-1]. Let’s take “aacecaaa” as an example here.
The concatenated string will be “aacecaaa#aaacecaa” (Why put # here? I’ll explain later)
After KMP processing, the kmp vector will be [0 1 0 0 0 1 2 2 0 1 2 2 3 4 5 6 7]. So for the last character, the longest length that the suffix matches prefix is 7. Note the suffix of the string is actually the reversed input string and the prefix is the input string itself. Also, it means that there is already 7 characters from the beginning matches the 7 characters that from the end. So all we need to do is to copy the rest 1 unmatched character to the beginning of the input string in a reverse order, which is exactly copying the first 1 character in the reversed string to the beginning of the input string.

When I revisited this problem, I made mistake in
line 16: I was checking "j != 0". However, we should check "tmp[i] == tmp[j]" because even j reaches back to 0, it's still possible that "tmp[i] == tmp[j]" and thus kmp[i] should be 1 not 0.

1:  class Solution {  
2:  public:  
3:    string shortestPalindrome(string s) {  
4:      string r = s;  
5:      reverse(r.begin(), r.end());  
6:      string tmp = s + "#" + r;  
7:      vector<int> kmp(tmp.size(), 0);  
8:      int i = 1, j = 0;  
9:      for (; i < tmp.size(); i++) {  
10:        if (tmp[i] == tmp[j]) kmp[i] = ++j;  
11:        else {  
12:          j = kmp[j-1];  
13:          while (j > 0 && tmp[i] != tmp[j]) {  
14:            j = kmp[j-1];  
15:          }  
16:          if (tmp[i] == tmp[j]) {  
17:            kmp[i] = j+1;  
18:            j++;  
19:          }  
20:        }  
21:      }  
22:      return r.substr(0, s.size()-kmp[kmp.size()-1])+s;  
23:    }  
24:  };  

Now let’s look at why “#” is needed. Without “#”, what happens if the input string is “aa”? The kmp vector will be [0 1 2 3]. The kmp[kmp.size()-1] is larger than the input string size which makes return line invalid.
And here is a short version of KMP algorithm.

1:  class Solution {  
2:  public:  
3:    string shortestPalindrome(string s) {  
4:      string r = s;  
5:      reverse(r.begin(), r.end());  
6:      string tmp = s + "#" + r;  
7:      vector<int> kmp(tmp.size(), 0);  
8:      int i = 1, j = 0;  
9:      for (; i < tmp.size(); i++) {  
10:        j = kmp[i-1];  
11:        while (j > 0 && tmp[i] != tmp[j]) {  
12:          j = kmp[j-1];  
13:        }  
14:        kmp[i] = (j += tmp[i] == tmp[j]);  
15:      }  
16:      return r.substr(0, s.size()-kmp[kmp.size()-1])+s;  
17:    }  
18:  };  

257. Binary Tree Paths

This a problem of DFS over tree. The trick here is the termination for DFS should be the node is a leaf node instead of NULL, otherwise, you'll output duplicated path. Also need to be careful about the output format.

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<string> binaryTreePaths(TreeNode* root) {  
13:      vector<string> res;  
14:      if (root == NULL) return res;  
15:      helper(root, "", res);  
16:      return res;  
17:    }  
18:    void helper(TreeNode* root, string path, vector<string> &res) {  
19:      if (root->left == NULL && root->right == NULL) {  
20:        res.push_back(path+to_string(root->val));  
21:        return;  
22:      }  
23:      if (path.empty()) {  
24:        if (root->left) helper(root->left, to_string(root->val)+"->", res);  
25:        if (root->right) helper(root->right, to_string(root->val)+"->", res);  
26:      } else {  
27:        if (root->left) helper(root->left, path+to_string(root->val)+"->", res);  
28:        if (root->right) helper(root->right, path+to_string(root->val)+"->", res);  
29:      }  
30:    }  
31:  };  

173. Binary Search Tree Iterator

This is actually a iterative traversal of BST by the help of stack.

1:  /**  
2:   * Definition for binary tree  
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 BSTIterator {  
11:  private:  
12:    stack<TreeNode *> stk;  
13:  public:  
14:    BSTIterator(TreeNode *root) {  
15:      while (root) {  
16:        stk.push(root);  
17:        root = root->left;  
18:      }  
19:    }  
20:    /** @return whether we have a next smallest number */  
21:    bool hasNext() {  
22:      return !stk.empty();  
23:    }  
24:    /** @return the next smallest number */  
25:    int next() {  
26:      TreeNode *t = stk.top();  
27:      stk.pop();  
28:      if (t->right) {  
29:        TreeNode *p = t->right;  
30:        while (p) {  
31:          stk.push(p);  
32:          p = p->left;  
33:        }  
34:      }  
35:      return t->val;  
36:    }  
37:  };  
38:  /**  
39:   * Your BSTIterator will be called like this:  
40:   * BSTIterator i = BSTIterator(root);  
41:   * while (i.hasNext()) cout << i.next();  
42:   */  

22. Generate Parentheses

We need to count the left and right parentheses. We start from n left parentheses and 0 right parentheses. When we place 1 left parentheses, we need to decrease the left parentheses count by 1 but increase the right parentheses count by 1. When we place 1 right parentheses, we only need to decrease the right parenthese count by 1. Note the two cases above are not exclusive to each other. When there is no more left and right parentheses, we stop and push the solution to the result.

1:  class Solution {  
2:  public:  
3:    vector<string> generateParenthesis(int n) {  
4:      vector<string> res;  
5:      helper(n, 0, "", res);  
6:      return res;  
7:    }  
8:    void helper(int l, int r, string sol, vector<string> &res) {  
9:      if (l == 0 && r == 0) {  
10:        res.push_back(sol);  
11:        return;  
12:      }  
13:      if (l > 0) helper(l-1, r+1, sol+"(", res);  
14:      if (r > 0) helper(l, r-1, sol+")", res);  
15:    }  
16:  };  

140. Word Break II

My intuition is to use backtracking solution directly. But it get TLE. So we definitely need to do some memorization.

1:  class Solution {  
2:  public:  
3:    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {  
4:      vector<string> res;  
5:      helper(s, 0, wordDict, "", res);  
6:      return res;  
7:    }  
8:    void helper(string s, int i, unordered_set<string> &wordDict, string sol, vector<string> &res) {  
9:      if (i == s.size()) { sol.pop_back(); res.push_back(sol); return;}  
10:      for (int j = i; j < s.size(); j++) {  
11:        string word = s.substr(i, j-i+1);  
12:        if (wordDict.count(word) == 0) continue;  
13:        helper(s, j+1, wordDict, sol+word+" ", res);  
14:      }  
15:    }  
16:  };  

Let’s look at one example first. Say, we have string “aaaab”, dictionary [“a”, “aa”]. Then let’s see how the solution above works.
Step 1: “a a a a” and “b” not valid.
Setp 2: “a a a” and recursively check “ab”.
Step 3: “a a aa” and “b” not valid.
Step 4: “a a” and recursively check “aab”.
Step 5: “a aa” and recursively check “ab”.
Step 6: “aa” and recursively check “aab”.
From here, we can see in Step 5 we don’t have to recursively check “ab” again because from Step 2 we already know that “ab” is not breakable. Same to Step 6. So if we can memorize if word[i..n-1] is breakable, then we can speed up the solution. Let dp[i] be that s[i..n-1] is not breakable. And then the trick becomes how to update the dp[i]. If there is no breakable words, no new solution will be added to the result. So we can update the dp[i] upon that.

1:  class Solution {  
2:  private:  
3:    vector<bool> dp;  
4:  public:  
5:    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {  
6:      vector<string> res;  
7:      dp = vector<bool>(s.size(), true);  
8:      helper(s, 0, wordDict, "", res);  
9:      return res;  
10:    }  
11:    void helper(string s, int i, unordered_set<string> &wordDict, string sol, vector<string> &res) {  
12:      if (i == s.size()) { sol.pop_back(); res.push_back(sol); return;}  
13:      for (int j = i; j < s.size(); j++) {  
14:        string word = s.substr(i, j-i+1);  
15:        int res_sz = res.size();  
16:        if (wordDict.count(word) == 0 || !dp[j]) continue;  
17:        helper(s, j+1, wordDict, sol+word+" ", res);  
18:        if (res_sz == res.size()) dp[j] = false;  
19:      }  
20:    }  
21:  };  

17. Letter Combinations of a Phone Number

A typical backtracking solution.

1:  class Solution {  
2:  private:  
3:    vector<string> pad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
4:  public:  
5:    vector<string> letterCombinations(string digits) {  
6:      vector<string> res;  
7:      if (digits.size() == 0) return res;  
8:      helper(digits, 0, "", res);  
9:      return res;  
10:    }  
11:    void helper(string &digits, int i, string sol, vector<string> &res) {  
12:      if (i == digits.size()) {  
13:        res.push_back(sol); return;  
14:      }  
15:      for (int j = 0; j < pad[digits[i]-'0'].size(); j++) {  
16:        sol += pad[digits[i]-'0'][j];  
17:        helper(digits, i+1, sol, res);  
18:        sol.pop_back();  
19:      }  
20:    }  
21:  };  

345. Reverse Vowels of a String

Easy, but easy to make mistake. I've highlighted in red the mistakes I made.

1:  class Solution {  
2:  public:  
3:    string reverseVowels(string s) {  
4:      if (s.empty()) return s;  
5:      int i = 0, j = s.size() - 1;  
6:      while (i < j) {  
7:        while (i < j && !isVowel(s[i])) i++;  
8:        while (i < j && !isVowel(s[j])) j--;  
9:        swap(s[i], s[j]);  
10:        i++, j--;  
11:      }  
12:      return s;  
13:    }  
14:    bool isVowel(char c) {  
15:      c = tolower(c);  
16:      return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';  
17:    }  
18:  };  

162. Find Peak Element

I tried naive way first which runs O(n) time.

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

Obviously, this naive way isn’t the best. We can do it by binary search. The idea is we keep looking for the two numbers in the middle. And if left middle number is less than the right middle number, we point left pointer to the right middle number, otherwise, we point right pointer to the left middle number. In this way, left and right pointers are always pointing to the larger one which will eventually help us find the peak.

1:  class Solution {  
2:  public:  
3:    int findPeakElement(vector<int>& nums) {  
4:      int l = 0, r = nums.size()-1;  
5:      while (l < r) {  
6:        int mid1 = l + (r - l) / 2;  
7:        int mid2 = mid1 + 1;  
8:        if (nums[mid1] < nums[mid2]) {  
9:          l = mid2;  
10:        } else {  
11:          r = mid1;  
12:        }  
13:      }  
14:      return l;  
15:    }  
16:  };  

231. Power of Two

Look at binary of an integer. If an integer is a power of two, it must contains only one "1" in its binary. Also, all the negative integers and zero are not power of two.

1:  class Solution {  
2:  public:  
3:    bool isPowerOfTwo(int n) {  
4:      if (n <= 0) return false;  
5:      while (!(n & 1)) {  
6:        n >>= 1;  
7:      }  
8:      return !(n >> 1) ? true : false;  
9:    }  
10:  };  

The following solution is inspired by counting number of ones in a integer.

1:  class Solution {  
2:  public:  
3:    bool isPowerOfTwo(int n) {  
4:      return n > 0 && (n & (n - 1)) == 0;  
5:    }  
6:  };  

20. Valid Parentheses

Nothing interesting. Just use stack.

1:  class Solution {  
2:  public:  
3:    bool isValid(string s) {  
4:      stack<char> stk;  
5:      for (char c : s) {  
6:        switch(c) {  
7:          case '(':  
8:            stk.push(c);  
9:            break;  
10:          case ')':  
11:            if (stk.empty() || stk.top() != '(') return false;  
12:            stk.pop();  
13:            break;  
14:          case '[':  
15:            stk.push(c);  
16:            break;  
17:          case ']':  
18:            if (stk.empty() || stk.top() != '[') return false;  
19:            stk.pop();  
20:            break;  
21:          case '{':  
22:            stk.push(c);  
23:            break;  
24:          case '}':  
25:            if (stk.empty() || stk.top() != '{') return false;  
26:            stk.pop();  
27:            break;  
28:        }  
29:      }  
30:      return stk.empty();  
31:    }  
32:  };  

When I revisit this problem, I have a more concise code. However, I made a mistake in line 15 where I returned true.

1:  class Solution {  
2:  public:  
3:    bool isValid(string s) {  
4:      stack<char> stk;  
5:      for (char c : s) {  
6:        if (c == '(' || c == '[' || c == '{') stk.push(c);  
7:        else if (stk.empty()) return false;  
8:        else {  
9:          if (c == ')' && stk.top() != '(') return false;   
10:          else if (c == ']' && stk.top() != '[') return false;  
11:          else if (c == '}' && stk.top() != '{') return false;  
12:          stk.pop();  
13:        }  
14:      }  
15:      return stk.empty();  
16:    }  
17:  };  

163. Missing Ranges

Keep track of previous node and the current node for the missing range. When output the missing range, we only need to output [prev+1, cur-1].

1:  class Solution {  
2:  public:  
3:    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {  
4:      long long pre = lower - 1, cur = 0;  
5:      vector<string> res;  
6:      for (int i = 0; i <= nums.size(); i++) {  
7:        cur = (i == nums.size()) ? upper+1 : nums[i];  
8:        if (cur - pre > 1) res.push_back(getRange(nums, pre+1, cur-1));  
9:        pre = cur;  
10:      }  
11:      return res;  
12:    }  
13:    string getRange(vector<int> &nums, int pre, int cur) {  
14:      if (pre == cur) return to_string(pre);  
15:      else return to_string(pre) + "->" + to_string(cur);  
16:    }  
17:  };  

The above code will fail the case of nums = [2147483647], lower = 0 and upper = 2147483647 because of overflow. So the two variables of "pre" and "cur" should be type of "long long"

288. Unique Word Abbreviation

The key idea has bee explained in the code. When I revisited this problem, I made a mistake in line 26. I returned "mp[abbr].size() == 1 && mp[abbr].count(word) == 1". This is wrong because it should be true if the new word does not exist in the hashed set.

1:  class ValidWordAbbr {  
2:  private:  
3:    unordered_map<string, unordered_set<string>> dict;  
4:    bool flag;  
5:    string abbreviation(string word) {  
6:      if (word.size() <= 2) return word;  
7:      return word[0] + to_string(word.size()-2) + word[word.size()-1];  
8:    }  
9:  public:  
10:    ValidWordAbbr(vector<string> &dictionary) {  
11:      for (string s : dictionary) {  
12:        string abbr = abbreviation(s);  
13:        dict[abbr].insert(s);  
14:      }  
15:    }  
16:    bool isUnique(string word) {  
17:      string abbr = abbreviation(word);  
18:      // The idea is set up a hash table whose key is the abbreviation and value is the corresponding word set.  
19:      // We only get true when the word set only contains the input word.  
20:      // Case 1: FALSE, the word set donesn't contain the input word.  
21:      //     e.g. ["dog"]; isUnique("dig"). dict["d1g"].size() = 1 while dict["d1g"].count("dig") = 0.  
22:      // Case 2: TRUE, the word set only contains the input word.  
23:      //     e.g. ["dog"]; isUnique("dog"). dict["d1g"].size() = 1 while dict["d1g"].count("dog") = 1.  
24:      // Case 3: FALSE, the word set contains more than one word.  
25:      //     e.g. ["dog", "dig"]; isUnique("dog"). dict["d1g"].size() = 2 while dict["d1g"].count("dog") = 1.  
26:      return dict[abbr].size() == dict[abbr].count(word);  
27:    }  
28:  };  
29:  // Your ValidWordAbbr object will be instantiated and called as such:  
30:  // ValidWordAbbr vwa(dictionary);  
31:  // vwa.isUnique("hello");  
32:  // vwa.isUnique("anotherWord");  

155. Min Stack

Maintain two stacks. One is the normal stack and the other stores the minimum number so far. These two stacks should always have the same size. When I revisit this problem, I made a mistake in line 11.

1:  class MinStack {  
2:  private:  
3:    stack<int> stk;  
4:    stack<int> minStk;  
5:  public:  
6:    /** initialize your data structure here. */  
7:    MinStack() {  
8:    }  
9:    void push(int x) {  
10:      stk.push(x);  
11:      if (!minStk.empty()) {  
12:        minStk.push(x < minStk.top() ? x : minStk.top());  
13:      } else {  
14:        minStk.push(x);  
15:      }  
16:    }  
17:    void pop() {  
18:      if (!stk.empty()) {  
19:        stk.pop();  
20:        minStk.pop();  
21:      }  
22:    }  
23:    int top() {  
24:      if (!stk.empty()) {  
25:        return stk.top();  
26:      } else {  
27:        return -1;  
28:      }  
29:    }  
30:    int getMin() {  
31:      if (!minStk.empty()) {  
32:        return minStk.top();  
33:      } else {  
34:        return -1;  
35:      }  
36:    }  
37:  };  
38:  /**  
39:   * Your MinStack object will be instantiated and called as such:  
40:   * MinStack obj = new MinStack();  
41:   * obj.push(x);  
42:   * obj.pop();  
43:   * int param_3 = obj.top();  
44:   * int param_4 = obj.getMin();  
45:   */  

146. LRU Cache

I made mistake in first place as following. The OJ complains "Runtime Error". After some debugging, I find I did wrong on line 27. When popping out the last element in the list, we need to erase this element in hash map too. However, here comes the question. To erase the element in the hash map, we need to know the key, but in my design, I don't know the key of the last element in the list.

1:  class LRUCache{  
2:  private:  
3:    int cap;  
4:    list<int> l;  
5:    unordered_map<int, list<int>::iterator> mp;  
6:  public:  
7:    LRUCache(int capacity) {  
8:      cap = capacity;  
9:    }  
10:    int get(int key) {  
11:      int ret = -1;  
12:      if (mp.find(key) != mp.end()) {  
13:        ret = *mp[key];  
14:        l.erase(mp[key]);  
15:        l.push_front(ret);  
16:        mp[key] = l.begin();  
17:      }  
18:      return ret;  
19:    }  
20:    void set(int key, int value) {  
21:      if (mp.find(key) != mp.end()) {  
22:        l.erase(mp[key]);  
23:        mp.erase(key);  
24:        l.push_front(value);  
25:        mp[key] = l.begin();  
26:      } else {  
27:        if (l.size() == cap) l.pop_back();  
28:        l.push_front(value);  
29:        mp[key] = l.begin();  
30:      }  
31:    }  
32:  };  

So, the right design should be that the list stores the key and and the value corresponding to the key is wrapped in a pair with the list iterator. And the hash map consists of key and the pair of key and list iterator.

1:  class LRUCache{  
2:  private:  
3:    int cap;  
4:    list<int> l;  
5:    unordered_map<int, pair<int, list<int>::iterator>> mp;  
6:  public:  
7:    LRUCache(int capacity) {  
8:      cap = capacity;  
9:    }  
10:    int get(int key) {  
11:      int ret = -1;  
12:      if (mp.find(key) != mp.end()) {  
13:        ret = mp[key].first;  
14:        l.erase(mp[key].second);  
15:        l.push_front(key);  
16:        mp[key].second = l.begin();  
17:      }  
18:      return ret;  
19:    }  
20:    void set(int key, int value) {  
21:      if (mp.find(key) != mp.end()) {  
22:        l.erase(mp[key].second);  
23:        mp.erase(key);  
24:      } else {  
25:        if (l.size() == cap) {  
26:          mp.erase(l.back());  
27:          l.pop_back();  
28:        }  
29:      }  
30:      l.push_front(key);  
31:      mp[key] = make_pair(value, l.begin());  
32:    }  
33:  };  

66. Plus One

I was thinking of add 1 from end and insert 1 in the front if any carry. But I found the top rated solution is very concise and clever. Pushing a number to the back is much faster than inserting in the front.

1:  class Solution {  
2:  public:  
3:    vector<int> plusOne(vector<int>& digits) {  
4:      int n = digits.size();  
5:      for (int i = n-1; i >= 0; i--) {  
6:        if (digits[i] == 9) digits[i] = 0;  
7:        else { digits[i]++; return digits; }  
8:      }  
9:      digits[0] = 1;  
10:      digits.push_back(0);  
11:      return digits;  
12:    }  
13:  };  

359. Logger Rate Limiter

I was trying to solve it as the same way as "362. Design Hit Counter" did. However, after reading the top rated solutions, I realized this problem is much easier. We can have a hash table whose key is the message and value is the expiration time. Once a new message comes in, we check if the timestamp falls in the expiration time which means the existing message is still valid, i.e. it has been printed in last 10 seconds. In this case, we print false. Otherwise, we update the expiration time.

1:  class Logger {  
2:    unordered_map<string, int> mp;  
3:  public:  
4:    /** Initialize your data structure here. */  
5:    Logger() {  
6:    }  
7:    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.  
8:      If this method returns false, the message will not be printed.  
9:      The timestamp is in seconds granularity. */  
10:    bool shouldPrintMessage(int timestamp, string message) {  
11:      if (timestamp < mp[message]) return false;  
12:      mp[message] = timestamp + 10;  
13:      return true;  
14:    }  
15:  };  
16:  /**  
17:   * Your Logger object will be instantiated and called as such:  
18:   * Logger obj = new Logger();  
19:   * bool param_1 = obj.shouldPrintMessage(timestamp,message);  
20:   */  

293. Flip Game

Well, an easy one.

1:  class Solution {  
2:  public:  
3:    vector<string> generatePossibleNextMoves(string s) {  
4:      int n = s.size();  
5:      vector<string> res;  
6:      for (int i = 0; i < n-1; i++) {  
7:        if (s[i] == '+' && s[i+1] == '+') {  
8:          s[i] = s[i+1] = '-';  
9:          res.push_back(s);  
10:          s[i] = s[i+1] = '+';  
11:        }  
12:      }  
13:      return res;  
14:    }  
15:  };  

370. Range Addition

I implemented in a naive way. But it got TLE.

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

The hits provides a O(n+k) running time solution. Let's see the example. Given length = 5.
update(1,3,2), we should have [0, 2, 2, 2, 0]. What if we only record two positions? It means we need to do sum from the left to right to get the new array. So we can modify the array to be [0, 2, 0, 0, -2] and when we do sum from left to right, i.e. res[i] = res[i] + res[i-1], we'll get [0, 2, 2, 2, 0] which is exactly the same as our expected array. So for each update(i, j, a), we add a to res[i] and subtract a from res[j+1]. In the end, we sum up the res from left to right following res[i] = res[i] + res[i-1].

1:  class Solution {  
2:  public:  
3:    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {  
4:      vector<int> res(length+1, 0);  
5:      for (int i = 0; i < updates.size(); i++) {  
6:        res[updates[i][0]] += updates[i][2];  
7:        res[updates[i][1]+1] -= updates[i][2];  
8:      }  
9:      for (int i = 1; i < length; i++) {  
10:        res[i] = res[i]+res[i-1];  
11:      }  
12:      res.pop_back();  
13:      return res;  
14:    }  
15:  };  

362. Design Hit Counter

For this design problem, I was thinking of use an 300-size array to keep the counts. However, this solution doesn't provide any information about if the hits in the array are expired. For example, we have a hit at 1s and we have another hit at 302s. Then when we count the hits in the last 300s, we'll get 2 because we don't know when to expire the hit at 1s. Therefore, we need to another array to record the timestamp for each count in last 300s. When we hit the counter, we'll wrap around the timestamp to 300s, say i, and then we check in the time[] array if time[i] matches the input timestamp. If so, we increase the hits[i] counter for that hit. If hits[i] is more than 1, it means there are multiple hits happening in the same second. On the other hand, if time[i] doesn't match the input timestamp, it means the time[i] has expired, we need to give it new time stamp and reset the hits[i] counter to 1. When counting the hits in last 300s, we just need to sum up all the hits in last 300s.

1:  class HitCounter {  
2:  private:  
3:    vector<int> time;  
4:    vector<int> hits;  
5:  public:  
6:    /** Initialize your data structure here. */  
7:    HitCounter() {  
8:      time = vector<int>(300, 0);  
9:      hits = vector<int>(300, 0);  
10:    }  
11:    /** Record a hit.  
12:      @param timestamp - The current timestamp (in seconds granularity). */  
13:    void hit(int timestamp) {  
14:      int i = timestamp % 300;  
15:      if (time[i] != timestamp) {  
16:        time[i] = timestamp;  
17:        hits[i] = 1;  
18:      } else {  
19:        hits[i]++;  
20:      }  
21:    }  
22:    /** Return the number of hits in the past 5 minutes.  
23:      @param timestamp - The current timestamp (in seconds granularity). */  
24:    int getHits(int timestamp) {  
25:      int count = 0;  
26:      for (int i = 0 ; i < 300; i++) {  
27:        if (timestamp - time[i] < 300) {  
28:          count += hits[i];  
29:        }  
30:      }  
31:      return count;  
32:    }  
33:  };  
34:  /**  
35:   * Your HitCounter object will be instantiated and called as such:  
36:   * HitCounter obj = new HitCounter();  
37:   * obj.hit(timestamp);  
38:   * int param_2 = obj.getHits(timestamp);  
39:   */  

369. Plus One Linked List

Well, I was thinking reverse the list, do increase and reverse the list again in first place. However, I don't think it is expected in the interview because this is so naive. And particularly, if we are not allowed to change the list order then this solution is out. Actually, we can do recursive way because recursion helps us "reverse" the list.

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* plusOne(ListNode* head) {  
12:      if (dfs(head) == 0) return head;  
13:      else {  
14:        ListNode *node = new ListNode(1);  
15:        node->next = head;  
16:        return node;  
17:      }  
18:    }  
19:    int dfs(ListNode *head) {  
20:      if (head == NULL) return 1;  
21:      int carry = dfs(head->next);  
22:      if (carry == 0) return 0;  
23:      int val = head->val + 1;  
24:      head->val = val % 10;  
25:      return val / 10;  
26:    }  
27:  };  

323. Number of Connected Components in an Undirected Graph

A dynamical connectivity problem. This is a typical application of union find.

1:  class Solution {  
2:  public:  
3:    int countComponents(int n, vector<pair<int, int>>& edges) {  
4:      vector<int> ufs(n, 0);  
5:      for (int i = 0; i < n; i++) ufs[i] = i;  
6:      for (int i = 0; i < edges.size(); i++) {  
7:        int u = edges[i].first;  
8:        int v = edges[i].second;  
9:        while (u != ufs[u]) { ufs[u] = ufs[ufs[u]]; u = ufs[u]; }  
10:        while (v != ufs[v]) { ufs[v] = ufs[ufs[v]]; v = ufs[v]; }  
11:        if (u != v) {  
12:          ufs[u] = ufs[v];  
13:          n--;  
14:        }  
15:      }  
16:      return n;  
17:    }  
18:  };  

Of course, DFS can be used to solve this problem too.

1:  class Solution {  
2:  public:  
3:    int countComponents(int n, vector<pair<int, int>>& edges) {  
4:      vector<vector<int>> graph(n);  
5:      for (int i = 0; i < edges.size(); i++) {  
6:        graph[edges[i].first].push_back(edges[i].second);  
7:        graph[edges[i].second].push_back(edges[i].first);  
8:      }  
9:      vector<bool> visited(n);  
10:      int count = 0;  
11:      for (int i = 0; i < n; i++) {  
12:        if (!visited[i]) {  
13:          dfs(graph, visited, i);  
14:          count++;  
15:        }  
16:      }  
17:      return count;  
18:    }  
19:    void dfs(vector<vector<int>> &graph, vector<bool> &visited, int i) {  
20:      visited[i] = true;  
21:      for (int j = 0; j < graph[i].size(); j++) {  
22:        if (!visited[graph[i][j]]) {  
23:          dfs(graph, visited, graph[i][j]);  
24:        }  
25:      }  
26:    }  
27:  };  

360. Sort Transformed Array

If a >=0, the minimum value is at the array's vertex. So we need to move the two end pointers toward the vertex and output from right to left.
If a <0, the maximum value is at the array's vertex. So we need to move the two end pointers toward the vertex but output from left to right.

1:  class Solution {  
2:  public:  
3:    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {  
4:      int start = 0, end = nums.size()-1;  
5:      int i = a >= 0 ? nums.size()-1 : 0;  
6:      vector<int> res(nums.size(), 0);  
7:      while (start <= end) {  
8:        int startNum = computeNumber(nums[start], a, b, c);  
9:        int endNum = computeNumber(nums[end], a, b, c);  
10:        if (a >= 0) {  
11:          if (startNum >= endNum) { res[i--] = startNum; start++; }  
12:          else { res[i--] = endNum; end--; }  
13:        } else {  
14:          if (startNum <= endNum) { res[i++] = startNum; start++; }  
15:          else { res[i++] = endNum; end--; }  
16:        }  
17:      }  
18:      return res;  
19:    }  
20:    int computeNumber(int n, int a, int b, int c) {  
21:      return a*n*n+b*n+c;  
22:    }  
23:  };  

261. Graph Valid Tree

The problem is trying to solve what is a tree. Actually the tree can be define by following two rules:
1. A graph without cycles.
2. A graph whose nodes are all connected.
Here is good video explaining two popular ways to solve the problem, i.e. Union Find and DFS.
https://www.youtube.com/watch?v=n_t0a_8H8VY
So we can use DFS to check if there is any cycle in the graph. And then after the DFS, we check if all the nodes have been visited.

1:  class Solution {  
2:  public:  
3:    bool validTree(int n, vector<pair<int, int>>& edges) {  
4:      vector<vector<int>> neighbors(n);  
5:      for (int i = 0; i < edges.size(); i++) {  
6:        neighbors[edges[i].first].push_back(edges[i].second);  
7:        neighbors[edges[i].second].push_back(edges[i].first);  
8:      }  
9:      vector<bool> visited(n, false);  
10:      if(dfs(neighbors, visited, 0, -1)) return false;  
11:      for (bool v : visited) {  
12:        if (!v) return false;  
13:      }  
14:      return true;  
15:    }  
16:    bool dfs(vector<vector<int>> &neighbors, vector<bool> &visited, int cur, int parent) {  
17:      visited[cur] = true;  
18:      for (int i = 0; i < neighbors[cur].size(); i++) {  
19:        int neighbor = neighbors[cur][i];  
20:        if ((visited[neighbor] && neighbor != parent) || ((!visited[neighbor]) && dfs(neighbors, visited, neighbor, cur)))  
21:          return true;  
22:      }  
23:      return false;  
24:    }  
25:  };  

Then here is the Union Find version. Note, Union Find is much faster than the DFS.

1:  class Solution {  
2:  public:  
3:    bool validTree(int n, vector<pair<int, int>>& edges) {  
4:      vector<int> ufs(n, 0);  
5:      if (edges.size() != n - 1) return false;  
6:      for (int i = 0; i < ufs.size(); i++) ufs[i] = i;  
7:      for (int i = 0; i < edges.size(); i++) {  
8:        int v = edges[i].first;  
9:        int u = edges[i].second;  
10:        while (v != ufs[v]) v = ufs[v]; // find the set that v belongs to  
11:        while (u != ufs[u]) u = ufs[u]; // find the set that u belongs to  
12:        if (v == u) return false;  
13:        ufs[u] = v;  
14:      }  
15:      return true;  
16:    }  
17:  };  

368. Largest Divisible Subset

I don't have any clue to solve this problem. I followed one of the top voted solutions. The trick here is for a new integer I, it can be placed into the set as long as it divides the smallest number in the set or it can be divided by the largest number in the set. Also for the numbers in the same subset, we use union find solution.
Let T[n] be the size of the largest divisible subset whose largest number is nums[n].
Let child[n] be the index of its child in the nums[n].
Now let's look at an example, nums = [1,2,3,4].
i = 0, j = 0, T = [1,0,0,0] child=[0,0,0,0]
i = 1, j = 1, T = [1,1,0,0] child=[0,1,0,0]
         j = 0, T = [1,2,0,0] child=[0,0,0,0] (2's child is 1)
i = 2, j = 2, T = [1,2,1,0] child=[0,1,2,0]
         j = 1, 3 can't be divided by 2, nothing to change
         j = 0, T = [1,2,2,0] child=[0,0,0,0] (3's child is 1)
i = 3, j = 3, T = [1,2,2,1] child=[0,1,2,3]
         j = 2, 4 can't be divided by 3, nothing to change
         j = 1, T = [1,2,2,3] child=[0,1,2,1] (4's child is 2)
So far, the longest subset is 3. And we can find these three numbers by chasing the child[] array, i.e. nums[3]->nums[1]->nums[0] (i.e. 4,2,1). Therefore, in order to get the largest divisible subset, we can maintain the largest size of the subsets and the largest number's index in the set. The subset can be achieved by chasing the child[] array.

1:  class Solution {  
2:  public:  
3:    vector<int> largestDivisibleSubset(vector<int>& nums) {  
4:      vector<int> res;  
5:      if (nums.size() == 0) return res;  
6:      vector<int> T(nums.size(), 0);  
7:      vector<int> child(nums.size(), 0);  
8:      int m = 0, mi = 0;  
9:      sort(nums.begin(), nums.end());  
10:      for (int i = 0; i < nums.size(); i++) {  
11:        for (int j = i; j >= 0; j--) {  
12:          if (nums[i] % nums[j] == 0 && T[j] + 1 > T[i]) {  
13:            T[i] = T[j] + 1;  
14:            child[i] = j;  
15:          }  
16:          if (T[i] > m) {  
17:            m = T[i];  
18:            mi = i;  
19:          }  
20:        }  
21:      }  
22:      for (int i = 0; i < m; i++) {  
23:        res.push_back(nums[mi]);  
24:        mi = child[mi];  
25:      }  
26:      return res;  
27:    }  
28:  };  

314. Binary Tree Vertical Order Traversal

This is a level order traversal problem. The trick here we need to track index for each node. If root index is i, then left child index is i-1 and right child index is i. Since the output is from left to right, i.e. from smallest index to largest index, we can use map which has sorted the keys. The index is key and the node vector that has this index as value. So the problem becomes level order traversal nodes, compute index for the node and its children, and push the node to right vector mapped by its index.

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>> verticalOrder(TreeNode* root) {  
13:      vector<vector<int>> res;  
14:      if (!root) return res;  
15:      map<int, vector<int>> mp;  
16:      queue<pair<int, TreeNode *>> q;  
17:      q.push(make_pair(0, root));  
18:      while (!q.empty()) {  
19:        int sz = q.size();  
20:        for (int i = 0; i < sz; i++) {  
21:          pair<int, TreeNode*> node = q.front();  
22:          q.pop();  
23:          int index = node.first;  
24:          mp[index].push_back(node.second->val);  
25:          if (node.second->left) {  
26:            q.push(make_pair(index-1, node.second->left));  
27:          }  
28:          if (node.second->right) {  
29:            q.push(make_pair(index+1, node.second->right));  
30:          }  
31:        }  
32:      }  
33:      for (auto it : mp) {  
34:        res.push_back(it.second);  
35:      }  
36:      return res;  
37:    }  
38:  };  

374. Guess Number Higher or Lower

A typical binary search.

1:  // Forward declaration of guess API.  
2:  // @param num, your guess  
3:  // @return -1 if my number is lower, 1 if my number is higher, otherwise return 0  
4:  int guess(int num);  
5:  class Solution {  
6:  public:  
7:    int guessNumber(int n) {  
8:      int l = 1, r = n, mid = 0, res = 0;  
9:      while (l <= r) {  
10:        mid = l + (r-l) /2;  
11:        res = guess(mid);  
12:        if (res == 0) return mid;  
13:        else if (res == 1) l = mid + 1;  
14:        else r = mid - 1;  
15:      }  
16:      return mid;  
17:    }  
18:  };  

356. Line Reflection

I followed the hit and solved the problem by set.

1:  class Solution {  
2:  public:  
3:    bool isReflected(vector<pair<int, int>>& points) {  
4:      set<pair<int,int>> s;  
5:      int minX = INT_MAX, maxX = INT_MIN;  
6:      for (int i = 0; i < points.size(); i++) {  
7:        minX = min(points[i].first, minX);  
8:        maxX = max(points[i].first, maxX);  
9:        s.insert(points[i]);  
10:      }  
11:      double y = (minX + maxX) * 1.0 / 2;  
12:      for (int i = 0; i < points.size(); i++) {  
13:        if (!s.count(make_pair(2*y-points[i].first, points[i].second))) return false;  
14:      }  
15:      return true;  
16:    }  
17:  };  

Obviously, this code can be improved because for line 12 we don't have to traverse all points. We can use unordered_map and y as key and the set of its corresponding x's as value. For each y, we traverse from two ends of the set (note numbers in set is sorted). This solution is faster than the first one.

1:  class Solution {  
2:  public:  
3:    bool isReflected(vector<pair<int, int>>& points) {  
4:      unordered_map<int, set<int>> mp;  
5:      int minX = INT_MAX, maxX = INT_MIN;  
6:      for (int i = 0; i < points.size(); i++) {  
7:        minX = min(points[i].first, minX);  
8:        maxX = max(points[i].first, maxX);  
9:        mp[points[i].second].insert(points[i].first);  
10:      }  
11:      double y = (minX + maxX) * 1.0 / 2;  
12:      for (auto i : mp) {  
13:        set<int> tmp = i.second;  
14:        for (auto start = tmp.begin(), end = tmp.end(); start != end; start++) {  
15:          if ((*start + *--end) / 2.0 != y) return false;  
16:          if (start == end) break;  
17:        }  
18:      }  
19:      return true;  
20:    }  
21:  };  

375. Guess Number Higher or Lower II

Let dp[i][j] be the minimum cost among  [i...j] on worst cases. So, To compute dp[i][j], we need to traverse every number among [i...j] for worst cases cost and select the minimum cost among these worst cases.
To compute worst case for k in [i...j], we have worst = (k + max(dp[i][k-1], dp[k+1][j])).
To get the minimum cost among [i...j], we just pick the choose min(cost, worst) for each worst.

1:  class Solution {  
2:  public:  
3:    int getMoneyAmount(int n) {  
4:      vector<vector<int>> dp(n+1, vector<int>(n+1, 0));  
5:      return helper(dp, 1, n);  
6:    }  
7:    int helper(vector<vector<int>> &dp, int s, int e) {  
8:      if (s >= e) return 0;  
9:      if (dp[s][e] != 0) return dp[s][e];  
10:      int cost = INT_MAX;  
11:      for (int i = s; i <= e; i++) {  
12:        int worst = i + max(helper(dp, s, i-1), helper(dp, i+1, e));  
13:        cost = min(cost, worst);  
14:      }  
15:      dp[s][e] = cost;  
16:      return cost;  
17:    }  
18:  };  

353. Design Snake Game

After visiting the top rated solutions, I know all we need to do is to maintain a double linked queue. Every move, we get the front node's row index and column index. Then we compute the new front's row and column index. And we also need to pop out the tail node. If the new front node is valid, i.e. it is in the board and also it doesn't hit the snake. Then the question is how to know if it hits the snake? This can be done by hash set. The hash set caches all the nodes' positions. As long as the new node can be found in the hash set, we know it hits the snake itself. Since we have a hash set to keep all the nodes' position, whenever we remove/insert a new node from/into the queue, we need to erase/insert it from/into the hash set too. Note, we need to remove the tail BEFORE checking otherwise the snake is one longer than it should be. If the new node is valid, we push the new node to the front and insert it into hash set. And then we check if the new node hits a food. If so, we increment the score and we push the tail back to the queue back.

When I revisited this problem, I missed line 35. It's important to check the index before accessing an array.

1:  class SnakeGame {  
2:  private:  
3:    int w, h, i;  
4:    deque<pair<int, int>> q;  
5:    vector<pair<int, int>> f;  
6:    set<pair<int, int>> s;  
7:  public:  
8:    /** Initialize your data structure here.  
9:      @param width - screen width  
10:      @param height - screen height   
11:      @param food - A list of food positions  
12:      E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */  
13:    SnakeGame(int width, int height, vector<pair<int, int>> food) {  
14:      w = width, h = height, i = 0;  
15:      f = food;  
16:      q.push_back(make_pair(0, 0));  
17:    }  
18:    /** Moves the snake.  
19:      @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down   
20:      @return The game's score after the move. Return -1 if game over.   
21:      Game over when snake crosses the screen boundary or bites its body. */  
22:    int move(string direction) {  
23:      pair<int, int> head = q.front();  
24:      pair<int, int> tail = q.back();  
25:      int r = head.first, c = head.second;  
26:      q.pop_back();  
27:      s.erase(tail);  
28:      if (direction == "U") r--;  
29:      else if (direction == "D") r++;  
30:      else if (direction == "R") c++;  
31:      else if (direction == "L") c--;  
32:      if (r < 0 || r == h || c < 0 || c == w || s.count(make_pair(r, c))) return -1;  
33:      q.push_front(make_pair(r, c));  
34:      s.insert(make_pair(r, c));  
35:      if (i == f.size()) return q.size()-1;  
36:      if (f[i].first == r && f[i].second == c) {  
37:        q.push_back(tail);  
38:        s.insert(make_pair(tail.first, tail.second));  
39:        i++;  
40:      }  
41:      return q.size()-1;  
42:    }  
43:  };  
44:  /**  
45:   * Your SnakeGame object will be instantiated and called as such:  
46:   * SnakeGame obj = new SnakeGame(width, height, food);  
47:   * int param_1 = obj.move(direction);  
48:   */  

358. Rearrange String k Distance Apart

This is similar idea to the count sort. First of all, we use hash table to mapping the letter and their appearance times in the input string. And then we want to reorder the string by place k different letters in a row. How can we achieve that? We want to place the letter that has most appearance first. Why? If you place the least appearance first, then you'll be ending up having most appearance letters only and not being able to make k different letters in a row early on. So we think of maximum heap for help. The maximum heap honors the appearance time. Once we place a letter, we need to remove the letter from the heap because it could be still the letter with most appearance but we can't place it until we've place k letters. On the other hand, we still need to cache the removed letters if they still have one more appearance. Once we finish placing k different letters, we push the cached letters back to the heap. Now, the question is in what situation we can't rearrange the string? When we are rearranging k letters, as long as the heap has more than k letters we are find. However, if the heap becomes empty (note we are removing letters when we've placed them), it means we can't make k different letters in a row. At this moment, we know that this string can't be rearranged.

1:  class Solution {  
2:  public:  
3:    string rearrangeString(string str, int k) {  
4:      if (k == 0) return str;  
5:      int l = str.size();  
6:      string res;  
7:      unordered_map<char, int> mp;  
8:      priority_queue<pair<int, char>> pq;  
9:      for (int i = 0; i < l; i++) mp[str[i]]++;  
10:      for (auto it : mp) pq.push(make_pair(it.second, it.first));  
11:      while (!pq.empty()) {  
12:        vector<pair<int, char>> cache;  
13:        int c = min(l, k);  
14:        for (int i = 0; i < c; i++) {  
15:          if (pq.empty()) return "";  
16:          pair<int, char> tmp = pq.top();  
17:          pq.pop();  
18:          res += tmp.second;  
19:          if (--tmp.first > 0) cache.push_back(tmp);  
20:          l--;  
21:        }  
22:        for (auto i : cache) pq.push(i);  
23:      }  
24:      return res;  
25:    }  
26:  };  

373. Find K Pairs with Smallest Sums

The idea is to try every pair of nums1 and nums2. For each pairs, we maintain a maximum heap. The heap order is determined by the sum of pair.  So when the heap size is less than k, we push the new pair to the heap. When the heap size is k, then we need to check if the new pair's sum is less than the heap top pair. If so, we push the new pair into heap and pop out the heap top. In the end, we output all the pairs in the heap.

1:  class Solution {  
2:  struct mycompare {  
3:    bool operator()(pair<int, int> &p1, pair<int, int> &p2) {  
4:      return p1.first + p1.second < p2.first + p2.second;  
5:    }  
6:  };  
7:  public:  
8:    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {  
9:      priority_queue<pair<int, int>, vector<pair<int, int>>, mycompare> pq;  
10:      vector<pair<int, int>> res;  
11:      for (int i = 0; i < nums1.size(); i++) {  
12:        for (int j = 0; j < nums2.size(); j++) {  
13:          if (pq.size() < k) {  
14:            pq.push(make_pair(nums1[i], nums2[j]));  
15:          } else if (nums1[i] + nums2[j] < pq.top().first + pq.top().second) {  
16:            pq.push(make_pair(nums1[i], nums2[j]));  
17:            pq.pop();  
18:          }  
19:        }  
20:      }  
21:      while (!pq.empty()) {  
22:        res.push_back(pq.top());  
23:        pq.pop();  
24:      }  
25:      return res;  
26:    }  
27:  };  

When I revisited the problem, I maintained a minimum heap and pushed all the pairs into the minimum heap and output the top k pairs. Obviously, it is wasting space as well time and easy to make mistake in line 18. The solution above is much better.

1:  class Solution {  
2:  private:  
3:    class compare {  
4:    public:  
5:      bool operator() (pair<int, int> &a, pair<int, int> &b) {  
6:        return a.first + a.second > b.first + b.second;  
7:      }  
8:    };  
9:  public:  
10:    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {  
11:      priority_queue<pair<int, int>, vector<pair<int,int>>, compare> minHeap;  
12:      for (int i = 0; i < nums1.size(); i++) {  
13:        for (int j = 0; j < nums2.size(); j++) {  
14:          minHeap.push(make_pair(nums1[i], nums2[j]));  
15:        }  
16:      }  
17:      vector<pair<int, int>> res;  
18:      while (!minHeap.empty() && k) {  
19:        res.push_back(minHeap.top());  
20:        minHeap.pop();  
21:        k--;  
22:      }  
23:      return res;  
24:    }  
25:  };  

There is more efficient way mentioned by the top rated solution. Need to investigate later.

My intuition is to use DFS. Similar to problem of "Number to Islands". The mistake I made is in red. I need to mark the visited position otherwise, I'll get infinite recursive DFS call. Also the rectangle corner points should be updated in the beginning of DFS.

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

There is a binary search solution in the top rated solutions but I don't quite understand. Need to revisit.

251. Flatten 2D Vector

I was thinking to maintain a queue. But soon, I realized I only need to maintain the row index and column index. In hasNext() we need to check if row index reaches the boundary and the column index reaches the boundary. If row index is not reaching the boundary and column index is on the boundary, we need to move one row below and initialize column index to 0. The reason we use while loop is there could be empty rows. We should return true if row index is not on the boundary.

1:  class Vector2D {  
2:  private:  
3:    int i, j;  
4:    vector<vector<int>> vecs;  
5:  public:  
6:    Vector2D(vector<vector<int>>& vec2d) {  
7:      vecs = vec2d;  
8:      i = 0, j = 0;  
9:    }  
10:    int next() {  
11:      return vecs[i][j++];  
12:    }  
13:    bool hasNext() {  
14:      while (i < vecs.size() && vecs[i].size() == j) {  
15:        i++, j = 0;  
16:      }  
17:      return i < vecs.size();  
18:    }  
19:  };  
20:  /**  
21:   * Your Vector2D object will be instantiated and called as such:  
22:   * Vector2D i(vec2d);  
23:   * while (i.hasNext()) cout << i.next();  
24:   */  

348. Design Tic-Tac-Toe

I solved it in naive way. The running time is O(n) which is not bad.
The top rated solution solves this problem in O(1). The idea is there is only two players and they can cancel each other.
When I revisited this problem, I made mistake in:
line 10: I missed to initialize these two members. This will lead to success for single case but failure for the whole test cases.
line 25: I missed abs() function. Since player2 adds -1 so he will win when the sum becomes -m.

1:  class TicTacToe {  
2:  private:  
3:    vector<int> rows;  
4:    vector<int> cols;  
5:    int diag;  
6:    int anti;  
7:    int m;  
8:  public:  
9:    /** Initialize your data structure here. */  
10:    TicTacToe(int n): rows(n), cols(n), m(n), diag(0), anti(0) {}  
11:    /** Player {player} makes a move at ({row}, {col}).  
12:      @param row The row of the board.  
13:      @param col The column of the board.  
14:      @param player The player, can be either 1 or 2.  
15:      @return The current winning condition, can be either:  
16:          0: No one wins.  
17:          1: Player 1 wins.  
18:          2: Player 2 wins. */  
19:    int move(int row, int col, int player) {  
20:      int a = player == 1 ? 1 : -1;  
21:      rows[row] += a;  
22:      cols[col] += a;  
23:      diag += row == col ? a : 0;  
24:      anti += row == m-1-col ? a : 0;  
25:      if (abs(rows[row]) == m || abs(cols[col]) == m || abs(diag) == m || abs(anti) == m) return player;  
26:      return 0;  
27:    }  
28:  };  
29:  /**  
30:   * Your TicTacToe object will be instantiated and called as such:  
31:   * TicTacToe obj = new TicTacToe(n);  
32:   * int param_1 = obj.move(row,col,player);  
33:   */  

272. Closest Binary Search Tree Value II

The O(n) solution will be straight forward. We can output all the nodes into an array, find the position where target is supposed in and move two pointers as predecessor and successor to output the closest k numbers. This also can be done by two stacks.

1:  class Solution {  
2:  public:  
3:    vector<int> closestKValues(TreeNode* root, double target, int k) {  
4:      vector<int> nodes;  
5:      vector<int> res;  
6:      inorder(root, nodes);  
7:      if (nodes.size() == 0) return res;  
8:      int l = 0, r = nodes.size()-1;  
9:      if (target < nodes[l]) {  
10:        while (k--) res.push_back(nodes[l++]);  
11:        return res;  
12:      }  
13:      if (target > nodes[r]) {  
14:        while (k--) res.push_back(nodes[r--]);  
15:        return res;  
16:      }  
17:      while (l <= r) {  
18:        int mid = l + (r - l) / 2;  
19:        if (nodes[mid] == target) {r = mid; break;}  
20:        else if (nodes[mid] > target) r = mid - 1;  
21:        else l = mid+1;  
22:      }  
23:      l = r;  
24:      r = l+1;  
25:      while (k--) {  
26:        if (l < 0) res.push_back(nodes[r++]);  
27:        else if (r == nodes.size()) res.push_back(nodes[l--]);  
28:        else if (abs(nodes[l]-target) < abs(nodes[r]-target)) {  
29:          res.push_back(nodes[l--]);  
30:        } else {  
31:          res.push_back(nodes[r++]);  
32:        }  
33:      }  
34:      return res;  
35:    }  
36:    void inorder(TreeNode *root, vector<int> &nodes) {  
37:      if (root == NULL) return;  
38:      inorder(root->left, nodes);  
39:      nodes.push_back(root->val);  
40:      inorder(root->right, nodes);  
41:    }  
42:  };  

There is another way to maintain the predecessor and successor stack by traversing the tree in inorder and reverse-inorder.

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> closestKValues(TreeNode* root, double target, int k) {  
13:      stack<int> predecessor;  
14:      stack<int> successor;  
15:      inorder(root, false, predecessor, target);  
16:      inorder(root, true, successor, target);  
17:      vector<int> res;  
18:      while (k--) {  
19:        if (predecessor.empty()) {  
20:          res.push_back(successor.top());  
21:          successor.pop();  
22:        } else if (successor.empty()) {  
23:          res.push_back(predecessor.top());  
24:          predecessor.pop();  
25:        } else if (abs(predecessor.top()-target) < abs(successor.top()-target)) {  
26:          res.push_back(predecessor.top());  
27:          predecessor.pop();  
28:        } else {  
29:          res.push_back(successor.top());  
30:          successor.pop();  
31:        }  
32:      }  
33:      return res;  
34:    }  
35:    void inorder(TreeNode *root, bool reverse, stack<int> &stk, double target) {  
36:      if (root == NULL) return;  
37:      inorder(reverse ? root->right : root->left, reverse, stk, target);  
38:      if ((reverse && root->val <= target) || ((!reverse) && root->val > target)) return;  
39:      stk.push(root->val);  
40:      inorder(reverse ? root->left : root->right, reverse, stk, target);  
41:    }  
42:  };  

And this problem actually can be converted to a design problem with two methods getPredecessor() and getSuccessor(). We can stop searching the BST when we find the closest predecessor and successor to target. And we can update the predecessor stack and successor stack in these two methods respectively. So the running time will be O(klogn);

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:    stack<treenode> pred;  
13:    stack<treenode> succ;  
14:  public:  
15:    vector<int> closestKValues(TreeNode* root, double target, int k) {  
16:      vector<int> res;  
17:      initPredecessor(root, target);  
18:      initSuccessor(root, target);  
19:      if (!succ.empty() &amp;&amp; !pred.empty() &amp;&amp; succ.top()-&gt;val == pred.top()-&gt;val) {  
20:        getNextPredecessor();  
21:      }  
22:      while (k--) {  
23:        if (succ.empty()) res.push_back(getNextPredecessor());  
24:        else if (pred.empty()) res.push_back(getNextSuccessor());  
25:        else if (abs(succ.top()->val - target) < abs(pred.top()->val - target)) {  
26:          res.push_back(getNextSuccessor());  
27:        } else {  
28:          res.push_back(getNextPredecessor());  
29:        }  
30:      }  
31:      return res;  
32:    }  
33:    void initPredecessor(TreeNode *root, double target) {  
34:      while (root) {  
35:        if (root->val == target) {  
36:          pred.push(root);  
37:          break;  
38:        } else if (root->val < target) {  
39:          pred.push(root);  
40:          root = root->right;  
41:        } else {  
42:          root = root->left;  
43:        }  
44:      }  
45:    }  
46:    void initSuccessor(TreeNode *root, double target) {  
47:      while (root) {  
48:        if (root->val == target) {  
49:          succ.push(root);  
50:          break;  
51:        } else if (root->val > target) {  
52:          succ.push(root);  
53:          root = root->left;  
54:        } else {  
55:          root = root->right;  
56:        }  
57:      }  
58:    }  
59:    int getNextPredecessor() {  
60:      TreeNode *root = pred.top();  
61:      pred.pop();  
62:      int res = root->val;  
63:      root = root->left;  
64:      while (root) {  
65:        pred.push(root);  
66:        root = root-&gt;right;  
67:      }  
68:      return res;  
69:    }  
70:    int getNextSuccessor() {  
71:      TreeNode *root = succ.top();  
72:      succ.pop();  
73:      int res = root->val;  
74:      root = root->right;  
75:      while (root) {  
76:        succ.push(root);  
77:        root = root->left;  
78:      }  
79:      return res;  
80:    }  
81:  };  

The second time I revisited this problem, I found that initPredecessor() and initSuccessor() can be combined into one function.

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:    stack<TreeNode *> pred;  
13:    stack<TreeNode *> succ;  
14:  public:  
15:    vector<int> closestKValues(TreeNode* root, double target, int k) {  
16:      vector<int> res;  
17:      if (root == NULL) return res;  
18:      initStacks(root, target);  
19:      while (k) {  
20:        if (pred.empty()) res.push_back(getNextPredecessor());  
21:        else if (succ.empty()) res.push_back(getNextSuccessor());  
22:        else if (abs(pred.top()->val-target) < abs(succ.top()->val-target)) {  
23:          res.push_back(getNextPredecessor());  
24:        } else {  
25:          res.push_back(getNextSuccessor());  
26:        }  
27:        k--;  
28:      }  
29:      return res;  
30:    }  
31:    void initStacks(TreeNode *root, double target) {  
32:      while (root != NULL) {  
33:        if (root->val <= target) {  
34:          pred.push(root);  
35:          root = root->right;  
36:        } else {  
37:          succ.push(root);  
38:          root = root->left;  
39:        }  
40:      }  
41:    }  
42:    int getNextPredecessor() {  
43:      TreeNode *t = pred.top();  
44:      int ret = t->val;  
45:      pred.pop();  
46:      t = t->left;  
47:      while (t) {  
48:        pred.push(t);  
49:        t = t->right;  
50:      }  
51:      return ret;  
52:    }  
53:    int getNextSuccessor() {  
54:      TreeNode *t = succ.top();  
55:      int ret = t->val;  
56:      succ.pop();  
57:      t = t->right;  
58:      while (t) {  
59:        succ.push(t);  
60:        t = t->left;  
61:      }  
62:      return ret;  
63:    }  
64:  };  

294. Flip Game II

The idea is to exhaust all the ways by backtracking. As long as there is a way to prevent the other from winning, we stop the backtracking.

1:  class Solution {  
2:  private:  
3:    string ss;  
4:    int len;  
5:  public:  
6:    bool canWin(string s) {  
7:      len = s.size();  
8:      ss = s;  
9:      return helper();  
10:    }  
11:    bool helper() {  
12:      for (int i = 0; i < len-1; i++) {  
13:        if (ss[i] == '+' && ss[i+1] == '+') {  
14:          ss[i] = ss[i+1] = '-'; // make the move  
15:          bool win = helper();  
16:          ss[i] = ss[i+1] = '+'; // restore the move  
17:          if (!win) return true;  
18:        }  
19:      }  
20:      return false;  
21:    }  
22:  };  

When I revisited this code, I got much conciser code:

1:  class Solution {  
2:  public:  
3:    bool canWin(string s) {  
4:      for (int i = 0; i+1 < s.size(); i++) {  
5:        if (s[i] == '+' && s[i+1] == '+') {  
6:          s[i] = s[i+1] = '-';  
7:          if (!canWin(s)) return true;  
8:          s[i] = s[i+1] = '+';  
9:        }  
10:      }  
11:      return false;  
12:    }  
13:  };  

351. Android Unlock Patterns

I was trying to naive DFS to search up to 8 neighbors for each number on pad. But I realized that such way has some issues. First of all, the valid pattern includes [1]-[8] where 8 is not a direct neighbor for 1. Also [1]-[2]-[1]-[4] is a valid pattern for m = 3 which complicates the usage of visited matrix. The top rated solution has a very clever way by using a skip matrix to solve the problem. In the dfs function, it just checks from 1 to 9 to see if they are next to each other or the number between them has been visited before so that they becomes next again.

1:  class Solution {  
2:  public:  
3:    int numberOfPatterns(int m, int n) {  
4:      vector<vector<int>> skip(10, vector<int>(10, 0));  
5:      skip[1][3] = skip[3][1] = 2;  
6:      skip[1][7] = skip[7][1] = 4;  
7:      skip[3][9] = skip[9][3] = 6;  
8:      skip[7][9] = skip[9][7] = 8;  
9:      skip[2][8] = skip[8][2] = skip[4][6] = skip[6][4] = skip[1][9] = skip[9][1] = skip[3][7] = skip[7][3] = 5;  
10:      int res = 0;  
11:      vector<bool> visited(10, 0);  
12:      for (int l = m; l <= n; l++) {  
13:        res += dfs(1, skip, visited, l-1) * 4;  
14:        res += dfs(2, skip, visited, l-1) * 4;  
15:        res += dfs(5, skip, visited, l-1);  
16:      }  
17:      return res;  
18:    }  
19:    int dfs(int n, vector<vector<int>> &skip, vector<bool> &visited, int l) {  
20:      if (l == 0) return 1;  
21:      int res = 0;  
22:      visited[n] = true;  
23:      for (int i = 1; i <= 9; i++) {  
24:        if (!visited[i] && (skip[n][i] == 0 || visited[skip[n][i]])) {  
25:          res += dfs(i, skip, visited, l-1);  
26:        }  
27:      }  
28:      visited[n] = false;  
29:      return res;  
30:    }  
31:  };  

271. Encode and Decode Strings

The idea is easy. To have a fixed length header to contain the length of the string. When decode, parse the header and get the string whose length is specified by the header.

When I revisited this problem, I made mistake in
line 9: I mistakenly had "res += to_string(strs[i].size()) + string(HEAD_SIZE-strs[i].size(), '.' + strs[i]". Note, the head size should be the size of the converted head size number.
line 17: I mistakenly had "i++" in the end.

1:  #define HEAD_SIZE 16  
2:  class Codec {  
3:  public:  
4:    // Encodes a list of strings to a single string.  
5:    string encode(vector<string>& strs) {  
6:      string res;  
7:      for (int i = 0; i < strs.size(); i++) {  
8:        string s = to_string(strs[i].size());  
9:        string append = string(HEAD_SIZE-s.size(), '.');  
10:        res += s + append + strs[i];  
11:      }  
12:      return res;  
13:    }  
14:    // Decodes a single string to a list of strings.  
15:    vector<string> decode(string s) {  
16:      vector<string> res;  
17:      for (int i = 0; i < s.size();) {  
18:        string head = s.substr(i, HEAD_SIZE);  
19:        int len = stol(head, NULL, 10);  
20:        i += HEAD_SIZE;  
21:        if (len > 0) res.push_back(s.substr(i, len));  
22:        else res.push_back("");  
23:        i += len;  
24:      }  
25:      return res;  
26:    }  
27:  };  
28:  // Your Codec object will be instantiated and called as such:  
29:  // Codec codec;  
30:  // codec.decode(codec.encode(strs));  

340. Longest Substring with At Most K Distinct Characters

I implemented a naive code first. And of course, it doesn’t pass large test set.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstringKDistinct(string s, int k) {  
4:      if (s.size() < k) return s.size();  
5:      int res = 0;  
6:      for (int i = 0; i < s.size(); i++) {  
7:        vector<int> letters(256, 0);  
8:        int count = 0;  
9:        int j = i;  
10:        while (j < s.size()) {  
11:          if (letters[s[j]] == 0) {  
12:            letters[s[j]] = 1;  
13:            count++;  
14:            if (count > k) break;  
15:          }  
16:          j++;  
17:        }  
18:        res = max(res, j-i);  
19:      }  
20:      return res;  
21:    }  
22:  };  

The top rated solution uses sliding window. Keep two pointers as the starting of the window and the end of the window. First of all, keep moving the right end of the window until the distinct characters are more than K. Then move the left end of the window until the distinct characters are equal to K. Then move right end again.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstringKDistinct(string s, int k) {  
4:      int res = 0, j = -1, i = 0, distinct = 0;  
5:      vector<int> chars(256, 0);  
6:      for (; i < s.size(); i++) {  
7:        distinct += chars[s[i]]++ == 0;  
8:        while (distinct > k) {  
9:          distinct -= --chars[s[++j]] == 0;  
10:        }  
11:        res = max(res, i-j);  
12:      }  
13:      return res;  
14:    }  
15:  };  

346. Moving Average from Data Stream

A typical application for queue. When queue is not full, we keep pushing the new number to the queue and compute the sum. When the queue is full, we subtract the front from the sum, pop out the front, push the new number to the end and add the new number to the sum.

1:  class MovingAverage {  
2:  private:  
3:    queue<int> que;  
4:    int m_size;  
5:    int sum;  
6:  public:  
7:    /** Initialize your data structure here. */  
8:    MovingAverage(int size) {  
9:      m_size = size;  
10:      sum = 0;  
11:    }  
12:    double next(int val) {  
13:      if (que.size() != m_size) {  
14:        que.push(val);  
15:        sum += val;  
16:      } else {  
17:        sum -= que.front();  
18:        que.pop();  
19:        que.push(val);  
20:        sum += val;  
21:      }  
22:      return sum * 1.0 / que.size();  
23:    }  
24:  };  
25:  /**  
26:   * Your MovingAverage object will be instantiated and called as such:  
27:   * MovingAverage obj = new MovingAverage(size);  
28:   * double param_1 = obj.next(val);  
29:   */  

270. Closest Binary Search Tree Value

Binary search. We should note that for BST to find place for a new node to insert, we must reach a NULL pointer. So the termination for binary search in BST is either the left or the right child node that we are ready to move to becomes NULL. We only need to compare the root node with the closest node in its subtree in order to get the right one.

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 closestValue(TreeNode* root, double target) {  
13:      int a = root->val;  
14:      TreeNode *child = target < a ? root->left : root->right;  
15:      if (child == NULL) return a;  
16:      int b = closestValue(child, target);  
17:      return abs(a - target) < abs(b - target) ? a : b;  
18:    }  
19:  };  

247. Strobogrammatic Number II

Follow the tips, I realized that this problem can be solved by backtracking. I was trying to design the backtracking API to include the final result. But it turns out not working and can complicate the solution. So I followed the API of top rated solution, i.e. the backtracking function returns the result. Also, it is important to do backtracking with n-2 not n-1.

1:  class Solution {  
2:  public:  
3:    vector<string> findStrobogrammatic(int n) {  
4:      return helper(n, n);  
5:    }  
6:    vector<string> helper(int n, int m) {  
7:      if (n == 0) return vector<string> {""};  
8:      if (n == 1) return vector<string> {"0", "1", "8"};  
9:      vector<string> tmp = helper(n-2, m), res;  
10:      for (int i = 0; i < tmp.size(); i++) {  
11:        if (n != m) res.push_back("0" + tmp[i] + "0");  
12:        res.push_back("1" + tmp[i] + "1");  
13:        res.push_back("8" + tmp[i] + "8");  
14:        res.push_back("6" + tmp[i] + "9");  
15:        res.push_back("9" + tmp[i] + "6");  
16:      }  
17:      return res;  
18:    }  
19:  };  

305. Number of Islands II

There is a good video talking about Union Find for dynamic connectivity problem.
https://www.youtube.com/watch?v=dxONo9jDbN8
And here is its improvement.
https://www.youtube.com/watch?v=SpqjfGTOriQ
The idea is, check each pointer and its neighbors. If the neighbor is water, then do nothing. Otherwise, find the roots for node itself and the neighbor. If they don’t have the same parent, then do union.

When I revisited the problem, I made mistake in
line 11&16: I computed the index by "i * m + j".
line 17&19: I ignored when the neighbor isn't water and union the islands when two islands is connected (Really don't know what I was thinking...).

1:  class Solution {  
2:  public:  
3:    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {  
4:      vector<int> res;  
5:      if (n == 0 || n == 0) return res;  
6:      vector<int> roots(m * n, -1);  
7:      vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
8:      int count = 0;  
9:      for (int k = 0; k < positions.size(); k++) {  
10:        count++;  
11:        int r = positions[k].first * n + positions[k].second;  
12:        roots[r] = r;  
13:        for (int l = 0; l < 4; l++) {  
14:          int i = positions[k].first + dir[l].first;  
15:          int j = positions[k].second + dir[l].second;  
16:          int nr = i * n + j;  
17:          if (i < 0 || i == m || j < 0 || j == n || roots[nr] == -1) continue;  
18:          int r1 = findIslands(roots, nr), r2 = findIslands(roots, r);  
19:          if (r1 != r2) {  
20:            count--;  
21:            roots[r1] = r2; // union the two islands  
22:          }  
23:        }  
24:        res.push_back(count);  
25:      }  
26:      return res;  
27:    }  
28:    int findIslands(vector<int> &roots, int id) {  
29:      while (roots[id] != id) {  
30:        // path compression: make every other node to point to its grandparent  
31:        roots[id] = roots[roots[id]];   
32:        id = roots[id];  
33:      }  
34:      return id;  
35:    }  
36:  };  

159. Longest Substring with At Most Two Distinct Characters

Same as problem “340. Longest Substring with At Most K Distinct Characters”.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstringTwoDistinct(string s) {  
4:      int i = 0, j = -1;  
5:      vector<int> dict(256, 0);  
6:      int len = 0;  
7:      int k = 0;  
8:      while (i < s.size()) {  
9:        k += dict[s[i]]++ == 0;  
10:        while (k > 2) k -= --dict[s[++j]] == 0;  
11:        len = max(len, i-j);  
12:        i++;  
13:      }  
14:      return len;  
15:    }  
16:  };  

276. Paint Fence

When there is only one fence, we have total k ways to paint.
When there is two fence, for the second fence, we can paint the same color with the first one and the total ways to paint these two posts is k. OR we can paint the different color and the total ways to paint these two posts is k*(k-1). If we can keep the total ways to paint ith post, then the ways for ith post is
Case 1: i-1 and i-2 have the same color, then the ways to paint is (k-1) * dp[i-2]
Case 2: i-1 and i-2 have different colors, then the ways to paint is (k-1) * dp[i-1]
So the dp[i] = (dp[i-2] + dp[i-1])*(k-1);

1:  class Solution {  
2:  public:  
3:    int numWays(int n, int k) {  
4:      if (n == 0) return 0;  
5:      if (n == 1) return k;  
6:      vector<int> dp(n, 0);  
7:      dp[0] = k;  
8:      dp[1] = k+k*(k-1);  
9:      for (int i = 2; i < n; i++) {  
10:        dp[i] = (dp[i-1] + dp[i-2]) * (k-1);  
11:      }  
12:      return dp[n-1];  
13:    }  
14:  };  

Also, this DP solution can be optimized to have O(1) space because we only care about previous two states.

1:  class Solution {  
2:  public:  
3:    int numWays(int n, int k) {  
4:      if (n == 0) return 0;  
5:      if (n == 1) return k;  
6:      int n_2 = k, n_1 = k*(k-1);  
7:      for (int i = 2; i < n; i++) {  
8:        int tmp = n_1;  
9:        n_1 = (n_2 + n_1) * (k-1);  
10:        n_2 = tmp;  
11:      }  
12:      return n_2 + n_1;  
13:    }  
14:  };