DSA Series: Graph (Blind 75, Java)

Overview

• Pattern cheat-sheet
• Primer: BFS, DFS, topological sort, union-find
• 1. Clone Graph (Medium · 133)
• 2. Course Schedule (Medium · 207)
• 3. Pacific Atlantic Water Flow (Medium · 417)
• 4. Number of Islands (Medium · 200)
• 5. Longest Consecutive Sequence (Medium · 128)
• 6. Alien Dictionary (Hard · 269, premium)
• 7. Graph Valid Tree (Medium · 261, premium)
• 8. Number of Connected Components in an Undirected Graph (Medium · 323, premium)

Part of the DSA Blind 75 series. Track your progress on the Interview Prep page.

Targets: Visa, Mastercard, NPCI, Amex, PayU. Java 11+. All code compiled and tested against the examples and edge cases.

Pattern cheat-sheet

Primer: BFS, DFS, topological sort, union-find

Representation. Adjacency list List<List<Integer>> (or Map<K, List<K>> for non-integer ids). Space O(V+E). Adjacency matrix is O(V^2) - only for dense graphs. For grids, the graph is implicit: neighbors are the 4 (or 8) cells around you.

Visited marking. Mark when you enqueue (BFS) or enter (DFS), not when you dequeue, otherwise nodes get queued many times.

BFS template (also shortest path in an unweighted graph)

Deque<Integer> q = new ArrayDeque<>();
boolean[] seen = new boolean[n];
q.add(src); seen[src] = true;
int dist = 0;
while (!q.isEmpty()) {
    for (int sz = q.size(); sz > 0; sz--) {      // one level at a time
        int u = q.poll();
        for (int v : adj.get(u)) if (!seen[v]) { seen[v] = true; q.add(v); }
    }
    dist++;
}

DFS template (recursive; use an explicit stack if depth may reach ~10^5 - Java stack overflows around 10^4 to 10^5 frames)

void dfs(int u, List<List<Integer>> adj, boolean[] seen) {
    seen[u] = true;
    for (int v : adj.get(u)) if (!seen[v]) dfs(v, adj, seen);
}

Grid directions: int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}}; and always bounds-check before reading.

Topological sort (directed graph; only valid if acyclic)

• Kahn's (BFS): compute indegree; queue all indegree 0; pop, append to order, decrement neighbors' indegree, enqueue those that hit 0. If order.size() < V there is a cycle. Gives the order for free and detects cycles.
• DFS 3-color: state 0 = unvisited, 1 = on current path, 2 = done. Meeting a node with state 1 means a back edge = cycle. Post-order reversed is a topological order.

Union-Find (Disjoint Set Union) - near O(1) amortized (inverse Ackermann) for find/union with path compression + union by rank.

