DFS — Advanced Patterns

# python
# LC 1905 - Count Sub Islands
# IDEA: flood each island of grid2 with an explicit stack; it counts if every cell is land in grid1
# time = O(m * n), space = O(m * n)
def countSubIslands(grid1, grid2):
    rows, cols = len(grid2), len(grid2[0])
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid2[r][c] != 1:
                continue
            is_sub = True
            grid2[r][c] = 0                    # sink on push: each cell enters the stack once
            stack = [(r, c)]
            while stack:
                y, x = stack.pop()
                if grid1[y][x] == 0:
                    is_sub = False             # keep flooding: the rest of the island must sink too
                for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    ny, nx = y + dy, x + dx
                    if 0 <= ny < rows and 0 <= nx < cols and grid2[ny][nx] == 1:
                        grid2[ny][nx] = 0
                        stack.append((ny, nx))
            if is_sub:
                count += 1
    return count

// java
// LC 1905 - Count Sub Islands
// IDEA: flood each island of grid2 with an explicit stack; it counts if every cell is land in grid1
// time = O(m * n), space = O(m * n)
public int countSubIslands(int[][] grid1, int[][] grid2) {
    int rows = grid2.length, cols = grid2[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid2[r][c] != 1) {
                continue;
            }
            boolean isSub = true;
            grid2[r][c] = 0;
            Deque<int[]> stack = new ArrayDeque<>();
            stack.push(new int[]{r, c});
            while (!stack.isEmpty()) {
                int[] cell = stack.pop();
                if (grid1[cell[0]][cell[1]] == 0) {
                    isSub = false;                 // keep flooding
                }
                for (int[] d : dirs) {
                    int ny = cell[0] + d[0], nx = cell[1] + d[1];
                    if (ny >= 0 && ny < rows && nx >= 0 && nx < cols && grid2[ny][nx] == 1) {
                        grid2[ny][nx] = 0;
                        stack.push(new int[]{ny, nx});
                    }
                }
            }
            if (isSub) {
                count++;
            }
        }
    }
    return count;
}

# python
# LC 1466 - Reorder Routes to Make All Paths Lead to the City Zero
# IDEA: undirected walk from 0; an edge crossed in its original direction must be reversed
# time = O(n), space = O(n)
def minReorder(n, connections):
    graph = [[] for _ in range(n)]
    for a, b in connections:
        graph[a].append((b, 1))      # a -> b as given: points away from 0 if walked from a
        graph[b].append((a, 0))      # the reverse direction costs nothing

    seen = [False] * n
    seen[0] = True
    stack = [0]
    reversals = 0
    while stack:
        city = stack.pop()
        for nxt, original in graph[city]:
            if not seen[nxt]:
                seen[nxt] = True
                reversals += original    # walked away from 0 along the original direction
                stack.append(nxt)
    return reversals

// java
// LC 1466 - Reorder Routes to Make All Paths Lead to the City Zero
// IDEA: undirected walk from 0; an edge crossed in its original direction must be reversed
// time = O(n), space = O(n)
public int minReorder(int n, int[][] connections) {
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] c : connections) {
        graph.get(c[0]).add(new int[]{c[1], 1});
        graph.get(c[1]).add(new int[]{c[0], 0});
    }
    boolean[] seen = new boolean[n];
    seen[0] = true;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    int reversals = 0;
    while (!stack.isEmpty()) {
        int city = stack.pop();
        for (int[] edge : graph.get(city)) {
            if (!seen[edge[0]]) {
                seen[edge[0]] = true;
                reversals += edge[1];
                stack.push(edge[0]);
            }
        }
    }
    return reversals;
}

pop  crosses           flag  reversals
0    0->1 (original)    1    1
0    0->4 (reverse)     0    1
4    4->5 (original)    1    2
1    1->3 (original)    1    3
3    3->2 (reverse)     0    3
answer 3

# python
# LC 2316 - Count Unreachable Pairs of Nodes in an Undirected Graph
# IDEA: component sizes by flood fill; each new component pairs with every node seen before it
# time = O(n + E), space = O(n + E)
def countPairs(n, edges):
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    seen = [False] * n
    pairs = 0
    seen_so_far = 0                 # nodes in the components already counted
    for start in range(n):
        if seen[start]:
            continue
        seen[start] = True
        stack = [start]
        size = 0
        while stack:
            node = stack.pop()
            size += 1
            for nxt in graph[node]:
                if not seen[nxt]:
                    seen[nxt] = True
                    stack.append(nxt)
        pairs += size * seen_so_far
        seen_so_far += size
    return pairs

