3873. Maximum Points Activated with One Addition

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a 2D integer array points, where points[i] = [xi, yi] represents the coordinates of the i-th point. All coordinates in points are distinct.

The activation rule works as follows: if a point is activated, then every other point that shares the same x-coordinate or the same y-coordinate with it also becomes activated. This activation then spreads from those newly activated points in the same way, continuing until no additional points can be activated.

Before activation starts, you are allowed to add exactly one additional point at any integer coordinate (x, y) that is not already present in points. The activation process begins by activating this newly added point.

Your task is to determine the maximum number of points that can be activated, counting the newly added point as well, and return that value as an integer.

For example, if you place the new point so that it shares an x-coordinate with one group of points and a y-coordinate with another group of points, both groups (plus the new point) all become activated together. Choosing the placement wisely lets you connect and activate as many points as possible.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Disjoint Set Union?

This problem maps to Disjoint Set Union through a short path in the full flowchart.

Union-Find groups points by shared x or y coordinates, then finds the two largest components to bridge with a new point.

Open in Flowchart

Intuition

The key observation is to understand what "activation spreading" really means. When two points share the same x-coordinate or the same y-coordinate, activating one activates the other. This relationship is transitive: if point A connects to B, and B connects to C, then activating A will eventually activate C as well. This naturally forms groups (connected components) of points that are all linked together through shared x or y coordinates.

If we activate any single point inside a group, the entire group lights up. So the original points are partitioned into several independent groups, where each group has a fixed size.

Now think about the new point we are allowed to add. By placing it cleverly, we can give it the same x-coordinate as points in one group and the same y-coordinate as points in another group. This means the new point acts as a bridge: activating it activates both groups at once, plus the new point itself. Since a point has exactly two coordinates (one x and one y), the new point can connect at most two different groups.

To maximize the total number of activated points, we therefore want to pick the two largest groups, bridge them with the new point, and add 1 for the new point itself. The answer is size of largest group + size of second largest group + 1.

To figure out the groups efficiently, we treat each coordinate value as a node and merge them. A point (x, y) tells us its x-coordinate and y-coordinate belong to the same group, so we union them. To avoid an x value like 5 accidentally clashing with a y value like 5, we shift all y-coordinates by a large constant m (e.g., 3 × 10^9), making x and y + m live in separate ranges. After all unions, every point belongs to the group identified by the root of its x-coordinate, so we simply count how many points fall into each group and pick the top two.

Pattern Learn more about Union Find patterns.

Solution Approach

We use a Union-Find (Disjoint Set Union) data structure to group the coordinates together.

Step 1: Map coordinates into one Union-Find structure

Each point (x, y) tells us that its x-coordinate and y-coordinate must belong to the same group. To store both x and y values inside the same Union-Find without conflicts, we add a large constant m = 3 × 10^9 to every y-coordinate. This way, an x-value and a y-value that happen to be numerically equal (like x = 5 and y = 5) are kept distinct, because the y-value becomes 5 + m. So for every point we perform:

uf.union(x, y + m)

Step 2: The Union-Find implementation

The UnionFind class uses dictionaries instead of fixed-size arrays, since coordinate values can be arbitrary integers:

find(x) lazily creates a node the first time it sees x (setting self.p[x] = x and self.size[x] = 1). It uses path compression (self.p[x] = self.find(self.p[x])) so that future lookups are faster.
union(a, b) finds the roots of both elements. If they are already in the same set, it returns False. Otherwise it merges them using union by size — the smaller tree is attached under the larger one, and the sizes are combined. This keeps the trees shallow.

Step 3: Count the size of each group

After all unions, we want to know how many original points fall into each group. We iterate over the points and, using the x-coordinate as a representative, find its group root and increment a counter:

cnt = Counter()
for x, _ in points:
    cnt[uf.find(x)] += 1

Each point is counted exactly once via its x-coordinate, and uf.find(x) returns the identifier of the group that point belongs to. So cnt maps each group root to the number of points in that group.

Step 4: Find the two largest groups

Since the newly added point can bridge at most two groups (it has one x-coordinate and one y-coordinate), we scan all group sizes and track the two largest values, mx1 and mx2:

mx1 = mx2 = 0
for x in cnt.values():
    if mx1 < x:
        mx2 = mx1
        mx1 = x
    elif mx2 < x:
        mx2 = x

Step 5: Return the answer

The final answer connects the two largest groups through the new point, plus the new point itself:

return mx1 + mx2 + 1

Complexity Analysis

Time complexity: O(n × α(n)), where n is the number of points and α is the inverse Ackermann function from the Union-Find operations, which is nearly constant in practice.
Space complexity: O(n), for storing the parent and size dictionaries as well as the counter.

Example Walkthrough

Let's trace through the solution with a small concrete example.

Input:

points = [[1, 1], [1, 5], [3, 5], [7, 2], [7, 9]]

Let m = 3 × 10^9. We'll write y + m simply as y' for readability (so 1' means 1 + m, 5' means 5 + m, etc.).

Step 1 & 2: Build the Union-Find by unioning x with y + m for each point.

We process each point and union its x-coordinate with its shifted y-coordinate:

Point	Operation	Effect on groups
`[1, 1]`	`union(1, 1')`	`{1, 1'}`
`[1, 5]`	`union(1, 5')`	`1` already with `1'`; merge in `5'` → `{1, 1', 5'}`
`[3, 5]`	`union(3, 5')`	`5'` is in the group above; merge `3` → `{1, 1', 5', 3}`
`[7, 2]`	`union(7, 2')`	`{7, 2'}`
`[7, 9]`	`union(7, 9')`	`7` already with `2'`; merge `9'` → `{7, 2', 9'}`

Why this works: Notice points [1,1] and [1,5] share x-coordinate 1, so they must activate together — and the union of 1 keeps them in one group. Then [1,5] and [3,5] share y-coordinate 5, so [3,5] joins too via the shared node 5'. This is the transitive "bridging" through shared coordinates.

After all unions we have two connected components among the coordinate nodes:

Group A: {1, 1', 5', 3} — comes from points [1,1], [1,5], [3,5]
Group B: {7, 2', 9'} — comes from points [7,2], [7,9]

Step 3: Count how many original points fall into each group (via the x-coordinate).

We look up uf.find(x) for each point's x-value:

Point	x	`find(x)` lands in	Counter update
`[1, 1]`	1	Group A	A → 1
`[1, 5]`	1	Group A	A → 2
`[3, 5]`	3	Group A	A → 3
`[7, 2]`	7	Group B	B → 1
`[7, 9]`	7	Group B	B → 2

Resulting counts: cnt = { A: 3, B: 2 }.

Step 4: Find the two largest group sizes.

Scanning the values [3, 2]:

See 3: mx1 = 3, mx2 = 0
See 2: 2 < 3 but 2 > 0, so mx2 = 2

We get mx1 = 3 and mx2 = 2.

Step 5: Compute the answer.

answer = mx1 + mx2 + 1 = 3 + 2 + 1 = 6

Verifying the placement: Group A contains x-coordinates {1, 3} and Group B contains x-coordinates {7} with y-coordinates {2, 9}. We add a new point that shares an x with Group A and a y with Group B — for instance, (3, 2). Activating (3, 2):

Its x-coordinate 3 lights up Group A (all 3 points).
Its y-coordinate 2 lights up Group B (all 2 points).
Plus the new point itself.

Total activated = 3 + 2 + 1 = 6, matching our computed answer. ✅

Solution Implementation

1from typing import List
2from collections import Counter
3
4
5class UnionFind:
6    """Union-Find (Disjoint Set Union) with union by size and path compression."""
7
8    def __init__(self) -> None:
9        # parent maps each node to its parent; nodes are created lazily
10        self.parent = {}
11        # tree_size tracks the size of the tree rooted at each node
12        self.tree_size = {}
13
14    def find(self, x: int) -> int:
15        # Lazily initialize a node the first time it is seen
16        if x not in self.parent:
17            self.parent[x] = x
18            self.tree_size[x] = 1
19        # Path compression: point x directly to the root
20        if self.parent[x] != x:
21            self.parent[x] = self.find(self.parent[x])
22        return self.parent[x]
23
24    def union(self, a: int, b: int) -> bool:
25        root_a, root_b = self.find(a), self.find(b)
26        # Already in the same set, nothing to merge
27        if root_a == root_b:
28            return False
29        # Union by size: attach the smaller tree under the larger one
30        if self.tree_size[root_a] > self.tree_size[root_b]:
31            self.parent[root_b] = root_a
32            self.tree_size[root_a] += self.tree_size[root_b]
33        else:
34            self.parent[root_a] = root_b
35            self.tree_size[root_b] += self.tree_size[root_a]
36        return True
37
38
39class Solution:
40    def maxActivated(self, points: List[List[int]]) -> int:
41        uf = UnionFind()
42        # Offset to keep y-values in a separate numeric range from x-values,
43        # so x and y never collide as the same node id
44        offset = int(3e9)
45
46        # Connect each point's x with its y (shifted by offset).
47        # This groups together all coordinates linked through shared points.
48        for x, y in points:
49            uf.union(x, y + offset)
50
51        # Count how many points fall into each connected component,
52        # keyed by the component root of the x-coordinate.
53        component_count = Counter()
54        for x, _ in points:
55            component_count[uf.find(x)] += 1
56
57        # Track the two largest component sizes
58        max1 = max2 = 0
59        for count in component_count.values():
60            if max1 < count:
61                max2 = max1
62                max1 = count
63            elif max2 < count:
64                max2 = count
65
66        # Combine the two largest groups, plus one extra activation
67        return max1 + max2 + 1
68

1if (p.get(x) != x) {  // Comparing Long objects with !=
2```
3
4When comparing `Long` objects with `!=`, Java compares **references**, not values. For values outside the cache range `[-128, 127]`, autoboxing creates new objects, so `!=` may return `true` even when values are equal. Since this code uses `+ 3e9` offsets (large values), this comparison would behave incorrectly. The same issue exists with `pa == pb`.
5
6## Standardized Version
7
8```java
9class UnionFind {
10    // Maps each node to its parent node
11    private final Map<Long, Long> parent = new HashMap<>();
12    // Maps each root node to the size of its component
13    private final Map<Long, Integer> size = new HashMap<>();
14
15    /**
16     * Finds the root representative of x with path compression.
17     * Lazily initializes x as its own parent if not seen before.
18     */
19    long find(long x) {
20        if (!parent.containsKey(x)) {
21            parent.put(x, x);
22            size.put(x, 1);
23        }
24        // Use longValue() comparison to avoid Long reference equality pitfalls
25        if (parent.get(x) != x) {
26            parent.put(x, find(parent.get(x)));
27        }
28        return parent.get(x);
29    }
30
31    /**
32     * Unions the sets containing a and b using union by size.
33     * Returns true if a merge happened, false if already connected.
34     */
35    boolean union(long a, long b) {
36        long rootA = find(a);
37        long rootB = find(b);
38        if (rootA == rootB) {
39            return false;
40        }
41
42        int sizeA = size.get(rootA);
43        int sizeB = size.get(rootB);
44        // Attach the smaller tree under the larger tree
45        if (sizeA > sizeB) {
46            parent.put(rootB, rootA);
47            size.put(rootA, sizeA + sizeB);
48        } else {
49            parent.put(rootA, rootB);
50            size.put(rootB, sizeA + sizeB);
51        }
52        return true;
53    }
54}
55
56class Solution {
57    public int maxActivated(int[][] points) {
58        UnionFind uf = new UnionFind();
59        // Offset to separate the x-coordinate space from the y-coordinate space,
60        // so x-values and y-values never collide in the same key range.
61        long offset = (long) 3e9;
62
63        // Treat each point as an edge connecting its x-coordinate node
64        // to its (offset) y-coordinate node, grouping rows and columns.
65        for (int[] point : points) {
66            uf.union(point[0], point[1] + offset);
67        }
68
69        // Count how many points fall into each connected component.
70        Map<Long, Integer> componentCount = new HashMap<>();
71        for (int[] point : points) {
72            componentCount.merge(uf.find(point[0]), 1, Integer::sum);
73        }
74
75        // Track the two largest component sizes.
76        int largest = 0;
77        int secondLargest = 0;
78        for (int count : componentCount.values()) {
79            if (largest < count) {
80                secondLargest = largest;
81                largest = count;
82            } else if (secondLargest < count) {
83                secondLargest = count;
84            }
85        }
86
87        // Combine the two biggest components plus one extra activation.
88        return largest + secondLargest + 1;
89    }
90}
91```
92
93## Important Note on the Bug
94
95The lines marked with reference comparison of `Long` objects (`parent.get(x) != x` and originally `p.get(x) != x`) are unsafe. To make the code **correct**, you should compare primitive `long` values:
96
97```java
98// Safer find() body:
99long root = parent.get(x);
100if (root != x) {                       // both unboxed to long → value comparison
101    long compressed = find(root);
102    parent.put(x, compressed);
103    return compressed;
104}
105return x;
106

1class UnionFind {
2public:
3    // Maps each node to its parent node
4    unordered_map<long long, long long> parent;
5    // Maps each root node to the size of its component
6    unordered_map<long long, int> size;
7
8    // Find the root of node x with path compression
9    long long find(long long x) {
10        // Lazily initialize the node if it hasn't been seen before
11        if (!parent.count(x)) {
12            parent[x] = x;
13            size[x] = 1;
14        }
15        // Path compression: point x directly to its root
16        if (parent[x] != x) {
17            parent[x] = find(parent[x]);
18        }
19        return parent[x];
20    }
21
22    // Union two nodes by size; returns false if already in the same set
23    bool unite(long long a, long long b) {
24        long long rootA = find(a), rootB = find(b);
25        if (rootA == rootB) return false;
26
27        // Attach the smaller tree under the larger tree
28        if (size[rootA] > size[rootB]) {
29            parent[rootB] = rootA;
30            size[rootA] += size[rootB];
31        } else {
32            parent[rootA] = rootB;
33            size[rootB] += size[rootA];
34        }
35        return true;
36    }
37};
38
39class Solution {
40public:
41    int maxActivated(vector<vector<int>>& points) {
42        UnionFind uf;
43        // Offset to separate the coordinate space of the second dimension
44        // from the first, avoiding collisions between p[0] and p[1] values
45        long long offset = (long long) 3e9;
46
47        // Connect each point's two coordinates so that points sharing a
48        // row or column end up in the same connected component
49        for (auto& point : points) {
50            uf.unite(point[0], point[1] + offset);
51        }
52
53        // Count how many points belong to each connected component (by root)
54        unordered_map<long long, int> countByRoot;
55        for (auto& point : points) {
56            long long root = uf.find(point[0]);
57            countByRoot[root]++;
58        }
59
60        // Track the two largest component sizes
61        int firstMax = 0, secondMax = 0;
62        for (auto& [root, count] : countByRoot) {
63            if (firstMax < count) {
64                secondMax = firstMax;
65                firstMax = count;
66            } else if (secondMax < count) {
67                secondMax = count;
68            }
69        }
70
71        // Combine the two largest components plus one additional activation
72        return firstMax + secondMax + 1;
73    }
74};
75

1// Parent pointer map for the union-find structure
2const parent: Map<number, number> = new Map();
3// Size map tracking the number of elements in each set (keyed by root)
4const setSize: Map<number, number> = new Map();
5
6/**
7 * Find the root representative of x with path compression.
8 * Lazily initializes x as its own parent with size 1 if unseen.
9 */
10function find(x: number): number {
11    // Lazy initialization: a new node points to itself with size 1
12    if (!parent.has(x)) {
13        parent.set(x, x);
14        setSize.set(x, 1);
15    }
16    // Path compression: link x directly to the root
17    if (parent.get(x)! !== x) {
18        parent.set(x, find(parent.get(x)!));
19    }
20    return parent.get(x)!;
21}
22
23/**
24 * Union the sets containing a and b using union-by-size.
25 * Returns true if a merge happened, false if they were already connected.
26 */
27function union(a: number, b: number): boolean {
28    const rootA = find(a);
29    const rootB = find(b);
30    // Already in the same set, nothing to merge
31    if (rootA === rootB) return false;
32
33    const sizeA = setSize.get(rootA)!;
34    const sizeB = setSize.get(rootB)!;
35
36    // Attach the smaller tree under the larger tree
37    if (sizeA > sizeB) {
38        parent.set(rootB, rootA);
39        setSize.set(rootA, sizeA + sizeB);
40    } else {
41        parent.set(rootA, rootB);
42        setSize.set(rootB, sizeA + sizeB);
43    }
44    return true;
45}
46
47/**
48 * Computes the maximum number of activated points by combining the two
49 * largest connected groups (plus one extra activation).
50 */
51function maxActivated(points: number[][]): number {
52    // Reset global union-find state for a fresh run
53    parent.clear();
54    setSize.clear();
55
56    // Offset used to separate y-coordinates from x-coordinates
57    // so they live in disjoint key spaces within the same structure
58    const offset = 3e9;
59
60    // Connect each point's x value with its offset y value
61    for (const [x, y] of points) {
62        union(x, y + offset);
63    }
64
65    // Count how many points belong to each connected component,
66    // keyed by the root of the point's x value
67    const count = new Map<number, number>();
68    for (const [x] of points) {
69        const root = find(x);
70        count.set(root, (count.get(root) ?? 0) + 1);
71    }
72
73    // Track the two largest group sizes
74    let max1 = 0;
75    let max2 = 0;
76    for (const size of count.values()) {
77        if (max1 < size) {
78            max2 = max1;
79            max1 = size;
80        } else if (max2 < size) {
81            max2 = size;
82        }
83    }
84
85    // Sum of the two largest groups, plus one additional activation
86    return max1 + max2 + 1;
87}
88

Time and Space Complexity

Time Complexity

The time complexity is O(n α(n)), where n is the number of points and α is the inverse Ackermann function. The analysis is as follows:

The first loop iterates over all points, performing one union operation per point. Each union internally calls find twice, and with path compression (in find) combined with union by size (in union), the amortized cost of each operation is O(α(n)). This loop contributes O(n α(n)).
The second loop also iterates over all points, performing one find operation per point. This contributes another O(n α(n)).
The final loop iterates over the values of cnt, which contains at most n distinct roots, costing O(n).

Combining these, the overall time complexity is dominated by the union-find operations, yielding O(n α(n)).

Space Complexity

The space complexity is O(n). The analysis is as follows:

The UnionFind structure maintains two dictionaries, p and size. Each point contributes a node x and a node y + m, so at most O(n) distinct keys are stored across both dictionaries.
The Counter object cnt stores at most n distinct root keys, requiring O(n) space.
The recursive find may incur a call stack of depth up to O(n) in the worst case, but this does not exceed the dominant O(n) term.

Therefore, the total space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Counting points by x-coordinate when distinct points share the same x-value

The line that builds the component counter is the most error-prone part of this solution:

component_count = Counter()
for x, _ in points:
    component_count[uf.find(x)] += 1

This works only because we iterate over every point and use its x-coordinate as the lookup key. A tempting "optimization" is to deduplicate x-coordinates first, or to count over uf.parent keys directly, like this:

# WRONG: counts each coordinate node, not each point
for node in uf.parent:
    component_count[uf.find(node)] += 1

This is incorrect for two reasons:

It counts coordinate values, not points. If two points (5, 1) and (5, 9) share x = 5, the x-node 5 exists only once in the Union-Find, so the group would be undercounted by one point.
It mixes x-nodes and y-nodes. Iterating over uf.parent includes the offset y-nodes (y + offset), inflating every count by the number of distinct y-values.

Solution: Always count by iterating over the original points list, using a consistent representative (the x-coordinate). Each point is then counted exactly once:

component_count = Counter()
for x, _ in points:
    component_count[uf.find(x)] += 1

Pitfall 2: An insufficient or risky offset value

The offset 3e9 separates x-nodes from y-nodes so that a coordinate like x = 5 never collides with y = 5 (stored as 5 + offset). Two mistakes commonly happen here:

Using int(3e9) carelessly. Floating-point literal 3e9 is fine here since it represents exactly, but writing something like int(2.1e9) or relying on float arithmetic for large offsets can introduce precision loss. Prefer an explicit integer literal:

offset = 3_000_000_000

Choosing an offset smaller than the coordinate range. If coordinates can be as large as 10^9 and the offset is also around 10^9, a large x-value could overlap with a small shifted y-value. The offset must strictly exceed the maximum possible coordinate magnitude. Given constraints up to 10^9, an offset of 3 × 10^9 safely clears the range.

Solution: Use an integer offset strictly larger than the maximum coordinate value, e.g. offset = 3_000_000_000.

Pitfall 3: Forgetting the new point can bridge at most two groups

A natural misreading of the problem is to assume the new point activates all groups it touches. But a single point has exactly one x-coordinate and one y-coordinate, so it can connect to at most:

one group through its x-coordinate, and
one group through its y-coordinate.

That is why we take only the two largest components (max1 + max2) rather than summing all of them. Summing every group would massively overcount.

Solution: Track only the top two component sizes and add 1 for the new point:

return max1 + max2 + 1

Pitfall 4: Recursion depth in `find` for large inputs

The find method is implemented recursively:

if self.parent[x] != x:
    self.parent[x] = self.find(self.parent[x])

Before path compression takes full effect, a long chain can be built up, and a deep recursion may hit Python's default recursion limit (1000) for very large or adversarial inputs.

Solution: Use an iterative find with two-pass path compression to avoid stack overflow:

def find(self, x: int) -> int:
    if x not in self.parent:
        self.parent[x] = x
        self.tree_size[x] = 1
        return x
    root = x
    while self.parent[root] != root:
        root = self.parent[root]
    while self.parent[x] != root:
        self.parent[x], x = root, self.parent[x]
    return root

This preserves path compression while keeping the call stack flat.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: