126. Word Ladder II

Difficulty: Hard

Frequency: N/A

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
        m.clear();
        results.clear();
        path.clear();
        
        wordList.insert(beginWord);
        wordList.insert(endWord);
        
        unordered_set<string> cur_lev;
        cur_lev.insert(beginWord);
        unordered_set<string> next_lev;
        path.push_back(endWord);
        
        while (true) {
            // delete previous level words
            for (auto it = cur_lev.begin(); it != cur_lev.end(); it++) {
                wordList.erase(*it);
            }
            // find current level words
            for (auto it = cur_lev.begin(); it != cur_lev.end(); it++) {
                findDict(*it, wordList, next_lev);
            }
            if (next_lev.empty()) {
                return results;
            }
            // if find endWord
            if (next_lev.find(endWord) != wordList.end()) {
                output(beginWord, endWord);
                return results;
            }
            cur_lev.clear();
            cur_lev = next_lev;
            next_lev.clear();
        }
        return results;
    }
private:
    unordered_map<string, vector<string>> m;
    vector<vector<string>> results;
    vector<string> path;
    void findDict(string word, unordered_set<string>& wordList, unordered_set<string>& next_level) {
        int n = word.size();
        string s = word;
        for (int i = 0; i < n; i++) {
            s = word;
            for (int j = 0; j < 26; j++) {
                s[i] = 'a' + j;
                if (wordList.find(s) != wordList.end()) {
                    next_level.insert(s);
                    m[s].push_back(word);
                }
            }
        }
    }
    void output(string& start, string last) {
        if (last == start) {
            reverse(path.begin(), path.end());
            results.push_back(path);
            reverse(path.begin(), path.end());
        } else {
            for (int i = 0; i < m[last].size(); i++) {
                path.push_back(m[last][i]);
                output(start, m[last][i]);
                path.pop_back();
            }
        }
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

210. Course Schedule II

Difficulty: Medium

Frequency: N/A

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

Hints:

1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS – A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
private:
    vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<unordered_set<int>> graph(numCourses);
        for (auto pre : prerequisites) {
            graph[pre.second].insert(pre.first);
        }
        return graph;
    }
    bool dfs(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited, vector<int>& result) {
        if (visited[node]) return false;
        visited[node] = onpath[node] = true;
        for (int neighbor : graph[node]) {
            if (onpath[neighbor] || dfs(graph, neighbor, onpath, visited, result)) {
                return true;
            }
        }
        result.push_back(node);
        return onpath[node] = false;
    }
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
        vector<bool> onpath(numCourses, false), visited(numCourses, false);
        vector<int> result;
        for (int i = 0; i < numCourses; i++) {
            if (!visited[i] && dfs(graph, i, onpath, visited, result)) {
                return {};
            }
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

207. Course Schedule

Difficulty: Medium

Frequency: N/A

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

Hints:

1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS – A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
private:
    vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<unordered_set<int>> graph(numCourses);
        for (auto pre : prerequisites) {
            graph[pre.second].insert(pre.first);
        }
        return graph;
    }
    bool dfs_cycle(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited) {
        if (visited[node]) return false;
        onpath[node] = visited[node] = true;
        for (int neighbor : graph[node]) {
            if (onpath[neighbor] || dfs_cycle(graph, neighbor, onpath, visited)) {
                return true;
            }
        }
        return onpath[node] = false;
    }
    
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
        vector<bool> onpath(numCourses, false), visited(numCourses, false);
        for (int i = 0; i < numCourses; i++) {
            if (!visited[i] && dfs_cycle(graph, i, onpath, visited)) {
                return false;
            }
        }
        return true;
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

133. Clone Graph

Difficulty: Medium

Frequency: N/A

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return NULL;
        UndirectedGraphNode *p1 = node;
        UndirectedGraphNode *p2 = new UndirectedGraphNode(node->label);
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> m;
        queue<UndirectedGraphNode*> q;
        q.push(node);
        m[node] = p2;
        while (!q.empty()) {
            p1 = q.front();
            p2 = m[p1];
            q.pop();
            for (int i = 0; i < p1->neighbors.size(); i++) {
                UndirectedGraphNode *nb = p1->neighbors[i];
                if (m.count(nb)) {
                    p2->neighbors.push_back(m[nb]);
                } else {
                    UndirectedGraphNode *tmp = new UndirectedGraphNode(nb->label);
                    p2->neighbors.push_back(tmp);
                    m[nb] = tmp;
                    q.push(nb);
                }
            }
        }
        return m[node];
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

127. Word Ladder

Difficulty: Medium

Frequency: N/A

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

---

Test Cases:

---

Solution 1:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Code:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        wordList.insert(endWord);
        queue<string> toVisit;
        addNextWords(beginWord, wordList, toVisit);
        int dist = 2;
        while (!toVisit.empty()) {
            int n = toVisit.size();
            for (int i = 0; i < n; i++) {
                string word = toVisit.front();
                toVisit.pop();
                if (word == endWord) return dist;
                addNextWords(word, wordList, toVisit);
            }
            dist++;
        }
    }
private:
    void addNextWords(string word, unordered_set<string>& wordList, queue<string>& toVisit) {
        wordList.erase(word);
        for (int i = 0; i < (int)word.size(); i++) {
            char c = word[i];
            for (int j = 0; j < 26; j++) {
                word[i] = 'a' + j;
                if (wordList.find(word) != wordList.end()) {
                    toVisit.push(word);
                    wordList.erase(word);
                }
            }
            word[i] = c;
        }
    }
};

---

Solution 2:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Submission errors:

 

---

Things to learn:

103. Binary Tree Zigzag Level Order Traversal

Difficulty: Medium

Frequency: N/A

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> results;
        if (!root) return results;
        deque<TreeNode*> deq;
        deq.push_front(root);
        bool front = true;
        while (!deq.empty()) {
            int s_size = deq.size();
            vector<int> result;
            while (s_size) {
                if (front) {
                    TreeNode *cur = deq.front();
                    deq.pop_front();
                    result.push_back(cur->val);
                    if (cur->left) deq.push_back(cur->left);
                    if (cur->right) deq.push_back(cur->right);
                } else {
                    TreeNode *cur = deq.back();
                    deq.pop_back();
                    result.push_back(cur->val);
                    if (cur->right) deq.push_front(cur->right);
                    if (cur->left) deq.push_front(cur->left);
                }
                s_size--;
            }
            front = !front;
            results.push_back(result);
        }
        return results;
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

317. (Locked)Shortest Distance from All Buildings

Difficulty: Hard

Frequency: N/A

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.
The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x – p1.x| + |p2.y – p1.y|.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 – 0 – 2 – 0 – 1
|    |     |     |    |
0 – 0 – 0 – 0 – 0
|     |     |     |    |
0 – 0 – 1 – 0 – 0
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        if (grid.empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        int nb = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) nb++;
            }
        }
        int result = INT_MAX;
        bool found = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) continue;
                int dist = 0, cnt = 0;
                vector<int> start = {i, j, 0};
                queue<vector<int>> myQ;
                myQ.push(start);
                vector<vector<bool>> visited = (m, vector<int>(n, false));
                visited[i][j] = true;
                while (!myQ.empty()) {
                    int p = myQ.front()[0];
                    int q = myQ.front()[1];
                    int steps = myQ.front()[2];
                    myQ.pop();
                    if (grid[p][q] == 1) {
                        cnt++;
                        dist += steps;
                    }
                    if (grid[p][q] == 0 || (p == i) && (q == j)) {
                        if (p - 1 >= 0 && grid[p - 1][q] > 2 && !visisted[p - 1][q]) {
                            vector<int> tmp = {p - 1, q, steps + 1};
                            myQ.push(tmp);
                            visited[p - 1][q] = true;
                        }
                        if (p + 1 < m && grid[p + 1][q] > 2 && !visisted[p + 1][q]) {
                            vector<int> tmp = {p + 1, q, steps + 1};
                            myQ.push(tmp);
                            visited[p + 1][q] = true;
                        } 
                        if (q - 1 >= 0 && grid[p][q - 1] > 2 && !visisted[p][q - 1]) {
                            vector<int> tmp = {p, q - 1, steps + 1};
                            myQ.push(tmp);
                            visited[p][q - 1] = true;
                        }
                        if (q + 1 < n && grid[p][q + 1] > 2 && !visisted[p][q + 1]) {
                            vector<int> tmp = {p, q + 1, steps + 1};
                            myQ.push(tmp);
                            visited[p][q + 1] = true;
                        }       
                    }
                }
                if (grid[i][j] == 1 && cnt < nb) return -1;
                if (grid[i][j] == 0 && cnt == nb) {
                    found = true;
                    result = min(disk, result);
                }
            }
        }
        return found ? result : -1;
    }
}

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

