Today we're looking at a hard problem from a recent LeetCode contest: Maximum Points Activated with One Addition. It looks intimidating at first, but once you map out how the points interact with each other, it boils down to a classic graph problem.
Let's break it down.
The Problem
We're given an array of points on a 2D plane. If you activate a point, every other point that shares its exact X or Y coordinate also gets activated — creating a chain reaction until nothing new can trigger.
We're allowed to add exactly one new point at any empty integer coordinate. Place it to maximize the total number of activated points.
Example:
Input: points = [[1,1],[2,2],[3,1]]
Points [1,1] and [3,1] share y = 1, so they're in the same component.
[2,2] is isolated.
Add a point at [2,1] → bridges both components → all 4 points activate.
Intuition: Think in Graphs
When a problem says "if A connects to B, and B connects to C, they all trigger together" — that's a connected components problem.
Treat every point as a node. If two points share an X or Y coordinate, draw an edge between them. Points naturally cluster into isolated islands. Activate any point in an island and the whole island lights up.
Now, where does our new point fit?
Our new point has exactly one X and one Y coordinate. It acts as a bridge — hooking its X into one component and its Y into a completely different one. A single new point can connect at most two distinct components.
So the strategy is simple: find the two largest components and bridge them together.
But wait — what if that (x, y) spot is already occupied?
If it were already a point, those two components would already share a point, meaning they'd already be merged into one. So grabbing an X from component A and a Y from component B is guaranteed to land on an empty coordinate. No need to validate it.
Algorithm
- Build components using Union-Find (DSU)
- Group points by shared X or Y coordinates and union them
- Collect all component sizes
- Sort descending, take the top two and add
1for the new point
Walkthrough
points = [[1,1], [2,2], [3,1], [2,5]]
Processing:
i=0: (1,1) → x_first[1]=0, y_first[1]=0
i=1: (2,2) → x_first[2]=1, y_first[2]=1
i=2: (3,1) → x_first[3]=2, y=1 seen → union(2, 0) [shares y=1 with point 0]
i=3: (2,5) → x=2 seen → union(3, 1) [shares x=2 with point 1]
Components after union:
Component A: {[1,1], [3,1]} → size 2
Component B: {[2,2], [2,5]} → size 2
Best move: bridge A and B with a new point (e.g. [1,2] — shares x=1 with A, y=2 with B)
Answer = 2 + 2 + 1 = 5
Solution
Python
class Solution:
def maxActivated(self, points: List[List[int]]) -> int:
n = len(points)
parent = list(range(n))
size = [1] * n
def find(i):
if parent[i] != i:
parent[i] = find(parent[i]) # path compression
return parent[i]
def union(i, j):
root_i, root_j = find(i), find(j)
if root_i != root_j:
parent[root_i] = root_j
size[root_j] += size[root_i]
x_first = {}
y_first = {}
for i, (x, y) in enumerate(points):
if x in x_first:
union(i, x_first[x])
else:
x_first[x] = i
if y in y_first:
union(i, y_first[y])
else:
y_first[y] = i
comp_sizes = [size[i] for i in range(n) if parent[i] == i]
comp_sizes.sort(reverse=True)
if len(comp_sizes) >= 2:
return comp_sizes[0] + comp_sizes[1] + 1
return comp_sizes[0] + 1
C++
class Solution {
public:
int maxActivated(vector<vector<int>>& points) {
int n = points.size();
vector<int> parent(n), size(n, 1);
iota(parent.begin(), parent.end(), 0);
function<int(int)> find = [&](int i) {
if (parent[i] != i) parent[i] = find(parent[i]);
return parent[i];
};
auto unite = [&](int i, int j) {
int ri = find(i), rj = find(j);
if (ri != rj) {
parent[ri] = rj;
size[rj] += size[ri];
}
};
unordered_map<int, int> x_first, y_first;
for (int i = 0; i < n; ++i) {
int x = points[i][0], y = points[i][1];
if (x_first.count(x)) unite(i, x_first[x]);
else x_first[x] = i;
if (y_first.count(y)) unite(i, y_first[y]);
else y_first[y] = i;
}
vector<int> comp_sizes;
for (int i = 0; i < n; ++i)
if (parent[i] == i)
comp_sizes.push_back(size[i]);
sort(comp_sizes.rbegin(), comp_sizes.rend());
if (comp_sizes.size() >= 2)
return comp_sizes[0] + comp_sizes[1] + 1;
return comp_sizes[0] + 1;
}
};
Complexity
| Complexity | Notes | |
|---|---|---|
| Time | O(N log N) | Union-Find is ~O(N), sorting component sizes dominates |
| Space | O(N) | parent/size arrays + coordinate hash maps |
Common Mistakes
Forgetting the +1 — The new point itself counts toward the total. Easy to miss when you're focused on bridging components.
Checking if the bridge coordinate is empty — You don't need to. As explained above, it's mathematically guaranteed to be empty. Don't waste time validating it.
Using BFS/DFS instead of Union-Find — BFS/DFS works but you'd need to build an adjacency list first, which adds complexity. Union-Find here is cleaner and faster since we're just grouping by shared coordinates.
Only checking parent[i] == i for roots — After path compression, this is the correct way to identify component roots. Don't re-use size[] values from non-root nodes.
Key Takeaway
The insight that unlocks this problem is recognizing the chain-activation rule as a graph structure. Once you see that shared coordinates create edges, Union-Find handles the rest.
The second insight — that a new point bridges at most two components and is always a valid empty cell — turns a seemingly complex optimization into just finding the two largest component sizes.
This pattern shows up in a family of problems:
- Connecting islands with one bridge
- Merging groups with one extra element
- "What's the best single addition/connection?" problems
Whenever you see chain reactions or transitive grouping, think Union-Find first.
Top comments (0)