Watch 2 video solutions for Maximum Points Activated with One Addition, a hard level problem involving Array, Hash Table, Union Find. This walkthrough by CodeWithMeGuys has 247 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 2D integer array points, where points[i] = [xi, yi] represents the coordinates of the ith point. All coordinates in points are distinct.
If a point is activated, then all points that have the same x-coordinate or y-coordinate become activated as well.
Activation continues until no additional points can be activated.
You may add one additional point at any integer coordinate (x, y) not already present in points. Activation begins by activating this newly added point.
Return an integer denoting the maximum number of points that can be activated, including the newly added point.
Example 1:
Input: points = [[1,1],[1,2],[2,2]]
Output: 4
Explanation:
Adding and activating a point such as (1, 3) causes activations:
(1, 3) shares x = 1 with (1, 1) and (1, 2) -> (1, 1) and (1, 2) become activated.(1, 2) shares y = 2 with (2, 2) -> (2, 2) becomes activated.Thus, the activated points are (1, 3), (1, 1), (1, 2), (2, 2), so 4 points in total. We can show this is the maximum activated.
Example 2:
Input: points = [[2,2],[1,1],[3,3]]
Output: 3
Explanation:
Adding and activating a point such as (1, 2) causes activations:
(1, 2) shares x = 1 with (1, 1) -> (1, 1) becomes activated.(1, 2) shares y = 2 with (2, 2) -> (2, 2) becomes activated.Thus, the activated points are (1, 2), (1, 1), (2, 2), so 3 points in total. We can show this is the maximum activated.
Example 3:
Input: points = [[2,3],[2,2],[1,1],[4,5]]
Output: 4
Explanation:
Adding and activating a point such as (2, 1) causes activations:
(2, 1) shares x = 2 with (2, 3) and (2, 2) -> (2, 3) and (2, 2) become activated.(2, 1) shares y = 1 with (1, 1) -> (1, 1) becomes activated.Thus, the activated points are (2, 1), (2, 3), (2, 2), (1, 1), so 4 points in total.
Constraints:
1 <= points.length <= 105points[i] = [xi, yi]-109 <= xi, yi <= 109points contains all distinct coordinates.Problem Overview: You are given a set of points and may add exactly one additional point. Points become activated when they connect through shared coordinates or relationships defined by the problem. The goal is to place one extra point so the resulting connected structure activates the maximum number of points.
Approach 1: Component Simulation with Hash Maps (O(n^2) time, O(n) space)
A direct strategy checks every possible candidate location that could connect multiple existing groups. For each candidate addition, iterate through the points and determine which ones become connected using coordinate-based lookups stored in hash maps. Maintain adjacency or group membership, then simulate merging affected points. This works for small inputs but becomes expensive because every potential addition may require scanning many points.
Approach 2: Union-Find with Coordinate Grouping (O(n α(n)) time, O(n) space)
The efficient solution models the problem as dynamic connectivity using Union Find. Each point belongs to a component. Use hash maps keyed by coordinates (or other activation relationships) to quickly identify points that should be merged. When processing the existing points, union any pair that already activates each other. Maintain component sizes in the disjoint set structure so you can quickly compute how many points a merge would activate.
After building the initial components, evaluate how a single added point could connect multiple groups. Using coordinate maps stored in a hash table, identify which components would become neighbors of the new point. Deduplicate component roots, sum their sizes, and add one for the inserted point. Track the maximum possible activation across all candidate connections.
This works because Union-Find supports near constant-time find and union operations. Path compression and union by rank keep operations close to O(α(n)), which is effectively constant for practical input sizes. The hash maps prevent scanning the entire array when searching for connectable points.
Recommended for interviews: Interviewers expect the Union Find approach combined with coordinate indexing. The brute-force simulation shows you understand the connectivity requirement, but the optimized solution demonstrates knowledge of disjoint set structures and how to merge components efficiently in large graphs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation with Hash Maps | O(n^2) | O(n) | Small inputs or when exploring how the extra point connects components |
| Union-Find with Coordinate Indexing | O(n α(n)) | O(n) | General case and interview solution for efficiently merging activation groups |