Skip to main content
Talentd

Maximum Points Activated with One Addition - Solution & Explanation

HardArrayHash TableUnion Find12 min read
Practice this problem

Problem Statement

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 <= 105
  • points[i] = [xi, yi]
  • -109 <= xi, yi <= 109
  • points contains all distinct coordinates.

Approach Overview

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.

Solution

We can use a Union-Find data structure to solve this problem.

First, we map the x coordinates and y coordinates of all points into the same Union-Find structure. Specifically, we add a sufficiently large constant m (e.g., 3 times 10^9) to each y coordinate to ensure that the x and y coordinates do not conflict.

Next, we iterate over all points and union those that share the same x coordinate or the same y coordinate. This way, points with the same x or y coordinate will be grouped into the same set.

Finally, we count the number of points in each set and find the sizes of the two largest sets. Since we can add one new point to connect these two sets, the final answer is the sum of the sizes of the two largest sets plus 1.

The time complexity is O(n \alpha(n)), where n is the number of points and \alpha is the inverse Ackermann function. The space complexity is O(n).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Simulation with Hash MapsO(n^2)O(n)Small inputs or when exploring how the extra point connects components
Union-Find with Coordinate IndexingO(n α(n))O(n)General case and interview solution for efficiently merging activation groups

Video Solution

weekly contest 493 | leetcode 3870 | leetcode 3871 | leetcode 3872| leetcode 3873 | DP | DSU | DSA • Code With Vick • 799 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Maximum Points Activated with One Addition easy or hard?
Maximum Points Activated with One Addition is typically classified as a hard problem because it combines graph connectivity reasoning with an optimization step for adding a new point. Efficient solutions require understanding Union-Find and component size tracking.
Maximum Points Activated with One Addition Python/Java solution
Most implementations use a Union-Find class with path compression and union by size. Points are processed to merge existing connections, then coordinate maps identify which components a new point could link. The logic is identical across Python, Java, C++, Go, and TypeScript.
How to solve Maximum Points Activated with One Addition in O(n)?
Build connected components using Union-Find while grouping points by coordinates with hash tables. For each potential connection created by the added point, gather the unique component roots and sum their sizes. Because Union-Find operations are nearly constant time and lookups use hash maps, the total runtime approaches O(n).
What is the best approach for Maximum Points Activated with One Addition?
The most efficient method uses Union-Find (Disjoint Set Union) combined with hash maps that index points by coordinates or activation relationships. Build connected components from existing points, then evaluate how a single additional point could merge multiple components. This approach runs in about O(n α(n)) time with O(n) space.
Is Maximum Points Activated with One Addition asked at Google/Amazon/Meta?
Problems involving Union-Find and component merging frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require adding a node or edge to maximize connectivity are common graph and disjoint-set interview questions.
What data structure is used in Maximum Points Activated with One Addition?
The primary data structure is Union-Find (Disjoint Set Union) to maintain connected components and quickly merge groups. Hash tables are also used to map coordinates or relationships to point indices, enabling fast lookup of neighbors that should be connected.
What is the time complexity of Maximum Points Activated with One Addition?
The optimal Union-Find solution runs in O(n α(n)) time, where α(n) is the inverse Ackermann function from the disjoint set structure. In practice this behaves almost like O(n). Space complexity is O(n) for storing parent arrays, component sizes, and coordinate hash maps.

Ready to solve this problem?

Practice Maximum Points Activated with One Addition with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays