LeetCode 3143 - Maximum Points Inside the Square

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Binary Search, Sorting

Solution

Problem Understanding

The problem asks us to find the maximum number of points that can be contained in a square centered at the origin (0, 0) such that no two points inside the square share the same tag. The square's edges are parallel to the axes, and points on the edges are considered inside. The input consists of a list of points, each represented by [x, y] coordinates, and a string s where s[i] is the tag of the point at points[i]. The output is an integer representing the maximum number of points that can be included in a valid square according to the above constraints.

The constraints tell us that points can have up to 10^5 elements, and coordinates can range from -10^9 to 10^9. Tags are lowercase English letters. Points are distinct, but tags are not necessarily unique. Edge cases include squares that are very small (side length zero), squares that include only one point due to tag conflicts, or points that lie exactly on the edges of the square.

This problem requires careful consideration of both geometry (distance from origin) and tag uniqueness, which immediately suggests that naive brute-force checking of all squares and combinations will be too slow.

Approaches

The brute-force approach would be to consider every possible square by checking all combinations of points to determine the minimum square size that includes those points while ensuring tag uniqueness. For each square, we would count points inside it and update the maximum. This approach is correct but computationally infeasible because it would involve O(n^2) or worse iterations for up to 10^5 points.

The optimal approach leverages two key insights. First, the square is centered at the origin, so its boundaries along the x- and y-axis are determined by the maximum absolute value of the included points' x or y coordinates. Second, to maintain tag uniqueness, we need to track which tags have already been included in a candidate square. Using sorting and a sliding window approach on the maximum coordinate values allows us to efficiently check candidate squares while maintaining the uniqueness constraint.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Check all possible squares formed by pairs of points, counting points inside and ensuring unique tags. Too slow for n = 10^5.
Optimal	O(n log n)	O(n)	Sort points by max(

Algorithm Walkthrough

Transform each point into a "distance metric" d = max(abs(x), abs(y)), representing the minimum half-side of a square centered at origin required to include this point.
Sort points by this distance d in ascending order. This allows us to consider squares from smallest to largest, ensuring we do not miss optimal smaller squares.
Use a sliding window approach with two pointers. The left pointer represents the start of the current candidate square, and the right pointer extends to include more points.
Maintain a hash map or set to track tags currently in the square. If adding a new point would violate tag uniqueness, move the left pointer forward until the duplicate tag is removed.
At each step, calculate the current count of points inside the valid square and update the maximum found so far.
Return the maximum count once all points have been processed.

Why it works: Sorting by maximum coordinate distance ensures we always consider squares that just enclose new points, so we never miss a smaller valid square. The sliding window guarantees tag uniqueness at all times, and the hash map allows constant-time tag checks. This combination ensures correctness while remaining efficient.

Python Solution

from typing import List

class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        # Compute the "distance" metric for each point
        points_with_distance = [(max(abs(x), abs(y)), tag) for (x, y), tag in zip(points, s)]
        points_with_distance.sort()  # sort by distance
        
        left = 0
        max_count = 0
        tag_count = {}
        
        for right in range(len(points_with_distance)):
            dist, tag = points_with_distance[right]
            tag_count[tag] = tag_count.get(tag, 0) + 1
            
            # maintain uniqueness constraint
            while tag_count[tag] > 1:
                _, left_tag = points_with_distance[left]
                tag_count[left_tag] -= 1
                if tag_count[left_tag] == 0:
                    del tag_count[left_tag]
                left += 1
            
            max_count = max(max_count, right - left + 1)
        
        return max_count

The implementation first converts points into a sortable metric d = max(abs(x), abs(y)). Sorting ensures that as we expand the square, all points considered are within or just beyond the current square. The tag_count dictionary maintains the count of each tag in the current window. If a duplicate is found, the window is shrunk from the left until the duplicate is removed, preserving the uniqueness invariant. max_count is updated after each expansion.

Go Solution

func maxPointsInsideSquare(points [][]int, s string) int {
    type point struct {
        dist int
        tag  byte
    }
    
    n := len(points)
    pts := make([]point, n)
    
    for i, p := range points {
        x, y := p[0], p[1]
        d := x
        if x < 0 {
            d = -x
        }
        if y < 0 {
            if -y > d {
                d = -y
            }
        } else if y > d {
            d = y
        }
        pts[i] = point{d, s[i]}
    }
    
    sort.Slice(pts, func(i, j int) bool { return pts[i].dist < pts[j].dist })
    
    left := 0
    maxCount := 0
    tagCount := make(map[byte]int)
    
    for right := 0; right < n; right++ {
        tag := pts[right].tag
        tagCount[tag]++
        
        for tagCount[tag] > 1 {
            tagLeft := pts[left].tag
            tagCount[tagLeft]--
            if tagCount[tagLeft] == 0 {
                delete(tagCount, tagLeft)
            }
            left++
        }
        
        if right-left+1 > maxCount {
            maxCount = right - left + 1
        }
    }
    
    return maxCount
}

In Go, we define a struct point to hold the distance metric and tag. Sorting uses sort.Slice. The map tagCount behaves like Python's dictionary to maintain uniqueness. Go-specific handling includes managing the absolute value computation explicitly and deleting map entries when counts drop to zero.

Worked Examples

Example 1: points = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], s = "abdca"

Point	Distance	Tag
[2,2]	2	a
[-1,-2]	2	b
[-4,4]	4	d
[-3,1]	3	c
[3,-3]	3	a

Sorting by distance: [2,2]->a, [-1,-2]->b, [-3,1]->c, [3,-3]->a, [-4,4]->d

Sliding window process:

Include a and b → window size 2, max_count = 2
Include c → window size 3, max_count = 3
Include next a → duplicate, shrink window → window contains b, c, a → still valid, max_count = 3
Include d → window size exceeds unique tags → adjust window

Final max_count = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting points by distance dominates; sliding window is O(n).
Space	O(n)	Additional array for distances and map for tags.

Sorting ensures we consider squares incrementally by size, and the sliding window ensures we only count unique tags efficiently.

Test Cases

# Provided examples
assert Solution().maxPointsInsideSquare([[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], "abdca") == 2  # Example 1
assert Solution().maxPointsInsideSquare([[1,1],[-2,-2],[-2,2]], "abb") == 1  # Example 2
assert Solution().maxPointsInsideSquare([[1,1],[-1,-1],[2,-2]], "ccd") == 0  # Example 3

# Edge cases
assert Solution().maxPointsInsideSquare([[0,0]], "a") == 1  # Single point at origin
assert Solution().maxPointsInsideSquare([[1,1],[-1,-1]], "aa") == 1  # Duplicate tags, can only pick one
assert Solution().maxPointsInsideSquare([[1,2],[2,1],[3,3]], "abc") == 3  # All unique tags

Test	Why