Start learning free

LESSON 496 OF 573 · GRAPHS

Redundant Connection in TypeScript: Union-Find in Nearly O(n)

Practice O(n · α(n)) Read the full explanation

A tree is an undirected graph that is connected (you can get from any node to any other by following edges) and has no cycle. Put another way, there is exactly one path between any two nodes.

You start with a tree of n nodes, numbered from 1 to n, and one extra edge is added to it. The extra edge joins two different nodes that were not joined by an edge before. The graph you get is given as an array edges of length n, where edges[i] = [ai, bi] means that there is an edge between nodes ai and bi.

Return an edge that can be removed so that the other n - 1 edges form a tree of all n nodes. If several edges work, return the one that comes last in edges.

 

Example 1:

Input: edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Explanation: The three edges form the cycle 1 - 2 - 3 - 1:
      1
     / \
    2 - 3
Removing any one of them leaves a tree. [2, 3] is the one that comes last.

Example 2:

Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]
Explanation: The cycle is 1 - 2 - 3 - 4 - 1:
    5 - 1 - 2
        |   |
        4 - 3
[1, 5] comes after [1, 4] in the input, but removing it would cut node 5 off from the others.
Of the four edges on the cycle, [1, 4] comes last.

Example 3:

Input: edges = [[1, 2], [3, 4], [2, 3], [4, 5], [1, 5]]
Output: [1, 5]
Explanation: When [2, 3] comes, nodes 2 and 3 have both been seen already, but in two
separate groups, {1, 2} and {3, 4}: the edge joins them. All five edges form the cycle
1 - 2 - 3 - 4 - 5 - 1, and [1, 5] comes last.

 

Constraints:

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ai < bi <= n
  • There are no repeated edges.
  • The graph is connected.

Note:

Your algorithm should run in O(n·α(n)) time, nearly O(n), and use O(n) extra space.

Trying each edge from the last one back, removing it and checking with a DFS whether the rest is still connected, costs O(n2). The tutorial adds the edges one by one, in the order they are given, with union-find, as in Graph Valid Tree: an edge whose two nodes are already in the same group closes a cycle. The graph has exactly one cycle, and removing any of its edges leaves a tree, while removing an edge that is not on it cuts the tree in two. The cycle closes when the last of its edges comes, because all its other edges came before, so the first edge that closes a cycle is the answer. With path halving and union by size, each step costs O(α(n)) amortized, where α is the inverse Ackermann function, below 5 for any n a computer can hold.

