You are given a 2D array points and a string s where, points[i] represents the coordinates of point i, and s[i] represents the tag of point i.
A valid square is a square centered at the origin (0, 0), has edges parallel to the axes, and does not contain two points with the same tag.
Return the maximum number of points contained in a valid square.
Note:
Example 1:
Input: points = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], s = "abdca"
Output: 2
Explanation:
The square of side length 4 covers two points points[0] and points[1].
Example 2:
Input: points = [[1,1],[-2,-2],[-2,2]], s = "abb"
Output: 1
Explanation:
The square of side length 2 covers one point, which is points[0].
Example 3:
Input: points = [[1,1],[-1,-1],[2,-2]], s = "ccd"
Output: 0
Explanation:
It's impossible to make any valid squares centered at the origin such that it covers only one point among points[0] and points[1].
Constraints:
1 <= s.length, points.length <= 105points[i].length == 2-109 <= points[i][0], points[i][1] <= 109s.length == points.lengthpoints consists of distinct coordinates.s consists only of lowercase English letters.Problem Overview: You are given 2D points and a string where each character labels a point. The square is centered at the origin and grows equally in all directions. Count the maximum number of points that can lie inside the square such that no two included points share the same label.
Approach 1: Dynamic Programming with Distance Tracking (O(n) time, O(k) space)
Each point enters the square when the side length reaches max(|x|, |y|), which is the Chebyshev distance from the origin. Compute this distance for every point. Maintain a hash structure that stores the smallest distance seen for each label. If the same label appears again, the square cannot grow beyond the larger of the two distances without including duplicates. Track the minimum such "bad" distance. Finally, count how many points have distance strictly smaller than that limit. This approach relies heavily on hash table lookups and linear scanning of the array of points.
Approach 2: Greedy with Sorting (O(n log n) time, O(n) space)
Compute the Chebyshev distance for every point and pair it with its label. Sort the points by distance so they enter the square in order of expansion. Iterate through the sorted list while keeping a set of used labels. If the current label has not appeared, add it and continue expanding the square. The moment a duplicate label appears, the square cannot include that point or any point farther away. The answer is the number of points processed before this conflict. This greedy reasoning works because the square grows monotonically, and sorted order guarantees earlier points are always closer. Sorting can be implemented using standard sorting algorithms available in most languages.
Recommended for interviews: The greedy + sorting approach is the one most interviewers expect. It shows that you recognized the geometric constraint (max(|x|, |y|)) and transformed the problem into an ordered expansion of the square. A brute-force expansion would be inefficient, while the greedy ordering gives a clear O(n log n) solution. The hash-based distance tracking optimization improves it further to O(n) by avoiding sorting once you understand the constraint.
The C solution uses an array to store results of subproblems. We iterate over the array and apply a recurring relation to fill it up. Once the array is filled, the final element contains the answer.
Time Complexity: O(n) since we iterate through a loop n times.
Space Complexity: O(n) because we store n results in the dp array.
In this C solution, we iterate through decisions based on the simplest immediate choice which would ideally derive the globally optimal solution for the situation.
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(n) since we iterate through a loop n times. |
| Greedy Algorithm | Time Complexity: O(n) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming / Distance Tracking | O(n) | O(k) | Best when you want the optimal linear solution using label distance tracking. |
| Greedy with Sorting | O(n log n) | O(n) | Good for interviews when reasoning about expanding squares and ordered points. |
3143. Maximum Points Inside the Square | Binary Search | Sorting | O(n) time • Aryan Mittal • 4,096 views views
Watch 6 more video solutions →Practice Maximum Points Inside the Square with our built-in code editor and test cases.
Practice on FleetCode