Skip to content
SparkTime, home
Menu
Theme
DSA From Zero to Job-Ready
Lessons
1 · Foundations (Think Like a Programmer)
2 · Data Structures and Recursion
3 · Core Algorithms and Reusable Patterns
4 · Advanced Interview Topics
5 · From Practice to Job-Ready
Lesson 24 of 28

Lesson 24 · Advanced Interview Topics

Range Queries and Disjoint Set Union

What to do when prefix sums are not enough: Fenwick and segment trees for range queries with updates (optional depth), and disjoint set union with path compression and union by size for connectivity, cycles and Kruskal's algorithm (the part worth knowing).

22 min read
On this page

Key takeaways

  • Prefix sums answer range queries on static data. When values change, a Fenwick tree or a segment tree gives O(log n) queries and updates. These are advanced topics, and less common for fresher interviews.
  • A Fenwick tree stores partial sums in an array and walks with i & -i. A segment tree stores the answer for a range at each node and works for sum, minimum, maximum and more.
  • Disjoint set union (union-find) keeps track of groups. find returns a group's representative, and union merges two groups.
  • Path compression plus union by size make each operation nearly constant, O(alpha(n)). Without them, a chain can make find O(n).
  • DSU is the right tool for connectivity when edges arrive over time, for detecting a cycle in an undirected graph, and for Kruskal's minimum spanning tree.

Imagine you maintain a leaderboard of scores, and you need to answer "what is the total score of players ranked 10 through 500?" many times, while individual scores keep changing. Prefix sums answer the range question beautifully, but if a single score changes, the whole prefix array must be rebuilt: O(n) per update. That is too slow if updates are frequent.

This article covers two families of tools that sit one step beyond the basics. The first handles range queries with updates (Fenwick trees and segment trees). The second, disjoint set union, tracks which items belong to the same group as groups merge over time.

How much of this do you need?

#

Be honest with yourself about priorities. Here is a rough guide for fresher and early-career interviews. Companies differ, so check your target roles.

Topic

Priority

Why

Prefix sums for static range queries

Essential

Covered earlier. Common.

Disjoint set union (union-find)

Worth knowing well

Short code, appears in graph and "groups" problems, and it is a classic follow-up to DFS for components

Kruskal's minimum spanning tree

Good to know

Uses DSU. Appears in graph rounds

Fenwick tree (BIT)

Optional

Short code, and a neat idea, but rarely required

Segment tree

Optional, advanced

Powerful, longer code. More common in contests and some product-company rounds

Lazy propagation, advanced variants

Beyond this course

Specialised

If time is short, read the DSU section carefully and skim the Fenwick and segment tree parts to understand what they offer.

What you will learn

#
  • When prefix sums stop being enough, and the options that replace them.
  • How a Fenwick tree and a segment tree work, at the level of ideas and code.
  • What disjoint set union is, and how path compression and union by size make it fast.
  • How to use DSU for connected components, cycle detection and Kruskal's algorithm.

Range queries with updates

#

The setting: an array of numbers. Two operations, repeated many times:

  • Query: the sum (or minimum, or maximum) of a range [left, right].
  • Update: change one element.

Approach

Query

Update

Notes

Plain loop

O(n)

O(1)

Fine for few queries

Prefix sums

O(1)

O(n), must rebuild

Best when nothing changes

Fenwick tree

O(log n)

O(log n)

Sums (and anything invertible). Short code

Segment tree

O(log n)

O(log n)

Sum, min, max, gcd and more

The trade is clear: both trees give up the instant O(1) queries of prefix sums, to get fast updates too.

Fenwick tree (binary indexed tree), optional

#

A Fenwick tree stores partial sums in a plain array so that both a prefix sum and a point update touch only about log n entries.

The trick is in which range each slot covers. With 1-based positions, slot i stores the sum of the elements in the range (i - lowbit(i), i], where lowbit(i) = i & -i is the lowest set bit of i (the trick from the bit article). For example, the slots for n = 8:

Slot i

Binary

lowbit

Covers positions

1

001

1

1

2

010

2

1 to 2

3

011

1

3

4

100

4

1 to 4

5

101

1

5

6

110

2

5 to 6

7

111

1

7

8

1000

8

1 to 8

Prefix sum of the first i elements. Add tree[i], then remove the lowest set bit (i -= i & -i) and repeat until i is 0. For i = 7 (111): add tree[7] (position 7), then i = 6: add tree[6] (positions 5 and 6), then i = 4: add tree[4] (positions 1 to 4). Total: positions 1 to 7. Each step removes one set bit, so there are at most log n steps.

Point update at position i. Add the change to tree[i], then move to the next slot that covers i (i += i & -i) and repeat while i <= n. For position 5: update slots 5, 6 and 8, which are exactly the slots whose ranges contain position 5.

A range sum is a difference of two prefix sums: sum(left..right) = prefix(right) - prefix(left - 1).

Our class uses a friendly 0-based public interface and shifts to 1-based inside.

Java
// File: Main.javaimport java.util.Random;public class Main {    static class FenwickTree {        private final int n;        private final long[] tree;               // 1-based internally        FenwickTree(int[] values) {            n = values.length;            tree = new long[n + 1];            for (int i = 0; i < n; i++) {                add(i, values[i]);            }        }        // Adds delta to the element at position index (0-based).        void add(int index, long delta) {            for (int i = index + 1; i <= n; i += i & -i) {                tree[i] += delta;            }        }        // Sum of the elements at positions 0..index. A negative index gives 0.        long prefix(int index) {            long sum = 0;            for (int i = index + 1; i > 0; i -= i & -i) {                sum += tree[i];            }            return sum;        }        long range(int left, int right) {            return prefix(right) - prefix(left - 1);        }    }    public static void main(String[] args) {        int[] values = {3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3};        FenwickTree fenwick = new FenwickTree(values);        System.out.println(fenwick.range(0, 4) + " " + fenwick.range(2, 5) + " " + fenwick.range(10, 10) + " " + fenwick.prefix(-1));        fenwick.add(3, 10);                       // the element at position 3 grows by 10        System.out.println(fenwick.range(0, 4) + " " + fenwick.range(2, 5));        // Compare with a plain array on 2000 random operations.        Random random = new Random(7);        int[] plain = new int[50];        FenwickTree check = new FenwickTree(plain);        boolean same = true;        for (int step = 0; step < 2000; step++) {            if (random.nextBoolean()) {                int index = random.nextInt(50);                int delta = random.nextInt(21) - 10;                plain[index] += delta;                check.add(index, delta);            } else {                int a = random.nextInt(50);                int b = random.nextInt(50);                int left = Math.min(a, b);                int right = Math.max(a, b);                long expected = 0;                for (int i = left; i <= right; i++) {                    expected += plain[i];                }                same &= expected == check.range(left, right);            }        }        System.out.println("matches the brute force on 2000 random operations: " + same);    }}
Code
15 14 3 025 24matches the brute force on 2000 random operations: true

Complexity: each add and prefix does at most about log2(n) + 1 steps. Building by repeated add takes O(n log n), and there are linear-time builds too. Space is O(n). The code is remarkably short, which is the Fenwick tree's appeal. It handles sums (and counts, XORs, and other "invertible" combinations), but not minimum or maximum directly, because you cannot subtract those.

Segment tree, optional and advanced

#

A segment tree is a binary tree over the positions of the array. The root represents the whole range [0, n - 1]. Each node represents a range and stores the answer for that range (its sum, or minimum, or whatever). A node covering [lo, hi] has two children covering [lo, mid] and [mid + 1, hi]. A leaf covers one element.

Code
Array: [5, 3, 8, 1]           Sum tree:        [0..3] 17                                              /          \                                       [0..1] 8          [2..3] 9                                       /     \           /     \                                  [0] 5     [1] 3    [2] 8     [3] 1

