How do you solve Maximum Points Activated with One Addition on LeetCode?

Maximum Points Activated with One Addition (LeetCode #3873) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Activation spreads through shared coordinates.

What is the time complexity of Maximum Points Activated with One Addition?

The optimal solution for Maximum Points Activated with One Addition runs in O(n) time and uses O(n) space. The DSU operations are nearly constant time, leading to linear complexity overall.

What is the brute force solution for Maximum Points Activated with One Addition?

The brute force approach for Maximum Points Activated with One Addition is Brute Force, with O(n²) time complexity and O(1) space complexity. Try adding a point at every possible coordinate and count activated points. This method is inefficient as it checks all combinations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Maximum Points Activated with One Addition?

Maximum Points Activated with One Addition uses the following concepts: Array, Hash Table, Union-Find. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Maximum Points Activated with One Addition?

Explain your thought process clearly. Discuss edge cases and constraints. Practice similar problems to build confidence.

What are common mistakes when solving Maximum Points Activated with One Addition?

Forgetting to check for existing points. Not handling disjoint sets correctly.

#3873

Maximum Points Activated with One Addition

Hard

ArrayHash TableUnion-FindHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Use a disjoint-set union (DSU) to group points by shared x or y coordinates. This allows efficient merging and counting.

⚙️

Algorithm

3 steps

1Step 1: Initialize DSU structure to group points by x and y coordinates.
2Step 2: For each point, union points that share the same x or y coordinate.
3Step 3: For each unique coordinate, calculate the maximum group size and add one for the new point.

solution.py23 lines

1class DSU:
2    def __init__(self):
3        self.parent = {}
4    def find(self, x):
5        if self.parent[x] != x:
6            self.parent[x] = self.find(self.parent[x])
7        return self.parent[x]
8    def union(self, x, y):
9        rootX = self.find(x)
10        rootY = self.find(y)
11        if rootX != rootY:
12            self.parent[rootY] = rootX
13
14points = [[1,1],[1,2],[2,2]]
15dsu = DSU()
16for x, y in points:
17    if x not in dsu.parent:
18        dsu.parent[x] = x
19    if y not in dsu.parent:
20        dsu.parent[y] = y
21    dsu.union(x, y)
22max_points = max(len(set(dsu.find(x) for x, y in points)), len(set(dsu.find(y) for x, y in points))) + 1
23print(max_points

ℹ

Complexity note: The DSU operations are nearly constant time, leading to linear complexity overall.

1Activation spreads through shared coordinates.
2Using DSU efficiently groups points.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.