417. Pacific Atlantic Water Flow

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

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

399. Evaluate Division

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

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

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

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

394. Decode String

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

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

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

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

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

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

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

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

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.

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