Query a range. Descend from the root. If a node's range lies entirely inside the query, return its stored value. If it lies entirely outside, return the identity value (0 for sums, a huge number for minimum). Otherwise, recurse into both children and combine their answers. At each level, at most a constant number of nodes are partially overlapping, so a query touches O(log n) nodes.

Update one element. Walk down to the leaf, change it, and recompute each node on the way back up from its two children: O(log n).

The same code works for different questions if you pass in the combine function and its identity: addition and 0 for sums, Math::min and Long.MAX_VALUE for minimums. A common array layout stores the tree in an array where the children of node i are 2i and 2i + 1, with size about 4n.

Java
// File: Main.javaimport java.util.Random;import java.util.function.LongBinaryOperator;public class Main {    static class SegmentTree {        private final int n;        private final long[] tree;        private final LongBinaryOperator combine;        private final long identity;        SegmentTree(int[] values, LongBinaryOperator combine, long identity) {            this.n = values.length;            this.tree = new long[Math.max(1, 4 * n)];            this.combine = combine;            this.identity = identity;            if (n > 0) {                build(1, 0, n - 1, values);            }        }        private void build(int node, int lo, int hi, int[] values) {            if (lo == hi) {                tree[node] = values[lo];                return;            }            int mid = lo + (hi - lo) / 2;            build(2 * node, lo, mid, values);            build(2 * node + 1, mid + 1, hi, values);            tree[node] = combine.applyAsLong(tree[2 * node], tree[2 * node + 1]);        }        // Answer for positions left..right, both included.        long query(int left, int right) {            return query(1, 0, n - 1, left, right);        }        private long query(int node, int lo, int hi, int left, int right) {            if (right < lo || hi < left) {                return identity;                       // no overlap            }            if (left <= lo && hi <= right) {                return tree[node];                     // full overlap            }            int mid = lo + (hi - lo) / 2;              // partial overlap: ask both children            return combine.applyAsLong(query(2 * node, lo, mid, left, right), query(2 * node + 1, mid + 1, hi, left, right));        }        void update(int index, long value) {            update(1, 0, n - 1, index, value);        }        private void update(int node, int lo, int hi, int index, long value) {            if (lo == hi) {                tree[node] = value;                return;            }            int mid = lo + (hi - lo) / 2;            if (index <= mid) {                update(2 * node, lo, mid, index, value);            } else {                update(2 * node + 1, mid + 1, hi, index, value);            }            tree[node] = combine.applyAsLong(tree[2 * node], tree[2 * node + 1]);        }    }    public static void main(String[] args) {        int[] values = {5, 3, 8, 1, 9, 2, 7};        SegmentTree sums = new SegmentTree(values, Long::sum, 0);        SegmentTree mins = new SegmentTree(values, Math::min, Long.MAX_VALUE);        System.out.println(sums.query(1, 4) + " " + mins.query(2, 5) + " " + sums.query(0, 6) + " " + mins.query(0, 6));        sums.update(3, 10);        mins.update(3, 10);        System.out.println(sums.query(1, 4) + " " + mins.query(2, 5));        Random random = new Random(11);        int[] plain = new int[40];        for (int i = 0; i < plain.length; i++) {            plain[i] = random.nextInt(100);        }        SegmentTree sumTree = new SegmentTree(plain, Long::sum, 0);        SegmentTree minTree = new SegmentTree(plain, Math::min, Long.MAX_VALUE);        boolean same = true;        for (int step = 0; step < 2000; step++) {            if (random.nextBoolean()) {                int index = random.nextInt(40);                int value = random.nextInt(100);                plain[index] = value;                sumTree.update(index, value);                minTree.update(index, value);            } else {                int a = random.nextInt(40);                int b = random.nextInt(40);                int left = Math.min(a, b);                int right = Math.max(a, b);                long expectedSum = 0;                long expectedMin = Long.MAX_VALUE;                for (int i = left; i <= right; i++) {                    expectedSum += plain[i];                    expectedMin = Math.min(expectedMin, plain[i]);                }                same &= expectedSum == sumTree.query(left, right) && expectedMin == minTree.query(left, right);            }        }        System.out.println("matches the brute force on 2000 random operations: " + same);    }}
Code
21 1 35 130 2matches the brute force on 2000 random operations: true