static class DSU {
    int[] parent, rank; int components;
    DSU(int n) { parent = new int[n]; rank = new int[n]; components = n;
                 for (int i = 0; i < n; i++) parent[i] = i; }
    int find(int x) {                      // path halving (iterative, no stack risk)
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    boolean union(int a, int b) {          // false if already connected => this edge closes a cycle
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        components--;
        return true;
    }
}

Use DSU when edges arrive incrementally (streaming) or when you only need connectivity; use DFS/BFS when you need paths, order, or distances.

1. Clone Graph (Medium · 133)

Problem statement. Given a reference to a node in a connected undirected graph, return a deep copy. Each node has int val and List<Node> neighbors. Example: adjacency list [[2,4],[1,3],[2,4],[1,3]] -> a new graph with the same structure and no shared node objects. Constraints: 0 <= nodes <= 100, 1 <= val <= 100, unique values, no repeated edges, graph is connected.

How the interviewer asks / follow-ups.

• Phrased as "deep copy a object graph with cyclic references", "snapshot a service-dependency topology / a merchant-hierarchy tree with cross-links for a what-if simulation", or "clone an in-memory account-relationship graph before running a fraud-rule experiment".
• Follow-ups: do it iteratively (avoid stack overflow); what if the graph is disconnected (take a list of roots / loop over all nodes)? What if nodes are huge and cannot fit in memory? How does Java's clone()/serialization deep copy handle cycles? Thread-safety if the graph is being mutated?
• Evaluates: knowing you need an old->new map to break cycles, marking visited at creation time, handling null and self-loops.

Approach 1: Brute force. Copy nodes without tracking visited -> infinite recursion on cycles. A "brute" workaround: first traverse to collect all nodes, then create copies, then wire edges (two passes). That is already correct and O(V+E); it is essentially the same as the map approach.

Approach 2: Hash map + DFS or BFS (optimal). Key insight: the map original -> clone doubles as the visited set. Create a clone the first time you see a node, and whenever you process an edge cur -> nb, ensure nb has a clone and add clone(nb) to clone(cur).neighbors. Dry run on 1-2, 1-4, 2-3, 3-4: queue [1], clone1. Pop 1: neighbors 2 and 4 are new -> clone2, clone4, queue [2,4]; wire clone1 -> clone2, clone4. Pop 2: neighbor 1 exists (reuse clone1), 3 new -> clone3; wire. Pop 4: 1 and 3 both exist; wire. Pop 3: wire to existing 2 and 4. Done; every edge is wired once per direction.

Java code

static class Node { int val; List<Node> neighbors = new ArrayList<>(); Node(int v){val=v;} }

static Node cloneGraph(Node node) {
    if (node == null) return null;                    // empty graph
    Map<Node, Node> copy = new HashMap<>();           // original -> clone (also the visited set)
    Deque<Node> q = new ArrayDeque<>();
    copy.put(node, new Node(node.val));
    q.add(node);
    while (!q.isEmpty()) {
        Node cur = q.poll();
        for (Node nb : cur.neighbors) {
            if (!copy.containsKey(nb)) {              // first time we see nb: create + schedule
                copy.put(nb, new Node(nb.val));
                q.add(nb);
            }
            copy.get(cur).neighbors.add(copy.get(nb)); // wire the edge (handles self-loops too)
        }
    }
    return copy.get(node);
}

(Recursive DFS variant: if (map.containsKey(n)) return map.get(n); Node c = new Node(n.val); map.put(n, c); for (Node nb : n.neighbors) c.neighbors.add(dfs(nb)); return c; - put into the map before recursing.)

Complexity

• Brute/two-pass and map approach: Time O(V+E) - every node and edge handled once. Space O(V) for the map + queue/recursion (output itself is O(V+E)).

Edge cases / pitfalls. Null input; single node; self-loop (node.neighbors contains itself); register the clone in the map before exploring neighbors or you recurse forever; do not use val as the key unless uniqueness is guaranteed (use node identity); disconnected graphs need an outer loop; deep recursion on long chains.

Pattern & related. Traversal + old->new map. Related: Copy List with Random Pointer (138), Clone N-ary Tree, Serialize/Deserialize Binary Tree (297), Course Schedule.

2. Course Schedule (Medium · 207)

Problem statement. There are numCourses labeled 0..n-1 and prerequisites[i] = [a, b] meaning you must take b before a. Return true if you can finish all courses. Example: n=2, [[1,0]] -> true. n=2, [[1,0],[0,1]] -> false. Constraints: 1 <= n <= 2000, 0 <= prerequisites.length <= 5000, all pairs unique.

How the interviewer asks / follow-ups.

• "Detect circular dependency among microservices / batch jobs / DB migrations / settlement pipeline stages", "can this DAG of payment-reconciliation jobs ever be scheduled?", "check a rule engine for cyclic rule references".
• Follow-ups: return one valid order (Course Schedule II, 210); return all orders (backtracking); print the actual cycle; run jobs in parallel - minimum number of rounds (level-by-level Kahn = longest path); weighted durations -> critical path; incremental edge insertions (dynamic cycle detection).
• Evaluates: modeling as a directed graph, direction of edges, cycle detection in directed graph (not the undirected parent trick), Kahn vs 3-color DFS.

Approach 1: Brute force. For every node, run a DFS and check if it can reach itself. Time O(V*(V+E)), space O(V). Correct but wasteful.

Approach 2: DFS with 3 colors. Key insight: in a directed graph, a cycle exists iff DFS finds a back edge to a node currently on the recursion path. Mark 0 = unvisited, 1 = in progress, 2 = finished (known safe, never revisit). Time O(V+E). Recursion depth up to V=2000 is fine here.

Approach 3: Kahn's algorithm (BFS topological sort) - preferred. Key insight: a node with indegree 0 has no unmet prerequisites, so it can be taken now; removing it may free others. If we can remove all nodes, no cycle; leftover nodes are on or behind a cycle. Dry run n=4, [[1,0],[2,0],[3,1],[3,2]]: edges 0->1, 0->2, 1->3, 2->3. indegree = [0,1,1,2]. Queue [0]. Pop 0 -> indeg1=0, indeg2=0 -> queue [1,2]. Pop 1 -> indeg3=1. Pop 2 -> indeg3=0 -> queue [3]. Pop 3. Processed 4 == n -> true. Order 0,1,2,3.

Java code

// Returns a valid order, or empty array if a cycle exists (this is Course Schedule II).
static int[] findOrder(int n, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] p : prerequisites) {            // p = [course, prereq]; edge prereq -> course
        adj.get(p[1]).add(p[0]);
        indeg[p[0]]++;
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
    int[] order = new int[n];
    int idx = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        order[idx++] = u;
        for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
    }
    return idx == n ? order : new int[0];      // idx < n => cycle
}

static boolean canFinish(int n, int[][] prerequisites) {
    return findOrder(n, prerequisites).length == n;
}

// Alternative: DFS with 3 colors
static boolean canFinishDfs(int n, int[][] pre) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] p : pre) adj.get(p[1]).add(p[0]);
    int[] state = new int[n];                  // 0 unvisited, 1 on path, 2 done
    for (int i = 0; i < n; i++) if (hasCycle(i, adj, state)) return false;
    return true;
}
private static boolean hasCycle(int u, List<List<Integer>> adj, int[] state) {
    if (state[u] == 1) return true;            // back edge
    if (state[u] == 2) return false;           // already proven safe
    state[u] = 1;
    for (int v : adj.get(u)) if (hasCycle(v, adj, state)) return true;
    state[u] = 2;
    return false;
}

Note: when n=1 and no prerequisites, order = [0], length 1 == n. For n with no prerequisites the returned array is length n (so findOrder(...).length == n is a valid check; n >= 1 per constraints).

Complexity

• Brute force: Time O(V*(V+E)), Space O(V).
• DFS 3-color: Time O(V+E), Space O(V+E) for adjacency + O(V) recursion.
• Kahn: Time O(V+E) - each node dequeued once, each edge relaxed once. Space O(V+E).

Edge cases / pitfalls. Self-prerequisite [0,0] is a cycle (indegree never reaches 0); edge direction mix-up ([a,b] means b -> a); disconnected components (loop over all start nodes / seed queue with all indegree 0); duplicate edges inflate indegree consistently in Kahn, so they are fine as long as you add both adjacency and indegree; using the undirected "visited + parent" cycle check on a directed graph is wrong (diamond DAG would be flagged).

Pattern & related. Topological sort / directed cycle detection. Related: Course Schedule II (210), Alien Dictionary (269), Minimum Height Trees (310), Parallel Courses (1136), Find Eventual Safe States (802), Sequence Reconstruction (444).

3. Pacific Atlantic Water Flow (Medium · 417)

Problem statement. heights[m][n] is an island. The Pacific touches the top and left edges, the Atlantic touches the bottom and right edges. Water flows from a cell to a 4-neighbor with height <= its own. Return all cells from which water can reach both oceans. Example: the 5x5 grid [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] -> [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]. Constraints: 1 <= m, n <= 200, 0 <= height <= 10^5.

How the interviewer asks / follow-ups.

• Disguised as "which nodes in a network can reach both a primary and a backup data-center", "which accounts can propagate funds/flags to both a source and sink set", or generic "reachability to two target sets under a monotone constraint".
• Follow-ups: why not run a search from every cell (complexity)? Iterative vs recursive for 200x200? What if there are k oceans? What if flow is allowed only strictly downhill? 8-direction movement?
• Evaluates: recognizing the reverse search trick (multi-source BFS from the targets), intersection of two reachability sets.

Approach 1: Brute force. From every cell run a DFS/BFS following non-increasing heights and check whether it touches both borders. Time O((mn)^2) worst case, space O(mn). For 200x200 = 40,000 cells * 40,000 = 1.6 * 10^9 - too slow.

Approach 2: Reverse multi-source BFS (optimal). Key insight: reachability is easier from the ocean side. Start from all Pacific border cells and move to neighbors with height >= current (going uphill, the reverse of flow); everything visited can flow to the Pacific. Do the same for the Atlantic. The answer is the intersection. Dry run on the 5x5 example, cell (2,2)=5: Pacific BFS seeds row 0 and column 0; (0,2)=2 -> (1,2)=3 (3 >= 2) -> (2,2)=5 (5 >= 3), so (2,2) reaches the Pacific. Atlantic BFS seeds row 4 and column 4; (2,4)=1 -> (2,3)=3 -> (2,2)=5, so it also reaches the Atlantic. Hence (2,2) is in the answer. On a 1x1 grid the single cell is a seed for both oceans -> [[0,0]].

Java code

private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

static List<List<Integer>> pacificAtlantic(int[][] h) {
    List<List<Integer>> res = new ArrayList<>();
    if (h == null || h.length == 0 || h[0].length == 0) return res;
    int m = h.length, n = h[0].length;
    boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
    Deque<int[]> qp = new ArrayDeque<>(), qa = new ArrayDeque<>();
    for (int i = 0; i < m; i++) {                    // left = Pacific, right = Atlantic
        pac[i][0] = true;   qp.add(new int[]{i, 0});
        atl[i][n-1] = true; qa.add(new int[]{i, n-1});
    }
    for (int j = 0; j < n; j++) {                    // top = Pacific, bottom = Atlantic
        pac[0][j] = true;   qp.add(new int[]{0, j});
        atl[m-1][j] = true; qa.add(new int[]{m-1, j});
    }
    bfs(h, qp, pac);
    bfs(h, qa, atl);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (pac[i][j] && atl[i][j]) res.add(Arrays.asList(i, j));
    return res;
}

private static void bfs(int[][] h, Deque<int[]> q, boolean[][] seen) {
    int m = h.length, n = h[0].length;
    while (!q.isEmpty()) {
        int[] c = q.poll();
        for (int[] d : DIRS) {
            int r = c[0] + d[0], cc = c[1] + d[1];
            if (r < 0 || cc < 0 || r >= m || cc >= n || seen[r][cc]) continue;
            if (h[r][cc] < h[c[0]][c[1]]) continue;  // reversed flow: only go to >= height
            seen[r][cc] = true;
            q.add(new int[]{r, cc});
        }
    }
}

Complexity

• Brute force: Time O((mn)^2), Space O(mn).
• Reverse BFS: Time O(mn) - each cell is enqueued at most once per ocean, 4 neighbor checks each. Space O(mn) for the two boolean grids and queues.

Edge cases / pitfalls. 1xN or Nx1 grids (every cell touches both oceans' borders, so all cells qualify); comparison direction (reverse search uses >=, not <=); forgetting that corner cells (0,n-1) and (m-1,0) are seeds of both; equal heights are traversable; marking visited when enqueuing; recursion depth up to 40,000 if you use recursive DFS - prefer BFS or iterative.

Pattern & related. Multi-source BFS / reverse reachability. Related: Number of Islands (200), Surrounded Regions (130), Walls and Gates (286), Rotting Oranges (994), 01 Matrix (542), Longest Increasing Path in a Matrix (329).

4. Number of Islands (Medium · 200)

Problem statement. Given an m x n grid of '1' (land) and '0' (water), return the number of islands (4-directionally connected land). Example: [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]] -> 3. Constraints: 1 <= m, n <= 300.

How the interviewer asks / follow-ups.

