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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Points Inside the Square

Difficulty: Medium

Problem Description

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.

Key Insights

  • A square is valid if it contains points with unique tags.
  • The side length of the square can be adjusted to maximize the number of points contained within it.
  • The distance from the origin to the corners of the square determines which points can be included.
  • Using a hash table can help efficiently track unique tags within the square.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

To solve the problem, we can use the following approach:

  1. Sort the Points: Start by sorting the points based on their distance from the origin. The distance can be calculated using the formula distance = x^2 + y^2 (we use squared distance to avoid floating-point inaccuracies).

  2. Use a Sliding Window: Implement a sliding window technique to explore possible valid squares of varying side lengths. For each potential side length, check how many points fall within the square.

  3. Track Unique Tags: Maintain a hash table to track tags of the points within the current window. If a point's tag is already present, remove points from the beginning of the window until the tags are unique again.

  4. Update Maximum Count: Throughout the process, update the maximum count of points found within the valid square.

Code Solutions

def maxPoints(points, s):
    from collections import defaultdict
    
    # Calculate the distances and pair them with their tags
    distances = [(x * x + y * y, s[i]) for i, (x, y) in enumerate(points)]
    distances.sort()  # Sort by distances
    
    max_count = 0
    left = 0
    tag_count = defaultdict(int)
    
    for right in range(len(distances)):
        tag_count[distances[right][1]] += 1
        
        # If we have duplicate tags, move the left pointer
        while tag_count[distances[right][1]] > 1:
            tag_count[distances[left][1]] -= 1
            if tag_count[distances[left][1]] == 0:
                del tag_count[distances[left][1]]
            left += 1
            
        # Update the maximum count of unique tags in the current window
        max_count = max(max_count, right - left + 1)
    
    return max_count
← Back to All Questions