Graph

427. Construct Quad Tree

Recursion + tree / 2D graph

/**
 * Definition for _Node.
 * class _Node {
 *     val: boolean
 *     isLeaf: boolean
 *     topLeft: _Node | null
 * 	topRight: _Node | null
 * 	bottomLeft: _Node | null
 * 	bottomRight: _Node | null
 * 	constructor(val?: boolean, isLeaf?: boolean, topLeft?: _Node, topRight?: _Node, bottomLeft?: _Node, bottomRight?: _Node) {
 *         this.val = (val===undefined ? false : val)
 *         this.isLeaf = (isLeaf===undefined ? false : isLeaf)
 *         this.topLeft = (topLeft===undefined ? null : topLeft)
 *         this.topRight = (topRight===undefined ? null : topRight)
 *         this.bottomLeft = (bottomLeft===undefined ? null : bottomLeft)
 *         this.bottomRight = (bottomRight===undefined ? null : bottomRight)
 *   }
 * }
 */


function construct(grid: number[][]): _Node | null {
    const m = grid.length, n = grid[0].length;
    return constructTree(grid, 0, m - 1, 0, n - 1);
};

function constructTree(grid: number[][], tLeft: number, tRight: number, bLeft: number, bRight: number): _Node | null {
    if (tLeft > tRight || bLeft > bRight || tRight - tLeft !== bRight - bLeft) {
        return null;
    }
    if (tLeft === tRight && bLeft === bRight) {
        return new _Node(grid[tLeft][bLeft] === 1, true, null, null, null, null);
    }
    if (isLeaf(grid, tLeft, tRight, bLeft, bRight)) {
        return new _Node(grid[tLeft][bLeft] === 1, true, null, null, null, null);
    }
    const tMid = Math.floor((tLeft + tRight) / 2);
    const bMid = Math.floor((bLeft + bRight) / 2);
    return new _Node(grid[tLeft][bLeft] === 1, 
        false, 
        constructTree(grid, tLeft, tMid, bLeft, bMid), // topLeft
        constructTree(grid, tLeft, tMid, bMid + 1, bRight), // topRight
        constructTree(grid, tMid + 1, tRight, bLeft, bMid), // bottomLeft
        constructTree(grid, tMid + 1, tRight, bMid + 1, bRight)); // bottomRight
}

function isLeaf(grid: number[][], tLeft: number, tRight: number, bLeft: number, bRight: number) {
    const val = grid[tLeft][bLeft];
    for (let i = tLeft; i <= tRight; i++) {
        for (let j = bLeft; j <= bRight; j++) {
            if (grid[i][j] !== val) return false;
        }
    }
    return true;
}

1192. Critical Connections in a Network

Convert edge to graph map. DFS traverse from 0 node, assign new id every time. Use arrays ids[] and low[] to store the corresponding ids and the low index of the connect graph. If next node is unvisited, DFS to next node. Update low[curt] after the traverse by low[curt] = Math.min(low[curt], low[next]). Add to result if ids[curt] < low[next]

int[] ids;
int[] low;
int index = 0;
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    this.ids = new int[n];
    this.low = new int[n];
    Arrays.fill(ids, -1);
    Map<Integer, Set<Integer>> graph = buildGraph(connections);
    List<List<Integer>> res = new ArrayList<>();
    dfs(0, -1, graph, res);
    return res;
}

private void dfs(int curt, 
                 int prev, 
                 Map<Integer, Set<Integer>> graph, 
                 List<List<Integer>> res) {
    ids[curt] = low[curt] = index++;
    if (!graph.containsKey(curt)) return;
    for (int next : graph.get(curt)) {
        if (next == prev) continue;
        if (ids[next] == -1) {
            dfs(next, curt, graph, res);
            low[curt] = Math.min(low[curt], low[next]);
            if (ids[curt] < low[next]) {
                res.add(Arrays.asList(curt, next));
            }
        } else {
            low[curt] = Math.min(low[curt], low[next]);
        }
    }
}

private Map<Integer, Set<Integer>> buildGraph(List<List<Integer>> edges) {
    Map<Integer, Set<Integer>> map = new HashMap<>();
    for (List<Integer> e : edges) {
        map.putIfAbsent(e.get(0), new HashSet<>());
        map.putIfAbsent(e.get(1), new HashSet<>());
        map.get(e.get(0)).add(e.get(1));
        map.get(e.get(1)).add(e.get(0));
    }
    return map;
}

1102. Path With Maximum Minimum Value

Use maxHeap to store a new class (val, x, y). Every time it pops the largest node, and maintain a min from the val.

int[][] dirs = {{1,0}, {0,1}, {-1,0}, {0,-1}};
public int maximumMinimumPath(int[][] A) {
    int m = A.length, n = A[0].length;
    PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<>(){
        public int compare(int[] a, int[] b) {
            return b[0] - a[0];
        }
    });
    pq.offer(new int[]{A[0][0], 0, 0});
    A[0][0] = -1;
    int min = Integer.MAX_VALUE;
    while (!pq.isEmpty()) {
        int[] curt = pq.poll();
        min = Math.min(min, curt[0]);
        if (curt[1] == m - 1 && curt[2] == n - 1) break;
        for (int[] d : dirs) {
            int nx = curt[1] + d[0];
            int ny = curt[2] + d[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && A[nx][ny] != -1) {
                pq.offer(new int[]{A[nx][ny], nx, ny});
                A[nx][ny] = -1;
            }
        }
    }
    return min;
}

332. Reconstruct Itinerary

Use PQ instead of Set as we can get the next stops in lexicographical order. DFS to the end of next and use bottom-up to construct itinerary.

public List<String> findItinerary(List<List<String>> tickets) {
    Map<String, PriorityQueue<String>> map = new HashMap<>();
    for (List<String> l : tickets) {
        map.putIfAbsent(l.get(0), new PriorityQueue<>());
        map.get(l.get(0)).add(l.get(1));
    }
    List<String> list = new ArrayList<>();
    dfs("JFK", list, map);
    return list;
}

private void dfs(String curt, List<String> list, Map<String, PriorityQueue<String>> map) {
    PriorityQueue<String> pq = map.get(curt);
    while (pq != null && !pq.isEmpty()) {
        String next = pq.poll();
        dfs(next, list, map);
    }
    list.add(0, curt);
}

1376. Time Needed to Inform All Employees

Get the largest time spent on each level.

Java (BFS)

public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    for (int i = 0; i < manager.length; i++) {
        int u = manager[i], v = i;
        if (u == -1) {
            continue;
        }
        graph.putIfAbsent(u, new HashSet<>());
        graph.get(u).add(v);
    }
    int totalTime = 0;
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{headID, 0});
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int[] curt = q.poll();
            int emp = curt[0], time = curt[1];
            totalTime = Math.max(time, totalTime);
            if (graph.get(emp) == null) continue;
            for (int next : graph.get(emp)) {
                q.offer(new int[]{next, time + informTime[emp]});
            }
        }
    }
    return totalTime;
}

Java (DFS)

Java (DFS + construct graph)