Tag: DFS

210. Course Schedule II

fightingminionLeave a comment

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

fightingminionLeave a comment

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

fightingminion2 Comments

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:

339. (Locked)Nested List Weight Sum

fightingminionLeave a comment

Difficulty: Easy

Frequency: N/A

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]], return 10. (four 1’s at depth 2, one 2 at depth 1)

Example 2:
Given the list [1,[4,[6]]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27)

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
    int depthSum(vector<NestedInteger>& nestedList) {
        return DFS(nestedList, 1);
    }
    int DFS(vector<NestedInteger>& nestedList, int level) {
        int sum = 0;
        for (int i = 0; i < nestedList.size(); i++) {
            if (nestedList[i].isInterger()) {
                sum += nestedList[i].getInteger() * level;
            } else {
                sum += DFS(nestedList[i].getList(), level + 1);
            }
        }
        return sum;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

 

Things to learn:

282. Expression Add Operators

fightingminionLeave a comment

Difficulty: Hard

Frequency: N/A

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []
My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> results;
        if (num.empty()) return results;
        for (int i = 1; i <= num.size(); i++) {
            string s = num.substr(0, i);
            long cur = stol(s);
            if (to_string(cur).size() != s.size()) continue;
            dfs(results, num, target, s, i, cur, cur, '#');
        }
        return results;
    }
    void dfs(std::vector<string>& results, const string& num, const int target, string cur, int pos, const long cv, const long pv, const char op) {
        if (pos == num.size() && cv == target) results.push_back(cur);
        else {
            for (int i = pos + 1; i <= num.size(); i++) {
                string s = num.substr(pos, i - pos);
                long now = stol(s);
                if (to_string(now).size() != s.size()) continue;
                dfs(results, num, target, cur + "+" + s, i, cv + now, now, '+');
                dfs(results, num, target, cur + "-" + s, i, cv - now, now, '-');
                dfs(results, num, target, cur + "*" + s, i, (op == '-') ? cv + pv - pv * now : ((op == '+') ? cv - pv + pv * now : pv * now), pv * now, op);
            }
        }
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

200. Number of Islands

fightingminionLeave a comment

Difficulty: Medium

Frequency: N/A

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

 

My solution:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) return 0;
        int result = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    result++;
                    DFS(grid, i, j);
                }
            }
        }
        return result;
    }
    void DFS(vector<vector<char>>& grid, int i, int j) {
        grid[i][j] = '0';
        if (i > 0 && grid[i - 1][j] == '1') DFS(grid, i - 1, j);
        if (i < grid.size() - 1 && grid[i + 1][j] == '1') DFS(grid, i + 1, j);
        if (j > 0 && grid[i][j - 1] == '1') DFS(grid, i, j - 1);
        if (j < grid[0].size() - 1 && grid[i][j + 1] == '1') DFS(grid, i, j+ 1);
    }
};
Things to learn:

124. Binary Tree Maximum Path Sum

fightingminion1 Comment

Difficulty: Hard

Frequency: N/A

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

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:
    int maxPathSum(TreeNode* root) {
        int maxVal = INT_MIN;
        getMaxSum(root, maxVal);
        return maxVal;
    }
    int getMaxSum(TreeNode* node, int& maxVal) {
        if (!node) return 0;
        int l = getMaxSum(node->left, maxVal);
        int r = getMaxSum(node->right, maxVal);
        if (l < 0) l = 0;
        if (r < 0) r = 0;
        if (l + r + node->val > maxVal) maxVal = l + r + node->val;
        return node->val += max(l, r);
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

099. Recover Binary Search Tree

fightingminion1 Comment

Difficulty: Hard

Frequency: N/A

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

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 {
private:
    TreeNode *first = NULL, *second = NULL, *pre = new TreeNode(INT_MIN);
public:
    void recoverTree(TreeNode* root) {
        tranverseTree(root);
        int tmp = first->val;
        first->val = second->val;
        second->val = tmp;
    }
    void tranverseTree(TreeNode* node) {
        if (!node) return;
        tranverseTree(node->left);
        if (!first && node->val < pre->val) first = pre;
        if (first && node->val < pre->val) second = node;
        pre = node;
        tranverseTree(node->right);
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

117. Populating Next Right Pointers in Each Node II

fightingminion2 Comments

Difficulty: Hard

Frequency: N/A

Follow up for problem “Populating Next Right Pointers in Each Node“.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

  • You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL
My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        root->next = NULL;
        TreeLinkNode *cur = root;
        while (cur) {
            TreeLinkNode *nn = cur;
            while (nn) {
                TreeLinkNode *ln = nn->left;
                TreeLinkNode *rn = nn->right;
                if (ln) {
                    if (rn) ln->next = rn;
                    else {
                        TreeLinkNode *tmp = nn;
                        while (tmp) {
                            if (!tmp->next) {
                                ln->next = NULL;
                                break;
                            } else if (tmp->next->left) {
                                ln->next = tmp->next->left;
                                break;
                            } else if (tmp->next->right) {
                                ln->next = tmp->next->right;
                                break;
                            }
                            tmp = tmp->next;
                        }
                    }
                }
                if (rn) {
                    TreeLinkNode *tmp = nn;
                    while (tmp) {
                        if (!tmp->next) {
                            rn->next = NULL;
                            break;
                        } else if (tmp->next->left) {
                            rn->next = tmp->next->left;
                            break;
                        } else if (tmp->next->right) {
                            rn->next = tmp->next->right;
                            break;
                        }
                        tmp = tmp->next;
                    }
                }
                nn = nn->next;
            }
            while (cur) {
                if (cur->left) {
                    cur = cur->left;
                    break;
                } else if (cur->right) {
                    cur = cur->right;
                    break;
                }
                cur = cur->next;
            }
        }
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

098. Validate Binary Search Tree

fightingminion2 Comments

Difficulty: Medium

Frequency: N/A

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.
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:
    bool isValidBST(TreeNode* root) {
        return checkBST(root, NULL, NULL);
    }
    bool checkBST(TreeNode* node, TreeNode* min, TreeNode* max) {
        if (!node) return true;
        if (min && node->val <= min->val || max && node->val >= max->val) return false;
        return checkBST(node->left, min, node) && checkBST(node->right, node, max);
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn: