We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Points Inside the Square

Number: 3419

Difficulty: Medium

Paid? No

Companies: HashedIn

Problem Description

Given an array of 2D points and a string s where each character s[i] is the “tag” of points[i], the task is to choose a square that is centered at the origin and has edges parallel to the axes (the square’s side‐length may be zero) so that the square contains some of these points. A point is “inside” the square if it is on or within its boundaries. However, the square must be “valid” – that is, it must not contain two points with the same tag. Return the maximum number of points that a valid square can cover.

Note that if a point lies exactly on the boundary, it is considered inside the square. The square is completely determined by its side length; since it is centered at the origin, any point (x,y) is inside if max(|x|,|y|) is at most half the side length. In other words, for a given point, we can define a “required half‐length” d = max(|x|,|y|) and a point is included when the half‐side (r) of the square is at least d. However, when two (or more) points have the same required d value, choosing r = d will include them all—so if their tags are not all distinct the square becomes invalid. Because r can be any value, valid squares will exactly “jump” from one threshold to the next in sorted order by d. The challenge is to select a square (i.e. pick the threshold r or, equivalently, the side length L = 2r) that collects a maximal number of points with no tag conflicts.

Key Insights

  • The square centered at (0, 0) with side length L covers all points whose Chebyshev distance max(|x|, |y|) ≤ L/2.
  • For each point, compute its required half-side (d = max(|x|, |y|)). A point is included if r (i.e. L/2) is at least d.
  • Since the square must include all points with d ≤ r, we cannot “choose” individual points from a group; if two points share the exact same d, then choosing r = d forces both to be inside.
  • The problem reduces to sorting points by d and grouping them by their d value. Then, moving in increasing order, we want to form the largest prefix (i.e. all groups with d less than some threshold) such that no tag appears more than once overall.
  • If a group (or the merge with earlier groups) would introduce a duplicate tag, then for any r that would include that group the square becomes invalid. In that case, the best valid square is achieved by taking a threshold just below that group’s d (hence, including only the already processed groups).

Space and Time Complexity

Time Complexity: O(n log n) – dominated by sorting the points. Space Complexity: O(n) – for storing the computed d values, groups, and frequency sets.

Solution

The solution first computes for each point the value d = max(|x|, |y|) which represents the smallest half-side r at which the square will include that point. Next, it sorts the points by d and groups the points that share the same d. For a square with half-side r, all groups with d ≤ r are automatically included. However, because the square must be valid (contain no duplicate tags), we iterate over the groups in increasing order and maintain a set of “used” tags. If a group contains a duplicate internally or if any tag in the current group already exists in the used set, then including that group would invalidate the square. Since r is chosen continuously, we can “choose” a threshold just below the current group to avoid the duplicate. The maximum valid number of points is then the cumulative count from all groups processed before the conflict.

Data structures used: • An array/list to store pairs of (d, tag) for each point. • Grouping by the d value. • A set to keep track of used tags.

The algorithm uses sorting by the computed d values, then iterates through the groups while checking for duplicates across groups, thereby computing the maximum valid “prefix” of groups.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java. Each solution includes line‐by‐line comments.

def maxPointsInsideSquare(points, s):
    # Compute required half-length d for each point (d = max(|x|, |y|))
    pts = []
    for (x, y), tag in zip(points, s):
        d = max(abs(x), abs(y))
        pts.append((d, tag))
    # Sort points by d in ascending order
    pts.sort(key=lambda x: x[0])
    
    # Group points that share the same d value
    groups = []
    current_d = None
    current_group = []
    for d, tag in pts:
        if current_d is None or d != current_d:
            if current_group:
                groups.append((current_d, current_group))
            current_d = d
            current_group = [tag]
        else:
            current_group.append(tag)
    if current_group:
        groups.append((current_d, current_group))
    
    used_tags = set()  # To keep track of tags already included
    cumulative = 0    # Total count of points included so far
    ans = 0         # Maximum valid count found
    for d, group_tags in groups:
        # If the group itself has duplicate tags, it is impossible to add it entirely
        if len(group_tags) != len(set(group_tags)):
            break
        # Check if any tag in the group is already used by previous groups
        conflict = False
        for tag in group_tags:
            if tag in used_tags:
                conflict = True
                break
        if conflict:
            break
        # Add the group's tags to the used set and update cumulative count
        used_tags.update(group_tags)
        cumulative += len(group_tags)
        ans = max(ans, cumulative)
    return ans

# Example usage:
points1 = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]]
s1 = "abdca"
print(maxPointsInsideSquare(points1, s1))  # Expected output: 2

points2 = [[1,1],[-2,-2],[-2,2]]
s2 = "abb"
print(maxPointsInsideSquare(points2, s2))  # Expected output: 1

points3 = [[1,1],[-1,-1],[2,-2]]
s3 = "ccd"
print(maxPointsInsideSquare(points3, s3))  # Expected output: 0
← Back to All Questions