The first numbers: sum(1..4) = 3 + 8 + 1 + 9 = 21, min(2..5) = 1, the whole-array sum is 35, and its minimum is 1. After changing position 3 from 1 to 10, the sum over 1..4 becomes 30 and the minimum over 2..5 becomes 2 (from the 2 at position 5).

Complexity: build O(n), query and update O(log n), space O(n) (about 4n slots). Segment trees can also support range updates with a technique called lazy propagation, which is beyond this course.

Disjoint set union (union-find), worth knowing

#

Now a different problem: groups that merge. You have n items, each starting in a group of its own. Over time you are told "these two are in the same group", and you must be able to answer "are these two in the same group?" The structure for this is the disjoint set union (DSU), also called union-find. It supports two operations:

  • find(x): returns the representative (the "root") of the group containing x. Two items are in the same group exactly when their representatives are equal.
  • union(a, b): merges the groups of a and b.

The idea

#

Store the groups as a forest of trees. Each item has a parent. A root is its own parent. find(x) follows parents up to the root. union(a, b) finds both roots, and makes one root the parent of the other (if they are different).

A naive version can degrade. Joining items in a chain (union(0, 1), union(1, 2), ...) can produce a tree that is just a long path, so find takes O(n). Two small improvements fix this:

  1. Path compression. While walking up in find, make the nodes you pass point closer to (or directly at) the root. Next time, the same lookups are short. The code below uses path halving, a one-pass version: parent[x] = parent[parent[x]] as it climbs.
  2. Union by size. When merging, attach the smaller tree under the larger one's root. This keeps trees shallow, because a node's depth only increases when its tree is merged under a tree at least as big, which can happen at most log n times.

With both, the cost per operation is O(α(n)) amortised, where α is the inverse Ackermann function. It grows so slowly that it is at most 4 for any input you could fit in the universe, so in practice we say "almost constant".

What DSU is used for

#
  • Connected components with edges arriving over time. Each edge is a union. The number of components is n minus the number of successful unions.
  • Cycle detection in an undirected graph. For each edge (a, b), if find(a) == find(b), they are already connected, so this edge closes a cycle.
  • Kruskal's algorithm for a minimum spanning tree (below).
  • Grouping problems, such as merging accounts that share an email.

DSU cannot split groups. It only merges. If the problem needs deletions, you need a different approach.

Java
// File: Main.javaimport java.util.Arrays;public class Main {    static class DisjointSet {        private final int[] parent;        private final int[] size;        private int components;        DisjointSet(int n) {            parent = new int[n];            size = new int[n];            components = n;            for (int i = 0; i < n; i++) {                parent[i] = i;                         // each item starts alone                size[i] = 1;            }        }        int find(int x) {            while (parent[x] != x) {                parent[x] = parent[parent[x]];          // path halving: point at the grandparent                x = parent[x];            }            return x;        }        // Returns true if two different groups were merged, false if they were already together.        boolean union(int a, int b) {            int rootA = find(a);            int rootB = find(b);            if (rootA == rootB) {                return false;            }            if (size[rootA] < size[rootB]) {            // attach the smaller tree under the larger                int temp = rootA;                rootA = rootB;                rootB = temp;            }            parent[rootB] = rootA;            size[rootA] += size[rootB];            components--;            return true;        }        boolean connected(int a, int b) {            return find(a) == find(b);        }        int sizeOf(int x) {            return size[find(x)];        }        int components() {            return components;        }    }    // Kruskal: sort the edges by weight, and take each edge that joins two different groups.    static long minimumSpanningTreeWeight(int n, int[][] edges) {    // each edge: {u, v, weight}        int[][] sorted = edges.clone();        Arrays.sort(sorted, (a, b) -> Integer.compare(a[2], b[2]));        DisjointSet groups = new DisjointSet(n);        long total = 0;        int taken = 0;        for (int[] edge : sorted) {            if (groups.union(edge[0], edge[1])) {                total += edge[2];                taken++;            }        }        return taken == n - 1 ? total : -1;               // -1: the graph is not connected    }    static int depthOf(int[] parent, int x) {        int depth = 0;        while (parent[x] != x) {            x = parent[x];            depth++;        }        return depth;    }    public static void main(String[] args) {        DisjointSet groups = new DisjointSet(6);        groups.union(0, 1);        groups.union(1, 2);        groups.union(3, 4);        System.out.println(groups.components() + " " + groups.connected(0, 2) + " " + groups.connected(2, 3) + " " + groups.sizeOf(0) + " " + groups.sizeOf(5));        DisjointSet cycle = new DisjointSet(3);        System.out.println(cycle.union(0, 1) + " " + cycle.union(1, 2) + " " + cycle.union(2, 0) + "  (false means this edge closes a cycle)");        int[][] edges = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};        System.out.println(minimumSpanningTreeWeight(4, edges) + " " + minimumSpanningTreeWeight(3, new int[][] {{0, 1, 1}}));        // Why union by size matters: join 0-1, 1-2, 2-3, ... in a chain.        int n = 10000;        int[] naiveParent = new int[n];        for (int i = 0; i < n; i++) {            naiveParent[i] = i;        }        for (int i = 0; i + 1 < n; i++) {            naiveParent[i] = i + 1;                       // naive union: always hang the old root under the new item        }        DisjointSet sized = new DisjointSet(n);        for (int i = 0; i + 1 < n; i++) {            sized.union(i, i + 1);        }        System.out.println("naive chain: item 0 is " + depthOf(naiveParent, 0) + " links below its root");        System.out.println("union by size: " + sized.components() + " group holding " + sized.sizeOf(0) + " items");    }}
Code
3 true false 3 1true true false  (false means this edge closes a cycle)19 -1naive chain: item 0 is 9999 links below its rootunion by size: 1 group holding 10000 items

The chain experiment shows the danger: always hanging the old root under the new item builds a path of 9,999 links, so find(0) would have to walk it all. With union by size, the tree stays shallow and the example ends with a single group of 10,000 items.

The cycle line shows the cycle test in action: the first two unions merge groups (true), but union(2, 0) finds that 0 and 2 are already together (through 1), so it returns false.

Dry run of Kruskal on the edges 0-1 (10), 0-2 (6), 0-3 (5), 1-3 (15), 2-3 (4). Sorted by weight: 2-3 (4), 0-3 (5), 0-2 (6), 0-1 (10), 1-3 (15).

Edge

Same group already?

Action

Total so far

2-3 (4)

no

take it, merge {2, 3}

4

0-3 (5)

no

take it, merge into {0, 2, 3}

9

0-2 (6)

yes (0 and 2 are connected)

skip: it would form a cycle

9

0-1 (10)

no

take it, merge into {0, 1, 2, 3}

19

1-3 (15)

yes

skip

19

The minimum spanning tree has weight 19 with 3 edges (n - 1). If fewer than n - 1 edges could be taken, the graph is disconnected and has no spanning tree, which the method reports as -1. Kruskal is O(E log E), dominated by the sort.

Complexity summary

#

Structure or task

Build

Query or find

Update or union

Space

Prefix sums (static)

O(n)

O(1)

O(n) rebuild

O(n)

Fenwick tree

O(n log n)

O(log n)

O(log n)

O(n)

Segment tree

O(n)

O(log n)

O(log n)

O(n)

DSU with compression and union by size

O(n)

O(α(n))

O(α(n))

O(n)

Kruskal's MST

O(E log E)

O(V + E)

Edge cases and common mistakes