• "Count clusters of connected high-risk transactions on a geo grid", "count disjoint regions in a heat-map of merchant outlets", "count connected groups in a 2D seat/server-rack map".
• Follow-ups: do not mutate the input (use a visited array); iterative to avoid stack overflow; diagonal connectivity (8 dirs); Number of Islands II (200-premium 305): land cells are added one at a time, report the count after each - union-find; grid too large for memory / streamed row by row; multi-threaded or distributed counting (partition the grid, merge border components with union-find); largest island area (695); distinct island shapes (694).
• Evaluates: clean grid traversal, bounds checks, complexity, and whether you see union-find for the dynamic variant.

Approach 1: Brute force. There is no meaningful naive version; a typical weak approach re-scans neighbors without a visited structure and double counts. A "slow" valid one: for each land cell, flood fill into a fresh visited set copy - O((mn)^2).

Approach 2: DFS/BFS flood fill (optimal). Key insight: scan cells; at each unvisited '1' you have found a new island - count it and flood-fill the whole island (sink it to '0' or mark visited) so it is never counted again. Dry run on ["11","01"]: (0,0) is '1' -> count=1, flood fill sinks (0,0), (0,1), (1,1). Remaining cells are '0' or sunk -> answer 1.

Approach 3: Union-find. Union adjacent land cells, answer = number of land cells minus successful unions. Same O(mn alpha) time; shines when cells are added dynamically (Islands II).

Java code

private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

static int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int m = grid.length, n = grid[0].length, count = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (grid[i][j] == '1') {
                count++;
                grid[i][j] = '0';                     // sink on enqueue (acts as visited)
                Deque<int[]> q = new ArrayDeque<>();
                q.add(new int[]{i, j});
                while (!q.isEmpty()) {
                    int[] c = q.poll();
                    for (int[] d : DIRS) {
                        int r = c[0] + d[0], cc = c[1] + d[1];
                        if (r >= 0 && cc >= 0 && r < m && cc < n && grid[r][cc] == '1') {
                            grid[r][cc] = '0';
                            q.add(new int[]{r, cc});
                        }
                    }
                }
            }
    return count;
}

(If the caller needs the grid intact, use a boolean[][] seen instead of sinking, or clone the grid first.)

Complexity

• Brute force: O((mn)^2) time.
• BFS/DFS: Time O(mn) - each cell is enqueued once and checked 4 times. Space O(min(m,n)) for a BFS queue frontier (O(mn) worst case for DFS recursion on a snake-like island).
• Union-find: Time O(mn * alpha(mn)), Space O(mn).

Edge cases / pitfalls. All water -> 0; all land -> 1; single cell; ragged/empty grid; marking visited on dequeue instead of enqueue causes duplicates and blow-up; recursive DFS on a 300x300 all-land grid recurses up to 90,000 deep -> StackOverflowError in Java; mutating the input (state it aloud); chars not ints ('1' vs 1).

Pattern & related. Connected components on an implicit grid graph. Related: Max Area of Island (695), Surrounded Regions (130), Number of Islands II (305), Pacific Atlantic (417), Flood Fill (733), Connected Components (323).

5. Longest Consecutive Sequence (Medium · 128)

Problem statement. Given an unsorted array of integers, return the length of the longest run of consecutive values (order in the array does not matter). Must run in O(n). Example: [100,4,200,1,3,2] -> 4 (1,2,3,4). [0,3,7,2,5,8,4,6,0,1] -> 9. Constraints: 0 <= n <= 10^5, -10^9 <= nums[i] <= 10^9.

How the interviewer asks / follow-ups.

• "Given a set of transaction IDs / invoice numbers / sequence numbers received out of order, find the longest gap-free run" (detect missing sequence numbers in a settlement file), or "longest streak of consecutive days with a transaction".
• Follow-ups: why is it O(n) when there is a nested while loop? Streaming input (maintain a map of run boundaries, or union-find)? Data does not fit in memory (external sort / range buckets)? Return the actual sequence? Allow one gap?
• Evaluates: HashSet mindset, the "only start at sequence heads" amortization argument, spotting the union-find/graph view (consecutive values as connected components).

Approach 1: Brute force. For each number, repeatedly search the array for x+1, x+2... Time O(n^3) worst (O(n^2) if you use a set for lookups per start). Space O(1).

