Graph

27. 542. 01 Matrix

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        return bfs(mat);
    }

    private int[][] bfs(int[][] mat) {
        int r = mat.length, c = mat[0].length;
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (mat[i][j] == 0)
                    q.offer(new int[] {i, j});
                else
                    mat[i][j] = -1;
            }
        }
        int[] directions = new int[] {-1, 0, 1, 0, -1};
        while(q.size() > 0) {
            int[] curr = q.poll();
            int m = curr[0], n = curr[1];
            for (int k = 0; k < 4; k++) {
                int nm = m + directions[k], nn = n + directions[k+1];
                if (nm < 0 || nm == r || nn < 0 || nn == c || mat[nm][nn] != -1)
                    continue;
                mat[nm][nn] = mat[m][n] + 1;
                q.offer(new int[] {nm, nn});
            }
        }
        return mat;
    }

    private int[][] dp(int[][] mat) {
        int r = mat.length, c = mat[0].length, INF = r + c;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (mat[i][j] == 0) continue;
                int top = INF, left = INF;
                if (i - 1 >= 0) top = mat[i - 1][j];
                if (j - 1 >= 0) left = mat[i][j - 1];
                mat[i][j] = Math.min(top, left) + 1;
            }
        }
        for (int i = r - 1; i >= 0; i--) {
            for (int j = c - 1; j >= 0; j--) {
                if (mat[i][j] == 0) continue;
                int bottom = INF, right = INF;
                if (i + 1 < r) bottom = mat[i + 1][j];
                if (j + 1 < c) right = mat[i][j + 1];
                mat[i][j] = Math.min(mat[i][j], Math.min(bottom, right) + 1);
            }
        }
        return mat;
    }
}

28. 133. Clone Graph

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) 
            return null;
        if (node.neighbors.size() == 0) 
            return new Node(node.val);
        return dfs(node, new HashMap<>());
    }

    private Node dfs(Node cur, Map<Node, Node> map) {
        Node clone = new Node(cur.val);
        map.put(cur, clone);
        for (Node n : cur.neighbors) {
            if (map.get(n) != null) {
                clone.neighbors.add(map.get(n));
            } else {
                clone.neighbors.add(dfs(n, map));
            }
        }
        return clone;
    }
}

29. 207. Course Schedule

LeetCode 207 & 210: Course Schedule I & II | Topological Sort | Kahn's algorithm

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;


class CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        final int[] courseDeps = new int[numCourses];
        for (final int[] pre : prerequisites) {
            courseDeps[pre[0]]++;
        }
        final Set<Integer> zeroDeps = new HashSet<>();
        for (int i = 0; i < numCourses; i++) {
            if (courseDeps[i] == 0) {
                zeroDeps.add(i);
            }
        }
        if (zeroDeps.isEmpty()) {
            return false;
        }
        while(!zeroDeps.isEmpty()) {
            final Iterator<Integer> it = zeroDeps.iterator();
            final int course = it.next();
            zeroDeps.remove(course);
            for (final int[] pre : prerequisites) {
                if (pre[1] == course) {
                    courseDeps[pre[0]]--;
                    if (courseDeps[pre[0]] == 0) {
                        zeroDeps.add(pre[0]);
                    }
                }
            }
        }
        for (final int i : courseDeps) {
            if (i > 0) {
                return false;
            }
        }
        return true;
    }

    @Test
    void givenInput1_whenCallCanFinish_thenItShouldReturnTrue() {
        final int numCourses = 2;
        final int[][] prerequisites = new int[][]{{1, 0}};
        assertTrue(canFinish(numCourses, prerequisites));
    }

    @Test
    void givenInput2_whenCallCanFinish_thenItShouldReturnFalse() {
        final int numCourses = 2;
        final int[][] prerequisites = new int[][]{{1, 0}, {0, 1}};
        assertFalse(canFinish(numCourses, prerequisites));
    }
}

30. 200. Number of Islands

1. union search / disjoint set / BFS

2. DFS / recursive

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty())
            return 0;

        int height = grid.size();
        int width = grid[0].size();
        int count = 0;
        queue<pair<int, int>> q;
        vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int r = 0; r < height; r++) {
            for (int c = 0; c < width; c++) {
                if (grid[r][c] == '1') {
                    count++;
                    q.push({r, c});

                    while(!q.empty()) {
                        pair<int, int> p = q.front();
                        q.pop();
                        if (grid[p.first][p.second] == '0') 
                            // it might have been updated to 0 by other neighbors
                            continue;

                        grid[p.first][p.second] = '0';

                        for (auto& dir : directions) {
                            int x = p.first + dir.first;
                            int y = p.second + dir.second;
                            if (x >= 0 
                                && x < height 
                                && y >= 0
                                && y < width 
                                && grid[x][y] == '1') {
                                q.push({x, y});
                            }
                        }
                    }   
                }
            }
        }
        return count;
    }
};

31. 994. Rotting Oranges

Note that in Graph BFS, compared with Tree BFS, we need to mark the visited node as visited to prevent infinite loop.