286. (Locked)Walls and Gates

Difficulty: Medium

Frequency: N/A

You are given a m x n 2D grid initialized with these three possible values.

1. -1 – A wall or an obstacle.
2. 0 – A gate.
3. INF – Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

class Solution {
private:
    struct Grid {
        int p, q, d;
        Grid(int p_, int q_, int d_) : p(p_), q(q_), d(d_) {}
    };
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.empty()) return;
        int m = rooms.size(), n = rooms[0].size();
        queue<Grid> myQ;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!rooms[i][j]) {
                    myQ.push(Grid(i - 1, j, 1));
                    myQ.push(Grid(i + 1, j, 1));
                    myQ.push(Grid(i, j - 1, 1));
                    myQ.push(Grid(i, j + 1, 1));
                    while (!myQ.empty()) {
                        Grid cur = myQ.front();
                        myQ.pop();
                        if (cur.p < 0 || cur.p >= m || cur.q < 0 || cur.q > n || rooms[cur.p][cur.q] < d) continue;
                        rooms[cur.p][cur.q] = d;
                        myQ.push(Grid(cur.p - 1, cur.q, d + 1));
                        myQ.push(Grid(cur.p + 1, cur.q, d + 1));
                        myQ.push(Grid(cur.p, cur.q - 1, d + 1));
                        myQ.push(Grid(cur.p, cur.q + 1, d + 1));                    
                    }
                }
            }
        }
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

130. Surrounded Regions

Difficulty: Medium

Frequency: N/A

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int width = board.size();
        if (!width) return;
        int length = board[0].size();
        if (!length) return;
        for (int i = 0; i < width; i++) {
            if (board[i][0] == 'O') flip(board, i, 0);
            if (board[i][length - 1] == 'O') flip(board, i, length - 1);
        }
        for (int j = 1; j < length - 1; j++) {
            if (board[0][j] == 'O') flip(board, 0, j);
            if (board[width - 1][j] == 'O') flip(board, width - 1, j);
        }
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < length; j++) {
                if (board[i][j] == 'T') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
    void flip(vector<vector<char>>& board, int i, int j) {
        int width = board.size();
        int length = board[0].size();
        queue<pair<int, int>> myQ;
        myQ.push(make_pair(i, j));
        board[i][j] = 'T';
        while (!myQ.empty()) {
            pair<int, int> cur = myQ.front();
            myQ.pop();
            int p = cur.first, q = cur.second;
            if (p > 0 && board[p - 1][q] == 'O') {
                myQ.push(make_pair(p - 1, q));
                board[p - 1][q] = 'T';
            }
            if (p < width - 1 && board[p + 1][q] == 'O') {
                myQ.push(make_pair(p + 1, q));
                board[p + 1][q] = 'T';
            }
            if (q > 0 && board[p][q - 1] == 'O') {
                myQ.push(make_pair(p, q - 1));
                board[p][q - 1] = 'T';
            }
            if (q < length - 1 && board[p][q + 1] == 'O') {
                myQ.push(make_pair(p, q + 1));
                board[p][q + 1] = 'T';
            }
        }
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

199. Binary Tree Right Side View

Difficulty: Medium

Frequency: N/A

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> results;
        if (!root) return results;
        queue<TreeNode*> myQ;
        myQ.push(root);
        while (!myQ.empty()) {
            int q_size = myQ.size();
            while (q_size) {
                TreeNode *cur = myQ.front();
                if (q_size == 1) results.push_back(cur->val);
                myQ.pop();
                if (cur->left) myQ.push(cur->left);
                if (cur->right) myQ.push(cur->right);
                q_size--;
            }
        }
        return results;
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn: