Showing posts with label topology sort. Show all posts
Showing posts with label topology sort. Show all posts

Wednesday, August 10, 2016

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

Thursday, July 7, 2016

329. Longest Increasing Path in a Matrix

My intituition is topology sort. I tried typical DFS solution for this problem as following, i.e. having a visited table to record if a node is visited. However, I got TLE.

1:  class Solution {  
2:  private:  
3:    int rows;  
4:    int cols;  
5:  public:  
6:    int longestIncreasingPath(vector<vector<int>>& matrix) {  
7:      rows = matrix.size();  
8:      if (rows == 0) return 0;  
9:      cols = matrix[0].size();  
10:      vector<vector<bool>> path(rows, vector<bool>(cols, false));  
11:      int maxLen = 0;  
12:      for (int i = 0; i < rows; i++) {  
13:        for (int j = 0; j < cols; j++) {  
14:          maxLen = max(maxLen, dfs(matrix, path, i, j));  
15:        }  
16:      }  
17:      return maxLen;  
18:    }  
19:    int dfs(vector<vector<int>> &matrix, vector<vector<bool>> &path, int i, int j) {  
20:      path[i][j] = true;  
21:      int len = 1;  
22:      if (i > 0 && !path[i-1][j] && matrix[i][j] < matrix[i-1][j]) len = max(len, 1+dfs(matrix, path, i-1, j));  
23:      if (j > 0 && !path[i][j-1] && matrix[i][j] < matrix[i][j-1]) len = max(len, 1+dfs(matrix, path, i, j-1));  
24:      if (i+1<rows && !path[i+1][j] && matrix[i][j] < matrix[i+1][j]) len = max(len, 1+dfs(matrix, path, i+1, j));  
25:      if (j+1<cols && !path[i][j+1] && matrix[i][j] < matrix[i][j+1]) len = max(len, 1+dfs(matrix, path, i, j+1));  
26:      path[i][j] = false;  
27:      return len;  
28:    }  
29:  };  

After revisiting my algorithm, I realized that if we can have the visited[i][j] to record the maximum length so far, I don’t have to go deep and it saves a lot of dfs time.

1:  class Solution {  
2:  private:  
3:    int rows;  
4:    int cols;  
5:  public:  
6:    int longestIncreasingPath(vector<vector<int>>& matrix) {  
7:      rows = matrix.size();  
8:      if (rows == 0) return 0;  
9:      cols = matrix[0].size();  
10:      vector<vector<int>> pathLength(rows, vector<int>(cols, false));  
11:      int maxLen = 0;  
12:      for (int i = 0; i < rows; i++) {  
13:        for (int j = 0; j < cols; j++) {  
14:          maxLen = max(maxLen, dfs(matrix, pathLength, i, j));  
15:        }  
16:      }  
17:      return maxLen;  
18:    }  
19:    int dfs(vector<vector<int>> &matrix, vector<vector<int>> &pathLength, int i, int j) {  
20:      if (pathLength[i][j] != 0) return pathLength[i][j];  
21:      int len = 1;  
22:      if (i > 0 && matrix[i][j] < matrix[i-1][j]) len = max(len, 1+dfs(matrix, pathLength, i-1, j));  
23:      if (j > 0 && matrix[i][j] < matrix[i][j-1]) len = max(len, 1+dfs(matrix, pathLength, i, j-1));  
24:      if (i+1<rows && matrix[i][j] < matrix[i+1][j]) len = max(len, 1+dfs(matrix, pathLength, i+1, j));  
25:      if (j+1<cols && matrix[i][j] < matrix[i][j+1]) len = max(len, 1+dfs(matrix, pathLength, i, j+1));  
26:      pathLength[i][j] = len;  
27:      return pathLength[i][j];  
28:    }  
29:  };  

When I revisited this problem, I made mistake in line 25. Instead of dfs, I had "dp[i][j] = max(dp[i][j], dp[ii][jj]+1)" because this seems to be sufficient for the example given by the problem. However, for case like [[3,4,5], [3,2,6], [2,2,1]] it is completely wrong.

1:  class Solution {  
2:  private:  
3:    int rows, cols;  
4:    vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};  
5:  public:  
6:    int longestIncreasingPath(vector<vector<int>>& matrix) {  
7:      rows = matrix.size();  
8:      if (rows == 0) return 0;  
9:      cols = matrix[0].size();  
10:      int maxLen = 0;  
11:      vector<vector<int>> dp(rows, vector<int>(cols, 1));  
12:      for (int i = 0; i < rows; i++) {  
13:        for (int j = 0; j < cols; j++) {  
14:          maxLen = max(maxLen, dfs(matrix, i, j, dp));  
15:        }  
16:      }  
17:      return maxLen;  
18:    }  
19:    int dfs(vector<vector<int>> &matrix, int i, int j, vector<vector<int>> &dp) {  
20:      if (dp[i][j] != 1) return dp[i][j];  
21:      for (int d = 0; d < dir.size(); d++) {  
22:        int ii = i + dir[d].first;  
23:        int jj = j + dir[d].second;  
24:        if (ii < 0 || ii == rows || jj < 0 || jj == cols || matrix[i][j] >= matrix[ii][jj]) continue;  
25:        dp[i][j] = max(dp[i][j], dfs(matrix, ii, jj, dp) + 1);  
26:      }  
27:      return dp[i][j];  
28:    }  
29:  };  

Monday, July 4, 2016

210. Course Schedule II

Same as "Course Schedule I". The only difference is push the course into result.

1:  class Solution {  
2:  public:  
3:    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {  
4:      vector<unordered_set<int>> graph = construct(numCourses, prerequisites);  
5:      vector<bool> path(numCourses, false), visited(numCourses, false);  
6:      vector<int> res;  
7:      for (int i = 0; i < numCourses; i++) {  
8:        if (!visited[i] && dfs(graph, i, path, visited, res)) return vector<int>{};  
9:      }  
10:      return res;  
11:    }  
12:    bool dfs(vector<unordered_set<int>> &graph, int course, vector<bool> &path, vector<bool> &visited, vector<int> &res) {  
13:      if (visited[course]) return false;  
14:      path[course] = visited[course] = true;  
15:      for (int p : graph[course]) {  
16:        if (path[p] || dfs(graph, p, path, visited, res)) return true;  
17:      }  
18:      res.push_back(course);  
19:      path[course] = false;  
20:      return false;  
21:    }  
22:    vector<unordered_set<int>> construct(int numCourses, vector<pair<int,int>>& prerequisites) {  
23:      vector<unordered_set<int>> graph(numCourses);  
24:      for (pair<int, int> p : prerequisites) {  
25:        graph[p.first].insert(p.second);  
26:      }  
27:      return graph;  
28:    }  
29:  };  

Sunday, June 26, 2016

207. Course Schedule

A typical topology sort problem. The following youtube is a very good material explaining topology sort.
https://www.youtube.com/watch?v=XPM9Q2LMxFk&list=PLqD_OdMOd_6YixsHkd9f4sNdof4IhIima&index=11

In this problem, there are three points.
1. use adjacent-list to represent the graph. In c++, the representation can be vector<unordered_set<int>>.
2. To make a successful topology sort, we need to make sure there is no cycle in the graph. This can be done by DFS.
3. We need two vectors to keep track of visited vertex. The visited vector keeps global graph vertex status. The path vector keeps the vertex status in one dfs function, i.e. vertices connected directly or remotely with one particular vertex.

1:  class Solution {  
2:  public:  
3:    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {  
4:      vector<unordered_set<int>> graph(numCourses);  
5:      construct_graph(graph, prerequisites);  
6:      vector<bool> visited(numCourses, false);  
7:      vector<bool> path(numCourses, false);  
8:      for (int i = 0; i < numCourses; i++) {  
9:        if (!visited[i] && dfs(graph, i, path, visited))  
10:          return false;  
11:      }  
12:      return true;  
13:    }  
14:    void construct_graph(vector<unordered_set<int>> &graph, vector<pair<int, int>> &prerequisites) {  
15:      for (int i = 0; i < prerequisites.size(); i++) {  
16:        graph[prerequisites[i].first].insert(prerequisites[i].second);  
17:      }  
18:    }  
19:    bool dfs(vector<unordered_set<int>> &graph, int vertex, vector<bool> &path, vector<bool> &visited) {  
20:      if (visited[vertex]) return false;  
21:      path[vertex] = visited[vertex] = true;  
22:      for (auto v: graph[vertex]) {  
23:        if (path[v] || dfs(graph, v, path, visited)) {  
24:          return true;  
25:        }  
26:      }  
27:      path[vertex] = false;  
28:      return false;  
29:    }  
30:  };   

Note line 21 and line 27, we revert the path[vertex] status to false in the end because path is a reference and we don't find any cycle. The reason we don't have to worry about if dfs() changes the path[v] to false is once we find a cycle we return true all the way up to the top of stack and we don't have to worry about the path again. On the other hand, if no cycle is found, each dfs() will revert the path[vertex] status.