#
  • Fenwick tree indexing. The tree is 1-based. Using index 0 makes i & -i equal to 0 and the loop never advances. Convert from 0-based input at the boundary.
  • Updating when you meant setting. A Fenwick add adds a delta. To set a value, add the difference between the new and the old value.
  • Overflow. Use long for sums.
  • Segment tree size. Allocate about 4n slots.
  • Inclusive versus exclusive ranges. Decide and be consistent: this article uses inclusive [left, right].
  • DSU union on non-roots. Always find both roots first. Setting parent[a] = b directly can detach nodes from their own groups (see the exercise).
  • Forgetting path compression or union by size. Correct, but a chain can make operations O(n).
  • A recursive find without compression on a long chain can overflow the stack. The iterative version avoids that.
  • Counting components. Start at n, and decrease only when a union actually merges two different groups.
  • Using DSU when edges are removed. DSU cannot undo a merge.
  • Using a heavy structure when a simple one works. If there are no updates, prefix sums are better. If the graph is static and you only need components once, a DFS is simpler.

Exercises

#

Exercise 1

Trace

#

For a Fenwick tree with n = 8, which slots are modified by add at 1-based position 5? Which slots are read by prefix of the first 6 elements?

Exercise 2: Mutable range sum

#

Implement a class with update(index, value) (set the element at a position to a new value) and sumRange(left, right), using a Fenwick tree. For the array [1, 3, 5], sumRange(0, 2) is 9. After update(1, 2), it is 8.

Exercise 3: Redundant connection

#

A graph that was a tree with nodes 1..n had one extra edge added. Given the edge list, return the edge that, if removed, leaves a tree. If several edges could be removed, return the one that appears last in the input. For [[1, 2], [1, 3], [2, 3]] the answer is [2, 3].

Exercise 4: Debug

#

This union method looks plausible but breaks connectivity. Find an input that shows the problem, and fix it.

Java
void union(int a, int b) {    parent[a] = b;}

Exercise 5: Interview-style, Kruskal's algorithm

#

Given n vertices and weighted undirected edges, return the total weight of a minimum spanning tree, or -1 if the graph is not connected. For n = 4 and edges (0,1,10), (0,2,6), (0,3,5), (1,3,15), (2,3,4) the answer is 19. Explain why the greedy edge choice is valid.

Show solutionHide solution

add at position 5. Start at i = 5 (101), then i += i & -i: 5 + 1 = 6, then 6 + 2 = 8, then 8 + 8 = 16 > 8, stop. The modified slots are 5, 6 and 8. These are exactly the slots whose ranges contain position 5: slot 5 covers position 5, slot 6 covers positions 5 and 6, slot 8 covers positions 1 to 8.

prefix of 6. Start at i = 6 (110): read tree[6] (positions 5 to 6). Then i -= i & -i: 6 - 2 = 4, read tree[4] (positions 1 to 4). Then 4 - 4 = 0, stop. The read slots are 6 and 4, and together they cover positions 1 to 6.

Java
// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    public static void main(String[] args) {        int n = 8;        List<Integer> modified = new ArrayList<>();        for (int i = 5; i <= n; i += i & -i) {            modified.add(i);        }        List<Integer> read = new ArrayList<>();        for (int i = 6; i > 0; i -= i & -i) {            read.add(i);        }        System.out.println("add at 5 modifies " + modified + ", prefix of 6 reads " + read);    }}
Code
add at 5 modifies [5, 6, 8], prefix of 6 reads [6, 4]

Exercise 2

Show solutionHide solution

Keep a copy of the current values in a plain array so we know the old value, and apply the difference to the Fenwick tree: add(index, newValue - oldValue). A range sum is then prefix(right) - prefix(left - 1). Both operations are O(log n).

Java
// File: Main.javapublic class Main {    static class NumArray {        private final int n;        private final long[] tree;        private final int[] values;        NumArray(int[] initial) {            n = initial.length;            tree = new long[n + 1];            values = initial.clone();            for (int i = 0; i < n; i++) {                add(i, initial[i]);            }        }        private void add(int index, long delta) {            for (int i = index + 1; i <= n; i += i & -i) {                tree[i] += delta;            }        }        private long prefix(int index) {            long sum = 0;            for (int i = index + 1; i > 0; i -= i & -i) {                sum += tree[i];            }            return sum;        }        void update(int index, int value) {            add(index, (long) value - values[index]);     // add only the change            values[index] = value;        }        long sumRange(int left, int right) {            return prefix(right) - prefix(left - 1);        }    }    public static void main(String[] args) {        NumArray array = new NumArray(new int[] {1, 3, 5});        System.out.println(array.sumRange(0, 2));        array.update(1, 2);        System.out.println(array.sumRange(0, 2) + " " + array.sumRange(1, 1) + " " + array.sumRange(2, 2));        array.update(0, 100);        array.update(0, 100);                              // setting the same value twice must not double count        System.out.println(array.sumRange(0, 0) + " " + array.sumRange(0, 2));    }}
Code
98 2 5100 107

Storing the old values is what makes update a set, so repeating the same update does not change the total twice.

Exercise 3

Show solutionHide solution

Go through the edges in order, using a DSU over the nodes. For each edge (a, b): if a and b are already in the same group, this edge closes a cycle. Because the input had exactly one extra edge, this is the redundant edge. Otherwise merge their groups. Since the graph is a tree plus one edge, there is exactly one cycle, so exactly one edge fails to merge, and we can return it directly. (It is the last edge of the cycle in input order, which matches "return the last one that could be removed".)

Time O(n α(n)), space O(n).

Java
// File: Main.javaimport java.util.Arrays;public class Main {    static int find(int[] parent, int x) {        while (parent[x] != x) {            parent[x] = parent[parent[x]];            x = parent[x];        }        return x;    }    static int[] findRedundantConnection(int[][] edges) {        int n = edges.length;                            // nodes are 1..n for a tree plus one extra edge        int[] parent = new int[n + 1];        int[] size = new int[n + 1];        for (int i = 0; i <= n; i++) {            parent[i] = i;            size[i] = 1;        }        for (int[] edge : edges) {            int a = find(parent, edge[0]);            int b = find(parent, edge[1]);            if (a == b) {                return edge;                             // already connected: this edge makes a cycle            }            if (size[a] < size[b]) {                int temp = a;                a = b;                b = temp;            }            parent[b] = a;            size[a] += size[b];        }        return new int[0];    }    public static void main(String[] args) {        System.out.println(Arrays.toString(findRedundantConnection(new int[][] {{1, 2}, {1, 3}, {2, 3}})));        System.out.println(Arrays.toString(findRedundantConnection(new int[][] {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}})));        System.out.println(Arrays.toString(findRedundantConnection(new int[][] {{1, 2}, {2, 1}})));    }}
Code
[2, 3][1, 4][2, 1]

In the second example, the edges 1-2, 2-3, 3-4 build a path, and 1-4 closes a cycle 1-2-3-4-1. The edge 1-5 is fine. The last test uses a repeated edge (1-2 twice), which is also a cycle of length 2, and DSU catches it, where the DFS "parent" trick would not.

Exercise 4

Show solutionHide solution

parent[a] = b assumes a and b are roots. If a is not a root (it is already below some other node), this overwrites its link and detaches it from the rest of its group.

Example: union(0, 1) sets parent[0] = 1, so 0 and 1 are together. Then union(0, 3) sets parent[0] = 3, which cuts 0 off from 1. Now find(0) is 3 and find(1) is 1, so connected(0, 1) is false, although they were merged.

The fix is to link roots: parent[find(a)] = find(b), after checking that the roots differ (and preferably by size).