// https://leetcode.com/problems/rotting-oranges/
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n  = grid[0].size();

        vector<vector<int>> visited = grid;
        queue<pair<int, int>> q;

        int countFreshOrange = 0;
        for (int i = 0; i < m; i++) {
            for (int j =0; j < n; j++) {
                if (visited[i][j] == 2) {
                    q.push({i, j});
                }
                if (visited[i][j] == 1) {
                    countFreshOrange++;
                }
            }
        }
        //q.empty() means there is no rotten orange in the grid and countFreshOrange = 0 means we will rotten the freshoranges in 0 mins
        if (countFreshOrange == 0)
            return 0;
        if (q.empty())
            return -1;

        int minutes = -1;
        int directions[] = {-1, 0, 1, 0, -1};
        while(!q.empty()) {
            int size = q.size();
            while (size--) { // so that we can count the steps
                auto [i, j] = q.front();
                q.pop();
                for (int k = 0; k < 4; k++) {
                    int ni = i + directions[k];
                    int nj = j + directions[k+1];
                    if (ni >=0 && ni < m && nj >= 0 && nj < n && visited[ni][nj] == 1) {
                        visited[ni][nj] = 2;
                        countFreshOrange--;
                        q.push({ni, nj});
                    }
                }
            }
            minutes++;
        }

        if (countFreshOrange == 0)
            return minutes;
        return -1;
    }
};

32. Accounts Merge

TODO

33. 127. Word Ladder

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // to remove redundant and speed up the algo
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) {
            return 0;
        }
        
        int length = 1;
        queue<string> q;
        q.push(beginWord);
        wordSet.erase(beginWord);
        
        while(!q.empty()) {
            int size = q.size();
            // loop through each BFS level
            for (int s = 0; s < size; s++) {
                string w = q.front();
                q.pop();
                if (w == endWord) {
                    return length;
                }
                
                for (int i = 0; i < w.length(); i++) {
                    char original = w[i];
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        w[i] = ch;
                        if (wordSet.find(w) != wordSet.end()) {
                            wordSet.erase(w);
                            q.push(w);
                        }
                        w[i] = original;
                    }
                }
            }
            length++;
        }
        return 0;
    }
};

34. Word Search

TODO

35. 310. Minimum Height Trees

• MST

• disjoint set

• Kruskal’s Minimum Spanning Tree (MST) Algorithm

• Prim’s Algorithm for Minimum Spanning Tree (MST)

  • Prim's Algorithm Visually Explained (Minimum Spanning Tree)

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) {
            return {0};
        }

        vector<int> indegree(n, 0);
        unordered_map<int, list<int>> g;
        for (int i = 0; i < n; i++) {
            g[i] = list<int>();
        }
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            indegree[u]++;
            indegree[v]++;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 1) {
                q.push(i);
            }
        }

        int remaining = n;
        while (remaining > 2) {
            int s = q.size();
            remaining -= s;
            for (int i = 0; i < s; i++) {
                int n = q.front();
                q.pop();
                cout << g.size() << endl;
                for (int adj : g[n]) {
                    if (--indegree[adj] == 1) {
                        q.push(adj);
                    }
                }
            }
        }
        
        vector<int> result;
        while(!q.empty()) {
            result.push_back(q.front());
            q.pop();
        }
        return result;
    }
};

787. Cheapest Flights Within K Stops

Bellman-Ford Algorithm

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        int results[n];
        std::fill(results, results + n, INT_MAX);
        results[src] = 0;
        for (int i = 0; i <= k; i++) {
            int resultsCopy[n];
            copy(results, results + n, resultsCopy);

            for (const auto& flight : flights) {
                int s = flight[0];
                int d = flight[1];
                int w = flight[2];
                if (results[s] == INT_MAX) {
                    continue;
                }
                // note here we compare with the resultsCopy because it 
                // could possibly be updated during the inner loop
                if (results[s] + w < resultsCopy[d]) { 
                    resultsCopy[d] = results[s] + w;
                }
            }
            copy(resultsCopy, resultsCopy + n, results);
        }
        if (results[dst] == INT_MAX) {
            return -1;
        }
        return results[dst];
    }
};

743. Network Delay Time

Dijkstra's algorithm

class Solution {
private:
    class Vertex {
    public:
        Vertex(int t, int n): time(t), node(n) {}

        bool operator<(const Vertex& other) const {
            return time > other.time; 
        }
    private:
        int time; 
        int node;   
        friend class Solution; 
    };      
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        unordered_map<int, vector<pair<int, int>>> v2e;
        for (const auto& time : times) {
            int src = time[0];
            int dst = time[1];
            int t = time[2];
            if (v2e.find(src) != v2e.end()) {
                v2e[src].push_back({dst, t});
            } else {
                v2e[src] = vector<pair<int, int>>();
                v2e[src].push_back({dst, t});
            }
        }

        int rst = 0;
        std::set<int> visited;
        std::priority_queue<Vertex> vq;
        vq.push(Vertex(0, k));
        while (!vq.empty()) {
            Vertex v = vq.top();
            vq.pop();
            if (visited.find(v.node) != visited.end()) {
                continue;
            }
            visited.insert(v.node);
            rst = max(rst, v.time);
            vector<pair<int, int>> edges = v2e[v.node];
            for (const auto& e : edges) {
                if (visited.find(e.first) == visited.end()) {
                    vq.push(Vertex(e.second + v.time, e.first));
                }
            }   
        }
        if (visited.size() == n) {
            return rst;
        }
        return -1;
    }  
};