// java
// LC 2316 - Count Unreachable Pairs of Nodes in an Undirected Graph
// IDEA: component sizes by flood fill; each new component pairs with every node seen before it
// time = O(n + E), space = O(n + E)
public long countPairs(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        graph.get(e[1]).add(e[0]);
    }
    boolean[] seen = new boolean[n];
    long pairs = 0, seenSoFar = 0;           // long: up to ~5 * 10^9 pairs
    for (int start = 0; start < n; start++) {
        if (seen[start]) {
            continue;
        }
        seen[start] = true;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        long size = 0;
        while (!stack.isEmpty()) {
            int node = stack.pop();
            size++;
            for (int nxt : graph.get(node)) {
                if (!seen[nxt]) {
                    seen[nxt] = true;
                    stack.push(nxt);
                }
            }
        }
        pairs += size * seenSoFar;
        seenSoFar += size;
    }
    return pairs;
}

# python
# LC 211 - Design Add and Search Words Data Structure
# IDEA: trie; a '.' in the query branches the DFS into every child, a letter follows one
# time = O(L) per addWord; search O(L) without '.', O(26^d * L) with d dots, space = O(total chars)
class WordDictionary:
    def __init__(self):
        self.root = {}

    def addWord(self, word):
        node = self.root
        for ch in word:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
        node['$'] = True                       # end-of-word marker

    def search(self, word):
        def dfs(node, i):
            if i == len(word):
                return '$' in node             # a word must END here
            ch = word[i]
            if ch == '.':
                for key, child in node.items():
                    if key != '$' and dfs(child, i + 1):
                        return True            # first match is enough
                return False
            if ch not in node:
                return False
            return dfs(node[ch], i + 1)

        return dfs(self.root, 0)

// java
// LC 211 - Design Add and Search Words Data Structure
// IDEA: trie; a '.' in the query branches the DFS into every child, a letter follows one
// time = O(L) per addWord; search O(L) without '.', O(26^d * L) with d dots, space = O(total chars)
class WordDictionary {
    private final WordDictionary[] children = new WordDictionary[26];
    private boolean isWord = false;

    public void addWord(String word) {
        WordDictionary node = this;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new WordDictionary();
            }
            node = node.children[c - 'a'];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        return dfs(word, 0, this);
    }

    private boolean dfs(String word, int i, WordDictionary node) {
        if (node == null) {
            return false;
        }
        if (i == word.length()) {
            return node.isWord;                       // must end a word, not just be a prefix
        }
        char c = word.charAt(i);
        if (c == '.') {
            for (WordDictionary child : node.children) {
                if (dfs(word, i + 1, child)) {
                    return true;
                }
            }
            return false;
        }
        return dfs(word, i + 1, node.children[c - 'a']);
    }
}

# python
# LC 676 - Implement Magic Dictionary
# IDEA: trie DFS carrying a mismatch budget of 1; it must be fully spent at the word's end
# time = O(26 * L^2) per search, space = O(total chars)
class MagicDictionary:
    def __init__(self):
        self.root = {}

    def buildDict(self, dictionary):
        for word in dictionary:
            node = self.root
            for ch in word:
                if ch not in node:
                    node[ch] = {}
                node = node[ch]
            node['$'] = True

    def search(self, searchWord):
        def dfs(node, i, budget):
            if i == len(searchWord):
                return budget == 0 and '$' in node     # exactly one change, and a whole word
            for ch, child in node.items():
                if ch == '$':
                    continue
                cost = 0 if ch == searchWord[i] else 1
                if cost <= budget and dfs(child, i + 1, budget - cost):
                    return True
            return False

        return dfs(self.root, 0, 1)

# python
# LC 1530 - Number of Good Leaf Nodes Pairs
# IDEA: post-order; each node returns leaf counts by depth below it and pairs left x right at the LCA
# time = O(N * distance^2), space = O(N + distance * height)
def countPairs(root, distance):
    pairs = [0]

    def leaves_by_depth(node):
        cnt = [0] * (distance + 1)        # cnt[d] = leaves exactly d edges below node
        if node is None:
            return cnt
        if node.left is None and node.right is None:
            cnt[0] = 1                    # a leaf is 0 edges from itself
            return cnt
        left = leaves_by_depth(node.left)
        right = leaves_by_depth(node.right)
        for d1 in range(distance + 1):    # join a left leaf and a right leaf through node
            for d2 in range(distance + 1):
                if d1 + d2 + 2 <= distance:
                    pairs[0] += left[d1] * right[d2]
        for d in range(distance):         # one edge farther for the parent; deeper leaves drop off
            cnt[d + 1] = left[d] + right[d]
        return cnt

    leaves_by_depth(root)
    return pairs[0]

// java
// LC 1530 - Number of Good Leaf Nodes Pairs
// IDEA: post-order; each node returns leaf counts by depth below it and pairs left x right at the LCA
// time = O(N * distance^2), space = O(N + distance * height)
class Solution {
    private int pairs = 0;

    public int countPairs(TreeNode root, int distance) {
        pairs = 0;                                        // a reused Solution must not carry counts over
        leavesByDepth(root, distance);
        return pairs;
    }

    // cnt[d] = number of leaves exactly d edges below node
    private int[] leavesByDepth(TreeNode node, int distance) {
        int[] cnt = new int[distance + 1];
        if (node == null) return cnt;
        if (node.left == null && node.right == null) {
            cnt[0] = 1;                                   // a leaf is 0 edges from itself
            return cnt;
        }
        int[] left = leavesByDepth(node.left, distance);
        int[] right = leavesByDepth(node.right, distance);
        for (int d1 = 0; d1 <= distance; d1++) {          // join a left leaf and a right leaf through node
            for (int d2 = 0; d2 <= distance; d2++) {
                if (d1 + d2 + 2 <= distance) pairs += left[d1] * right[d2];
            }
        }
        for (int d = 0; d < distance; d++) {              // one edge farther for the parent
            cnt[d + 1] = left[d] + right[d];
        }
        return cnt;
    }
}

# python
# LC 3965 - Finish Time of Tasks I
# IDEA: build children lists; compute nodes in reverse DFS pre-order so children finish first
# time = O(n), space = O(n)
def finishTime(n, edges, baseTime):
    children = [[] for _ in range(n)]
    for parent, child in edges:              # directed: parent -> child
        children[parent].append(child)

    order = []                               # DFS pre-order from the root
    stack = [0]
    while stack:
        node = stack.pop()
        order.append(node)
        for child in children[node]:
            stack.append(child)

    finish = [0] * n
    for node in reversed(order):             # every child appears after its parent in `order`
        if not children[node]:
            finish[node] = baseTime[node]    # leaf
            continue
        earliest = min(finish[c] for c in children[node])
        latest = max(finish[c] for c in children[node])
        own_duration = (latest - earliest) + baseTime[node]
        finish[node] = latest + own_duration
    return finish[0]

// java
// LC 3965 - Finish Time of Tasks I
// IDEA: build children lists; compute nodes in reverse DFS pre-order so children finish first
// time = O(n), space = O(n)
public long finishTime(int n, int[][] edges, int[] baseTime) {
    List<List<Integer>> children = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        children.add(new ArrayList<>());
    }
    for (int[] e : edges) {
        children.get(e[0]).add(e[1]);
    }
    int[] order = new int[n];
    int size = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    while (!stack.isEmpty()) {
        int node = stack.pop();
        order[size++] = node;
        for (int c : children.get(node)) {
            stack.push(c);
        }
    }
    long[] finish = new long[n];             // long: values compound with depth
    for (int i = n - 1; i >= 0; i--) {
        int node = order[i];
        if (children.get(node).isEmpty()) {
            finish[node] = baseTime[node];
            continue;
        }
        long earliest = Long.MAX_VALUE, latest = Long.MIN_VALUE;
        for (int c : children.get(node)) {
            earliest = Math.min(earliest, finish[c]);
            latest = Math.max(latest, finish[c]);
        }
        finish[node] = latest + (latest - earliest) + baseTime[node];
    }
    return finish[0];
}

# python
# LC 388 - Longest Absolute File Path
# IDEA: stack[d] = path length up to the open directory at depth d; popping == returning up the DFS
# time = O(N), space = O(D)   N = input length, D = deepest nesting
def lengthLongestPath(input):
    longest = 0
    stack = [0]                                # depth 0 has an empty prefix
    for line in input.split('\n'):
        name = line.lstrip('\t')
        depth = len(line) - len(name)          # leading tabs = depth
        while len(stack) > depth + 1:          # close the directories this line is not inside
            stack.pop()
        if '.' in name:                        # a file is a leaf: score it, never push it
            longest = max(longest, stack[depth] + len(name))
        else:                                  # a directory: its prefix plus the name plus '/'
            stack.append(stack[depth] + len(name) + 1)
    return longest

// java
// LC 388 - Longest Absolute File Path
// IDEA: stack[d] = path length up to the open directory at depth d; popping == returning up the DFS
// time = O(N), space = O(D)
public int lengthLongestPath(String input) {
    int longest = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    for (String line : input.split("\n")) {
        int depth = 0;
        while (depth < line.length() && line.charAt(depth) == '\t') {
            depth++;
        }
        String name = line.substring(depth);
        while (stack.size() > depth + 1) {
            stack.pop();
        }
        if (name.contains(".")) {
            longest = Math.max(longest, stack.peek() + name.length());
        } else {
            stack.push(stack.peek() + name.length() + 1);
        }
    }
    return longest;
}

# python
# LC 1233 - Remove Sub-Folders from the Filesystem
# IDEA: path trie; DFS collects the first stored folder on each branch and cuts below it
# time = O(total path chars), space = O(total path chars)
def removeSubfolders(folder):
    root = {}
    for path in folder:
        node = root
        for part in path.split('/')[1:]:       # [0] is the empty string before the first '/'
            if part not in node:
                node[part] = {}
            node = node[part]
        node['$'] = path                       # the full path ends here

    kept = []
    stack = [root]
    while stack:
        node = stack.pop()
        if '$' in node:
            kept.append(node['$'])
            continue                           # cut: anything deeper is a sub-folder
        for child in node.values():
            stack.append(child)
    return kept

# python
# LC 4015 - Weighted Sum of a Tree
# IDEA: memoized climb up parent[] (explicit stack, no recursion); height = max depth
# time = O(n), space = O(n)
def weightedSum(parent, nums):
    n = len(parent)
    depth = [0] * n                    # 0 = not computed yet; depths are 1-based
    for start in range(n):
        chain = []
        x = start
        while depth[x] == 0:           # climb until a computed node, or past the root
            if parent[x] == -1:
                depth[x] = 1
                break
            chain.append(x)
            x = parent[x]
        d = depth[x]
        while chain:                   # unwind: fill every node climbed through
            d += 1
            depth[chain.pop()] = d

    height = max(depth)
    total = 0
    for i in range(n):
        total += nums[i] * (height - depth[i] + 1)
    return total

// java
// LC 4015 - Weighted Sum of a Tree
// IDEA: memoized climb up parent[] with an explicit stack; height = max depth
// time = O(n), space = O(n)
class Solution {
    public long weightedSum(int[] parent, int[] nums) {
        int n = parent.length;
        int[] depth = new int[n];                         // 0 = not computed yet; depths are 1-based
        java.util.ArrayDeque<Integer> chain = new java.util.ArrayDeque<>();
        for (int start = 0; start < n; start++) {
            int x = start;
            while (depth[x] == 0) {                       // climb until a computed node, or past the root
                if (parent[x] == -1) {
                    depth[x] = 1;
                    break;
                }
                chain.push(x);
                x = parent[x];
            }
            int d = depth[x];
            while (!chain.isEmpty()) {                    // unwind: fill every node climbed through
                d++;
                depth[chain.pop()] = d;
            }
        }
        int height = 0;
        for (int dep : depth) height = Math.max(height, dep);
        long total = 0;
        for (int i = 0; i < n; i++) {
            total += (long) nums[i] * (height - depth[i] + 1);
        }
        return total;
    }
}

start  climb                 depths filled
0      root                  depth0 = 1
1      1 -> 0 (known)        depth1 = 2
2      2 -> 0                depth2 = 2
3      3 -> 0                depth3 = 2
4      4 -> 2 (known)        depth4 = 3
5      5 -> 2                depth5 = 3
height 3: 5*3 + 2*2 + 3*2 + 1*2 + 4*1 + 6*1 = 37