Java
// File: Main.javapublic class Main {    static int find(int[] parent, int x) {        while (parent[x] != x) {            x = parent[x];        }        return x;    }    public static void main(String[] args) {        int[] buggy = {0, 1, 2, 3};        buggy[0] = 1;                                   // union(0, 1)        buggy[0] = 3;                                   // union(0, 3), done on a non-root        System.out.println("buggy: connected(0, 1) = " + (find(buggy, 0) == find(buggy, 1)));        int[] fixed = {0, 1, 2, 3};        fixed[find(fixed, 0)] = find(fixed, 1);         // union(0, 1)        int rootOfZero = find(fixed, 0);        int rootOfThree = find(fixed, 3);        if (rootOfZero != rootOfThree) {            fixed[rootOfZero] = rootOfThree;            // union(0, 3), done on roots        }        System.out.println("fixed: connected(0, 1) = " + (find(fixed, 0) == find(fixed, 1)) + ", connected(0, 3) = " + (find(fixed, 0) == find(fixed, 3)));    }}
Code
buggy: connected(0, 1) = falsefixed: connected(0, 1) = true, connected(0, 3) = true

Exercise 5

Show solutionHide solution

Sort the edges by weight. Go through them from lightest to heaviest. Take an edge if it connects two different groups (use DSU), otherwise skip it, since it would create a cycle. Stop when n - 1 edges are taken. If you run out of edges first, the graph is disconnected.

Why is the greedy choice valid? (the cut property). Take the lightest edge among all edges that connect two different groups. Suppose some minimum spanning tree does not contain it. Add the edge to that tree: this creates a cycle, and that cycle must cross between the two groups in at least one other edge, which is at least as heavy (it is not lighter, because our edge is the lightest crossing edge). Swap that heavier edge for ours: we still have a spanning tree, and its weight is not larger. So there is a minimum spanning tree that includes our edge. Repeating this at each step shows the greedy result is optimal. Sorting dominates the cost: O(E log E).

Java
// File: Main.javaimport java.util.Arrays;public class Main {    static int find(int[] parent, int x) {        while (parent[x] != x) {            parent[x] = parent[parent[x]];            x = parent[x];        }        return x;    }    static long kruskal(int n, int[][] edges) {        int[][] sorted = edges.clone();        Arrays.sort(sorted, (a, b) -> Integer.compare(a[2], b[2]));        int[] parent = new int[n];        int[] size = new int[n];        for (int i = 0; i < n; i++) {            parent[i] = i;            size[i] = 1;        }        long total = 0;        int taken = 0;        for (int[] edge : sorted) {            int a = find(parent, edge[0]);            int b = find(parent, edge[1]);            if (a == b) {                continue;                                  // would form a cycle            }            if (size[a] < size[b]) {                int temp = a;                a = b;                b = temp;            }            parent[b] = a;            size[a] += size[b];            total += edge[2];            taken++;        }        return taken == n - 1 ? total : -1;    }    public static void main(String[] args) {        int[][] edges = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};        System.out.println(kruskal(4, edges));        System.out.println(kruskal(3, new int[][] {{0, 1, 1}}));        System.out.println(kruskal(1, new int[][] {}));        System.out.println(kruskal(3, new int[][] {{0, 1, 2}, {1, 2, 2}, {0, 2, 2}}));    }}
Code
19-104

A single vertex needs no edges, so its minimum spanning tree has weight 0 (and taken == n - 1 == 0). For the triangle with equal weights, any two of the three edges form a minimum spanning tree, total 4.

Where to go next

#
  • Next: The Interview Problem-Solving Workflow starts the final module, which turns everything you have learned into interview performance.
  • Related: Graphs: Representations, BFS, and DFS solved component counting with a search. DSU solves the same problem incrementally, and the two are good to compare.
  • Practice habit: when a problem says "merge groups", "are these connected?" or "edges arrive one at a time", think DSU. When it says "range query with updates" and the constraints are large, think Fenwick or segment tree, and confirm that this level of depth is appropriate for your target interviews.

Keep reading

More in Technology →

  • Guide · Technology

    How to Learn Data Structures and Algorithms Without Burning Out

  • Guide · Career

    The OA Landscape: Platforms, Formats, Proctoring and Rules

  • Guide · Career

    A LinkedIn Profile That Gets Recruiter Messages

←Next lesson →