Problem Description

You have a 2D array points where each points[i] represents the coordinates [x, y] of point i, and a string s where s[i] represents the tag (label) of point i.

The task is to find a square that:

• Is centered at the origin (0, 0)
• Has edges parallel to the x and y axes
• Does not contain two points with the same tag

You need to return the maximum number of points that can be contained in such a valid square.

Key rules:

• A point is inside the square if it lies on or within the square's boundaries
• The square's side length can be zero (meaning it could just be a single point at the origin)
• The square must be "valid" - it cannot contain two points that share the same tag

For example, if you have points at (1, 2) with tag 'a', (2, 1) with tag 'b', and (3, 3) with tag 'a', a square with side length 4 (extending from -2 to 2 on both axes) would only contain the first two points. If we tried to make the square larger to include the third point, it would contain two points with tag 'a', making it invalid.

The goal is to find the size of the square that maximizes the number of points while maintaining validity (no duplicate tags).

Intuition

Since the square is centered at the origin and has edges parallel to the axes, we can think of it as extending equally in all four directions. For a square with side length 2d, it extends from -d to d on both the x and y axes.

The key insight is that for any point (x, y) to be inside this square, both |x| and |y| must be at most d. This means the point's distance from the origin (in terms of the square's boundaries) is determined by max(|x|, |y|). This value tells us the minimum half-side length needed for a square to contain that point.

Instead of trying different square sizes, we can group points by their required minimum square size. Points with max(|x|, |y|) = 3 need a square with half-side length at least 3, while points with max(|x|, |y|) = 5 need at least 5.

By sorting these groups in ascending order of their required square size, we can gradually "expand" our square from the origin outward. As we expand to each new size, we include all points at that distance. We keep track of which tags we've already seen - if we encounter a duplicate tag while expanding, we know we can't make the square any larger without violating the "no duplicate tags" constraint.

This greedy approach works because once we encounter a duplicate tag at distance d, any larger square would also contain this duplicate, making it invalid. Therefore, the maximum valid square is the one just before we encounter the first duplicate tag.

Learn more about Binary Search and Sorting patterns.

Solution Approach

The implementation uses a hash table and sorting to efficiently find the maximum valid square:

1. Group points by distance: Create a hash table g where the key is the distance d = max(|x|, |y|) and the value is a list of indices of points at that distance. This effectively groups points by the minimum square size needed to contain them.

2. Process points in order: Sort the keys of the hash table (the distances) in ascending order. This allows us to simulate expanding the square from the origin outward.

3. Track used tags: Use a set vis to keep track of which tags have already been included in our current square.

4. Expand and validate: For each distance d in sorted order:

   • Get all point indices at this distance from g[d]
   • For each point at this distance:
     • Check if its tag s[i] is already in vis
     • If yes, we've found a duplicate tag - return the current answer immediately
     • If no, add the tag to vis
   • If all points at this distance are valid, add their count to the answer

5. Return result: If we process all distances without finding duplicates, return the total count.

The algorithm's efficiency comes from:

• Mapping each point (x, y) to its minimum required square size using max(|x|, |y|) in O(1) time
• Grouping points by distance to avoid checking unnecessary points
• Early termination when the first duplicate tag is found
• Using a set for O(1) tag lookup

This greedy approach guarantees the maximum number of points because we always try to include points closest to the origin first, and stop as soon as including more points would violate the constraint.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input:

• points = [[1,1], [-2,2], [3,1], [0,1], [2,2]]
• s = "abcda"

Step 1: Calculate distances and group points

For each point, calculate d = max(|x|, |y|):

• Point 0: [1,1] → d = max(1,1) = 1, tag = 'a'
• Point 1: [-2,2] → d = max(2,2) = 2, tag = 'b'
• Point 2: [3,1] → d = max(3,1) = 3, tag = 'c'
• Point 3: [0,1] → d = max(0,1) = 1, tag = 'd'
• Point 4: [2,2] → d = max(2,2) = 2, tag = 'a'

Group by distance:

• Distance 1: points [0, 3] with tags ['a', 'd']
• Distance 2: points [1, 4] with tags ['b', 'a']
• Distance 3: points [2] with tag ['c']

Step 2: Process distances in ascending order

Initialize: vis = {} (empty set), answer = 0

Distance 1:

• Process point 0 (tag 'a'): Not in vis, add 'a' to vis = {'a'}
• Process point 3 (tag 'd'): Not in vis, add 'd' to vis = {'a', 'd'}
• Both points valid, answer = 2

Distance 2:

• Process point 1 (tag 'b'): Not in vis, add 'b' to vis = {'a', 'd', 'b'}
• Process point 4 (tag 'a'): 'a' is already in vis!
• Found duplicate tag, stop immediately

Result: Return answer = 3

The maximum valid square has half-side length between 1 and 2 (specifically, it needs to be at least 1 but less than 2 to exclude point 4). This square contains 3 points: [1,1], [0,1], and [-2,2] with tags 'a', 'd', and 'b' respectively, with no duplicate tags.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is determined by the following operations:

• Creating the dictionary g by iterating through all points: O(n), where each point calculation max(abs(x), abs(y)) takes O(1) time
• Sorting the keys of dictionary g: O(k × log k), where k is the number of unique distances. In the worst case, k = n (all points have different distances), so this becomes O(n × log n)
• Iterating through the sorted distances and checking each point: O(n) total, as each point is visited exactly once

The dominant operation is the sorting step, giving us an overall time complexity of O(n × log n).

Space Complexity: O(n)

The space complexity comes from:

• Dictionary g storing all point indices grouped by distance: O(n) in total, as it stores n indices across all distance groups
• Set vis storing unique characters: O(min(n, 26)) = O(1) for lowercase English letters, or O(n) in the general case
• The sorted list of keys: O(k) where k ≤ n, so O(n) in the worst case

The overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding Distance Calculation

Issue: Using Euclidean distance sqrt(x² + y²) instead of Chebyshev distance max(|x|, |y|).

Since the square has edges parallel to the axes and is centered at the origin, a point (x, y) requires a square with side length 2 * max(|x|, |y|) to be contained. Using Euclidean distance would incorrectly determine which points can fit in the same square.

Example: Point (3, 1) requires a square extending from -3 to 3 (side length 6), not based on sqrt(10).

Solution:

# Correct: Chebyshev distance
distance = max(abs(x), abs(y))

# Incorrect: Euclidean distance
# distance = math.sqrt(x**2 + y**2)

Pitfall 2: Including Points at Invalid Distance Level

Issue: Adding all points at the current distance to the answer before checking if they create tag conflicts.

The algorithm must check ALL points at the same distance for tag conflicts BEFORE adding any of them to the result. If any point at distance d has a duplicate tag, NO points at distance d should be included.

Incorrect approach:

for distance in sorted(distance_to_indices.keys()):
    for index in distance_to_indices[distance]:
        tag = s[index]
        if tag in used_tags:
            return total_points
        used_tags.add(tag)
        total_points += 1  # Wrong: incrementing immediately

Correct approach:

for distance in sorted(distance_to_indices.keys()):
    # First check ALL points at this distance
    for index in distance_to_indices[distance]:
        tag = s[index]
        if tag in used_tags:
            return total_points  # Don't include ANY points at this distance
        used_tags.add(tag)
  
    # Only increment after confirming all points are valid
    total_points += len(distance_to_indices[distance])

Pitfall 3: Not Handling Edge Cases

Issue: Forgetting to handle special cases like empty input or single point at origin.

Solution: The current implementation handles these naturally:

• Empty points array returns 0
• Single point works correctly
• Point at origin (0, 0) has distance 0 and is handled properly

Pitfall 4: Using Wrong Data Structure for Tag Tracking

Issue: Using a list instead of a set for used_tags, leading to O(n) lookup time instead of O(1).

Solution: Always use a set for membership checking:

used_tags = set()  # O(1) lookup
# Not: used_tags = []  # O(n) lookup