STEP 1 OF 16
    Ctrl + Enter to check

    TYPESCRIPT · GRAPHS

    Redundant Connection in TypeScript, explained

    Problem overview

    A tree is a connected graph with no cycle. The input of findRedundantConnection is edges, the edges of a tree of n nodes numbered 1 to n with one extra edge added, so the array holds exactly n edges. Each edge is a pair [a, b] with a < b, there are no repeated edges, and the graph is connected. The method returns an edge that can be removed so the remaining n - 1 edges form a tree again. If several edges work, it returns the one that comes last in edges.

    For [[1, 2], [1, 3], [2, 3]] the three edges form the cycle 1 - 2 - 3 - 1. Removing any of them leaves a tree, and [2, 3] comes last, so that is the answer. For [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] the cycle is 1 - 2 - 3 - 4 - 1, and the answer is [1, 4]. The edge [1, 5] comes later in the input, but removing it would cut node 5 off.

    The algorithm should run in nearly O(n) time, written O(n·α(n)), and use O(n) extra space.

    Approach: add edges one by one and watch for the first cycle

    A slow way is to try each edge from the last one back, remove it, and check with a depth-first search whether the rest is still connected. That costs O(n^2).

    The faster way adds the edges in the order given and keeps track of which nodes are connected so far. When an edge joins two nodes that are already connected, it closes a cycle. The graph has exactly one cycle, and removing any edge of it leaves a tree, while removing an edge that is not on it cuts the tree in two. All the other edges of the cycle came earlier in the input, so the edge that closes the cycle is the last edge of the cycle, which is the answer.

    The test is only "are these two nodes already in the same group?", and union-find answers that quickly. It keeps each group as a tree: every node points to a parent, and the root, the one node that is its own parent, names the group. Two nodes are in the same group when they lead to the same root. To merge two groups, hang one root under the other.

    Two tricks keep the trees shallow:

    • Union by size. Always hang the smaller tree under the larger one. A node goes one level deeper only when its group at least doubles, so no path to a root has more than about log2(n) steps.
    • Path halving. While walking up to the root, point each visited node at its grandparent. Later walks from there take about half the steps.

    Together they make each operation O(α(n)) amortized, where α is the inverse Ackermann function, below 5 for any input a computer can hold.

    A tempting shortcut is to return the first edge whose two nodes have both appeared in earlier edges. It is wrong: for [[1, 2], [3, 4], [2, 3], [4, 5], [1, 5]] it returns [2, 3]. Nodes 2 and 3 have both been seen, but in two separate groups, {1, 2} and {3, 4}, and the edge joins them. The real cycle is 1 - 2 - 3 - 4 - 5 - 1, and the answer is [1, 5].

    Step by step

    1. Store n as edges.length. A tree of n nodes has n - 1 edges, and with the extra one there are n, so it is also the number of nodes.
    2. Create parent with Array.from({length: n + 1}, (_, i) => i), so each node starts as its own parent. Nodes start at 1, so the arrays have n + 1 entries and index 0 is never used. The _ is the unused value, and i is the index.
    3. Create size, n + 1 entries filled with 1. Only the roots' entries are kept up to date.
    4. Loop over edges in the given order, because the order decides which edge of the cycle is returned.
    5. Find the root of edge[0] into rootA, declared with let because it may be swapped.
    6. Find the root of edge[1] into rootB.
    7. Test for the cycle: if rootA === rootB, the two ends are already connected, so return edge.
    8. Make rootA the larger root. If size[rootA] < size[rootB], swap them with [rootA, rootB] = [rootB, rootA], a destructuring assignment.
    9. Merge: set parent[rootB] to rootA.
    10. Update the size: size[rootA] += size[rootB]. The size of rootB is never read again because it is no longer a root.
    11. Return [] after the loop. The input always contains a cycle, so the loop returns first, but a function with a return type must return on every path.
    12. Write find(parent, x): loop while parent[x] !== x.
    13. Halve the path: set parent[x] = parent[parent[x]], then x = parent[x]. Each turn climbs two levels.
    14. Return x, the root.

    The solution in TypeScript

    class Solution {
    findRedundantConnection(edges: number[][]): number[] {
        const n = edges.length;
        const parent: number[] = Array.from({length: n + 1}, (_, i) => i);
        const size: number[] = new Array(n + 1).fill(1);
        for (const edge of edges) {
            let rootA = this.find(parent, edge[0]);
            let rootB = this.find(parent, edge[1]);
            if (rootA === rootB) {
                return edge;
            }
            if (size[rootA] < size[rootB]) {
                [rootA, rootB] = [rootB, rootA];
            }
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        }
        return [];
    }

    find(parent: number[], x: number): number {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

    TypeScript details:

    • Arrays are passed by reference. find receives the same parent array and writes into it, so the path halving is seen by the caller. For parent = [0, 0, 1, 2], find(parent, 3) returns 0 and leaves [0, 0, 1, 1].
    • Reassigning a parameter. x = parent[x] changes only the local copy of the number. The caller's value is not affected, because numbers are passed by value.
    • Swapping with destructuring. [rootA, rootB] = [rootB, rootA] builds a temporary array and unpacks it. After a = 1, b = 2 the same line gives a = 2, b = 1. Both variables were declared with let, so they can be reassigned.
    • The returned array is the input's own. return edge hands back the pair from edges, not a copy. That is fine here, since nothing changes it afterwards.
    • Erased types. The annotations on parent, size and the signatures are checked by the compiler only.

    Complexity

    Time: O(n·α(n)). Each of the n edges makes two calls to find and at most one merge, each O(α(n)) amortized thanks to union by size and path halving. That is nearly O(n).

    Space: O(n). The parent and size arrays have n + 1 entries each. The loop in find uses no call stack, however long the walk.

    Edge cases and common mistakes

    • The smallest input. [[1, 2], [2, 3], [1, 3]] returns [1, 3]: the triangle's last edge.
    • Edges after the cycle. The answer is the edge that closes the cycle, even when other edges follow it. For [[1, 3], [3, 4], [1, 5], [3, 5], [2, 3]] the answer is [3, 5], though [2, 3] comes after it.
    • A cycle in the middle. [[1, 2], [2, 3], [3, 4], [2, 4], [4, 5], [5, 6]] returns [2, 4].
    • Comparing nodes instead of roots. Two nodes can be connected without sharing a parent. Always compare the roots from find, never parent[a] and parent[b].
    • Checking only whether both nodes were seen. It returns [2, 3] where [1, 5] is correct, as above.
    • Arrays too short. The nodes start at 1, so the arrays need n + 1 entries. With n entries, node n would be out of range.
    • Linking without size. If you always hang the first root under the second, a chain of edges [1, 2], [2, 3], ..., [999, 1000] followed by [1, 1000] builds a path where one lookup climbs 999 steps. Union by size keeps such chains short.

    Testing

    • [[1, 2], [1, 3], [2, 3]] gives [2, 3].
    • [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] gives [1, 4].
    • [[1, 2], [3, 4], [2, 3], [4, 5], [1, 5]] gives [1, 5].
    • [[1, 2], [2, 3], [1, 3]] gives [1, 3].
    • [[1, 2], [2, 3], [3, 4], [2, 4], [4, 5], [5, 6]] gives [2, 4].
    • [[1, 3], [3, 4], [1, 5], [3, 5], [2, 3]] gives [3, 5].
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free