Approach 2: Sort. Sort, then scan counting runs while skipping duplicates. Time O(n log n), space O(1)/O(n) depending on sort. Doesn't meet the O(n) requirement but is a good fallback.

Approach 3: HashSet with sequence heads (optimal). Key insight: only start counting from x if x-1 is not in the set - that means x is the head of a run. Then walk upward. Every element is walked over at most once (as part of exactly one run), so total work is O(n). Dry run [100,4,200,1,3,2]: set = {1,2,3,4,100,200}. 100: 99 absent -> head, 101 absent -> len 1. 4: 3 present -> skip. 200: head, len 1. 1: head -> 2,3,4 -> len 4. Others skipped. Answer 4.

Java code

static int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int x : nums) set.add(x);              // dedups for free
    int best = 0;
    for (int x : set) {                         // iterate the set, not the array (duplicates)
        if (set.contains(x - 1)) continue;      // x is not a sequence head
        int len = 1, cur = x;
        while (set.contains(cur + 1)) { cur++; len++; }
        best = Math.max(best, len);
    }
    return best;
}

Note: x - 1 / cur + 1 could overflow at Integer.MIN_VALUE / MAX_VALUE; with the stated constraints (|x| <= 10^9) it is safe. If the range were the full int range, use long.

Complexity

• Brute force: O(n^2) to O(n^3) time, O(1) space.
• Sort: O(n log n) time, O(1)-O(n) space.
• HashSet: Time O(n) expected - each element is visited once by the outer loop and at most once by an inner walk. Space O(n).

Edge cases / pitfalls. Empty array -> 0; duplicates (must not count twice - sort-based scan needs if (a[i]==a[i-1]) continue); negative numbers; all identical -> 1; the "nested loop = O(n^2)" objection - explain the head check; adversarial hash collisions are a theoretical concern only.

Pattern & related. HashSet lookup / implicit graph (x connected to x+1). Related: Binary Tree Longest Consecutive Sequence (298), Missing Number (268), First Missing Positive (41), Contains Duplicate (217), Union-Find formulation (Longest Consecutive via DSU).

6. Alien Dictionary (Hard · 269, premium)

Problem statement. Given a list of words sorted lexicographically according to an unknown alphabet's order, derive a valid order of the letters. Return any valid order, or "" if none exists (contradiction/invalid input). Example: ["wrt","wrf","er","ett","rftt"] -> "wertf". ["z","x","z"] -> "" (cycle). ["abc","ab"] -> "" (invalid: a longer word before its own prefix). Constraints: 1 <= words.length <= 100, 1 <= word length <= 100, lowercase letters.

How the interviewer asks / follow-ups.

• "Given sorted records and the sort is by a custom key you cannot see, infer the key order" - e.g. infer the processing priority of transaction types / card-BIN ranges from sorted logs, or infer the dependency order of schema migrations from pairwise "A before B" constraints.
• Follow-ups: multiple valid orders - how to get the lexicographically smallest (use a PriorityQueue instead of a queue)? Is the order unique (queue size is always 1)? Return all orders? Letters that never appear in constraints - are they included? Detect which words make it inconsistent?
• Evaluates: extracting edges only from the first differing character of adjacent words, the prefix trap, including all letters as nodes, cycle detection via Kahn.

Approach 1: Brute force. Try all permutations of the letters and check they sort the word list. Time O(L! * N * len) - hopeless beyond tiny alphabets.

Approach 2: Graph + topological sort (optimal). Key insight: comparing each adjacent pair of words yields at most one ordering fact (the first position where they differ: a[k] < b[k]). Comparing non-adjacent pairs adds nothing new (transitivity). Build a directed graph on letters, topologically sort; a cycle means contradiction. Dry run ["wrt","wrf","er","ett","rftt"]: wrt/wrf -> t<f; wrf/er -> w<e; er/ett -> r<t; ett/rftt -> e<r. Edges: t->f, w->e, r->t, e->r. Indegrees: w0, e1, r1, t1, f1. Kahn: w, e, r, t, f -> "wertf".

Java code

static String alienOrder(String[] words) {
    Map<Character, Set<Character>> adj = new HashMap<>();
    Map<Character, Integer> indeg = new HashMap<>();
    for (String w : words)                              // every letter is a node, even with no edges
        for (char c : w.toCharArray()) {
            adj.putIfAbsent(c, new HashSet<>());
            indeg.putIfAbsent(c, 0);
        }
    for (int i = 0; i + 1 < words.length; i++) {
        String a = words[i], b = words[i + 1];
        if (a.length() > b.length() && a.startsWith(b)) return "";   // "abc" before "ab" is invalid
        for (int k = 0; k < Math.min(a.length(), b.length()); k++) {
            char x = a.charAt(k), y = b.charAt(k);
            if (x != y) {
                if (adj.get(x).add(y)) indeg.merge(y, 1, Integer::sum); // add edge once only
                break;                                  // only first difference is informative
            }
        }
    }
    Deque<Character> q = new ArrayDeque<>();
    for (Map.Entry<Character, Integer> e : indeg.entrySet())
        if (e.getValue() == 0) q.add(e.getKey());
    StringBuilder sb = new StringBuilder();
    while (!q.isEmpty()) {
        char u = q.poll();
        sb.append(u);
        for (char v : adj.get(u))
            if (indeg.merge(v, -1, Integer::sum) == 0) q.add(v);
    }
    return sb.length() == indeg.size() ? sb.toString() : "";  // shorter => cycle
}

(For ties, the output order depends on HashMap iteration; any valid order is accepted by the problem. Use a TreeMap / PriorityQueue<Character> for deterministic smallest-first.)

Complexity

• Brute force: O(26! * total chars) conceptually.
• Graph + Kahn: Time O(C + U^2) where C = total characters across all words (building edges) and U = unique letters (<= 26), as edges are at most min(N-1, U^2). Effectively O(C). Space O(U + min(N, U^2)) = O(1) for a fixed alphabet.

Edge cases / pitfalls. Prefix case ("abc","ab" -> ""); duplicate edges inflating indegree (guard with Set.add result); letters that only appear but have no constraints must still be in the output; single word -> its distinct letters in any order; identical adjacent words (no edge); cycle -> ""; building edges from only first pair mismatch - do not keep scanning after the first difference.

Pattern & related. Derive a DAG from pairwise constraints + topological sort. Related: Course Schedule II (210), Sequence Reconstruction (444), Verifying an Alien Dictionary (953), Parallel Courses (1136).

7. Graph Valid Tree (Medium · 261, premium)

Problem statement. Given n nodes labeled 0..n-1 and a list of undirected edges, decide whether they form a valid tree (connected and acyclic). Example: n=5, [[0,1],[0,2],[0,3],[1,4]] -> true. n=5, [[0,1],[1,2],[2,3],[1,3],[1,4]] -> false (cycle 1-2-3). Constraints: 1 <= n <= 2000, 0 <= edges.length <= 5000, no self-loops or duplicate edges.

How the interviewer asks / follow-ups.

• "Validate that a merchant/organization hierarchy has no cycles and a single root", "verify a network topology config is a spanning tree", "validate that the approval-chain graph is a tree".
• Follow-ups: edges arrive as a stream - detect the first edge that creates a cycle (Redundant Connection, 684); find the redundant edge in a directed graph (685); what if the graph might have duplicates/self-loops; return the cycle itself.
• Evaluates: the characterization "tree = connected + exactly n-1 edges" and a fast negative check, union-find usage.

Approach 1: Brute force / DFS with parent. Build an adjacency list, DFS from node 0 while tracking the parent; if you meet a visited non-parent neighbor -> cycle; after DFS, verify all n nodes were visited. Time O(V+E), space O(V+E). This is already optimal in time, but more code.

Approach 2: Union-find with edge-count shortcut (clean). Key insight: a graph on n nodes is a tree iff it has exactly n-1 edges and is acyclic (then it is automatically connected). If edges.length != n-1 return false immediately. Then union each edge; if an edge joins two nodes already in the same set, it forms a cycle -> false. Dry run: n=4, [[0,1],[2,3]] has 2 edges != 3 -> false (disconnected). The cyclic example has 5 edges != 4 -> false. n=3, [[0,1],[1,2]]: 2 == 2 and both unions succeed -> true. n=3, [[0,1],[1,0]]: 2 == 2 but the second union fails (already connected) -> false.

Java code (uses the DSU class from the primer)

static boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;     // tree has exactly n-1 edges
    DSU d = new DSU(n);
    for (int[] e : edges)
        if (!d.union(e[0], e[1])) return false;  // already connected => cycle
    return true;                                 // n-1 edges + no cycle => connected
}

Complexity

• DFS with parent: Time O(V+E), Space O(V+E).
• Union-find: Time O(E * alpha(V)) ~ O(V) since E = V-1 after the check; Space O(V).

Edge cases / pitfalls. n=1 with no edges -> true; n=0 not allowed; the edge-count check removes the need for a separate connectivity pass - explain why; when using DFS remember the parent check for undirected edges (otherwise every edge looks like a cycle) and the final "visited count == n" check; duplicate edge [0,1],[1,0] counts as a cycle of length 2 (DFS with parent id check would miss it - use edge index or union-find).

Pattern & related. Union-find / tree characterization (E = V-1 and connected). Related: Number of Connected Components (323), Redundant Connection (684, 685), Minimum Height Trees (310), Course Schedule (directed analog).

8. Number of Connected Components in an Undirected Graph (Medium · 323, premium)

Problem statement. Given n nodes and a list of undirected edges, return the number of connected components. Example: n=5, [[0,1],[1,2],[3,4]] -> 2. n=5, [[0,1],[1,2],[2,3],[3,4]] -> 1. Constraints: 1 <= n <= 2000, 1 <= edges.length <= 5000, no repeated edges.

How the interviewer asks / follow-ups.

• "How many independent groups of linked accounts / devices / cards are there (fraud rings)?", "count isolated networks of services", "friend/merchant groups".
• Follow-ups: edges arrive in a stream and you must report the count after each edge (union-find shines); account merging by shared email/phone/device (721 pattern); distributed version with billions of edges (MapReduce / label propagation, or per-shard DSU then merge); also return the sizes of the largest component.
• Evaluates: choosing union-find vs DFS, counting components via decrement-on-successful-union, path compression + union by rank.

Approach 1: Brute force / DFS or BFS. Build the adjacency list; for each unvisited node, run a traversal and increment the count. Time O(V+E), space O(V+E). This is optimal asymptotically - "brute" here is just less convenient for streams.

Approach 2: Union-find (optimal for streaming). Key insight: start with n components; each union that merges two different sets reduces the count by one. Final count = n - (number of successful unions). Dry run n=5, [[0,1],[1,2],[3,4]]: count 5 -> union(0,1)=4 -> union(1,2)=3 -> union(3,4)=2. Answer 2.

Java code (DSU from the primer tracks components)

static int countComponents(int n, int[][] edges) {
    DSU d = new DSU(n);
    for (int[] e : edges) d.union(e[0], e[1]);   // union returns false for redundant edges; ignored
    return d.components;                         // starts at n, -1 per successful merge
}

DFS alternative:

static int countComponentsDfs(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
    boolean[] seen = new boolean[n];
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (seen[i]) continue;
        count++;
        Deque<Integer> st = new ArrayDeque<>();   // iterative DFS
        st.push(i); seen[i] = true;
        while (!st.isEmpty()) {
            int u = st.pop();
            for (int v : adj.get(u)) if (!seen[v]) { seen[v] = true; st.push(v); }
        }
    }
    return count;
}

Complexity

• DFS/BFS: Time O(V+E), Space O(V+E).
• Union-find: Time O((V+E) * alpha(V)) ~ O(V+E), Space O(V).

Edge cases / pitfalls. No edges -> n components (isolated nodes count); duplicate/redundant edges must not decrement the counter (only successful unions do); nodes that never appear in any edge still count; forgetting to compress paths -> O(V) per find in the worst case; recursive find can overflow the stack on a degenerate chain without union by rank (use iterative as above).

Pattern & related. Union-find / connected components. Related: Graph Valid Tree (261), Number of Islands (200), Accounts Merge (721), Redundant Connection (684), Number of Provinces (547), Most Stones Removed (947).