LeetCode 3873 - Maximum Points Activated with One Addition

LeetCode Problem 3873

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Union-Find

Solution

Problem Understanding

The problem is asking us to simulate a chain reaction of activations on a set of 2D points. Each point is defined by its (x, y) coordinates and all points are distinct. When a point is activated, any point sharing the same x coordinate or y coordinate becomes activated as well. This activation propagates recursively: newly activated points can activate other points based on the same rule.

The twist is that we are allowed to add one additional point at any integer coordinate not already in the set. Activation begins from this newly added point, and we want to determine the maximum number of points that can ultimately be activated, including the newly added point.

The input is a list of points, and the output is a single integer representing the maximum number of activated points. The constraints indicate that the input size can be up to 10^5 points, and the coordinates can be very large, ranging from -10^9 to 10^9. This rules out naive approaches that try all possible new points in the entire integer grid, since the search space is effectively infinite. The problem guarantees that no two points have the same coordinates, which simplifies the problem by avoiding ambiguity in activation. Edge cases might include very sparse distributions of points, points forming a line or a cluster, or when activating any new point only connects to one existing point.

Approaches

Brute-Force Approach

A brute-force approach would consider adding a new point at every possible integer coordinate and simulate the full activation chain. For each candidate point, we would recursively or iteratively mark activated points based on shared x or y coordinates, then count the total activated points. While this approach is guaranteed to find the correct maximum, it is infeasible because the number of possible coordinates is essentially unbounded, and simulating activations for each candidate point requires O(n) time per simulation. With n up to 10^5, this would be far too slow.

Key Insight for Optimal Approach

The key insight is that adding a point only matters if it connects two or more clusters of points. Each cluster can be defined as a set of points connected via shared x or y coordinates. Using a Union-Find (Disjoint Set Union, DSU) data structure, we can precompute these clusters efficiently. After identifying clusters, the optimal new point is always at an intersection of an x coordinate from one cluster and a y coordinate from another cluster that are not already occupied by an existing point. By evaluating only these candidate intersections, we reduce the search space drastically from the infinite plane to at most n^2 candidates, which is manageable with proper optimization using hash maps.

Here, α(n) is the inverse Ackermann function, practically constant for all reasonable n.

Algorithm Walkthrough

1. Initialize Union-Find: Assign each point an ID and initialize a Union-Find structure. Each point starts in its own set.
2. Connect points by x-coordinate: Use a hash map from x-coordinate to point IDs. For points sharing the same x, union them in the DSU.
3. Connect points by y-coordinate: Similarly, use a hash map from y-coordinate to point IDs and union points sharing the same y.
4. Compute cluster sizes: After all unions, determine the size of each cluster by counting points in the same root set.
5. Map x and y to clusters: For each x, record all clusters that have points with this x. Similarly for y.
6. Identify candidate intersections: Consider new points at intersections of x and y coordinates from different clusters. Skip coordinates that already exist.
7. Compute activation potential: For each candidate intersection, sum the sizes of the clusters it connects plus 1 (for the new point). Keep track of the maximum.
8. Return the result: The maximum computed from all candidates is the final answer.

Why it works: This works because any optimal new point must connect at least two previously disconnected clusters. Connecting points within the same cluster adds nothing, and considering only existing x and y coordinates ensures the new point will maximize activation without testing the infinite plane. Union-Find guarantees we know the exact cluster memberships and sizes efficiently.

Python Solution

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return
        if self.size[xr] < self.size[yr]:
            xr, yr = yr, xr
        self.parent[yr] = xr
        self.size[xr] += self.size[yr]

class Solution:
    def maxActivated(self, points: list[list[int]]) -> int:
        n = len(points)
        point_index = {tuple(p): i for i, p in enumerate(points)}
        uf = UnionFind(n)

        x_map = {}
        y_map = {}
        for i, (x, y) in enumerate(points):
            if x in x_map:
                uf.union(i, x_map[x])
            else:
                x_map[x] = i
            if y in y_map:
                uf.union(i, y_map[y])
            else:
                y_map[y] = i

        cluster_size = {}
        for i in range(n):
            root = uf.find(i)
            cluster_size[root] = cluster_size.get(root, 0) + 1

        x_clusters = {}
        y_clusters = {}
        for i, (x, y) in enumerate(points):
            root = uf.find(i)
            x_clusters.setdefault(x, set()).add(root)
            y_clusters.setdefault(y, set()).add(root)

        max_activated = max(cluster_size.values())
        existing_points = set(point_index.keys())

        for x in x_clusters:
            for y in y_clusters:
                if (x, y) in existing_points:
                    continue
                combined_clusters = x_clusters[x] | y_clusters[y]
                total = 1 + sum(cluster_size[root] for root in combined_clusters)
                max_activated = max(max_activated, total)

        return max_activated

This Python implementation first builds the clusters using Union-Find, then computes the maximum number of activated points by trying candidate intersections formed from existing x and y coordinates. It ensures no existing points are duplicated.

Go Solution

type UnionFind struct {
    parent []int
    size   []int
}

func NewUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    size := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
        size[i] = 1
    }
    return &UnionFind{parent, size}
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
    xr, yr := uf.Find(x), uf.Find(y)
    if xr == yr {
        return
    }
    if uf.size[xr] < uf.size[yr] {
        xr, yr = yr, xr
    }
    uf.parent[yr] = xr
    uf.size[xr] += uf.size[yr]
}

func maxActivated(points [][]int) int {
    n := len(points)
    pointIndex := map[[2]int]int{}
    for i, p := range points {
        pointIndex[[2]int{p[0], p[1]}] = i
    }

    uf := NewUnionFind(n)

    xMap := map[int]int{}
    yMap := map[int]int{}
    for i, p := range points {
        x, y := p[0], p[1]
        if j, ok := xMap[x]; ok {
            uf.Union(i, j)
        } else {
            xMap[x] = i
        }
        if j, ok := yMap[y]; ok {
            uf.Union(i, j)
        } else {
            yMap[y] = i
        }
    }

    clusterSize := map[int]int{}
    for i := 0; i < n; i++ {
        root := uf.Find(i)
        clusterSize[root]++
    }

    xClusters := map[int]map[int]struct{}{}
    yClusters := map[int]map[int]struct{}{}
    for i, p := range points {
        root := uf.Find(i)
        x, y := p[0], p[1]
        if _, ok := xClusters[x]; !ok {
            xClusters[x] = map[int]struct{}{}
        }
        xClusters[x][root] = struct{}{}
        if _, ok := yClusters[y]; !ok {
            yClusters[y] = map[int]struct{}{}
        }
        yClusters[y][root] = struct{}{}
    }

    maxActivated := 0