Maximum Points Inside the Square - Practice Coding Problems

Maximum Points Inside the Square - Problem

You are given a 2D array points where points[i] represents the coordinates of point i, and a string s where s[i] represents the tag of point i.

A valid square is a square that:

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

Return the maximum number of points contained in a valid square.

Note: A point is considered to be inside the square if it lies on or within the square's boundaries. The side length of the square can be zero.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: The square with maximum side length that doesn't contain duplicate tags has size 4 (distance 2 from origin), containing points [2,2] (tag 'a') and [-1,-2] (tag 'b'). Total: 2 points.

Example 2 — All Different Tags

$ Input: points = [[1,1],[-2,-2],[3,-1]], s = "abb"

› Output: 1

💡 Note: The largest valid square can only contain 1 point because tags 'b' appear twice. The square of size 2 (distance 1) contains only [1,1] with tag 'a'.

Example 3 — Single Point

$ Input: points = [[1,1]], s = "a"

› Output: 1

💡 Note: Only one point exists, so the maximum is 1.

Constraints

1 ≤ points.length ≤ 10⁵
points[i].length == 2
-10⁹ ≤ points[i][0], points[i][1] ≤ 10⁹
s.length == points.length
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Points with coordinates and tags

Process

Find largest square without duplicate tags

Output

Maximum number of points in valid square

Key Takeaway

🎯 Key Insight: The problem requires finding the maximum square size where each tag appears at most once

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is to find the largest square centered at origin that contains at most one point of each tag. The optimal approach uses binary search on the answer or sorting by distance for O(n log n) time complexity. Binary search leverages the monotonic property: if a square size is invalid, all larger sizes are also invalid.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(n log n)	O(n)	Binary search on square size to find maximum valid size
Brute Force - Try All Square Sizes	O(n²)	O(n)	Try every possible square size and check validity
Sort by Distance - Incremental Expansion	O(n log n)	O(n)	Sort points by distance, then expand square incrementally

Binary Search on Answer — Algorithm Steps

Step 1: Binary search on possible square sizes
Step 2: For each size, check if square is valid
Step 3: Adjust search range based on validity

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Space

Binary search on sorted distances

Validate Size

Check if square size has duplicate tags

Narrow Range

Update search boundaries

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int max_val(int a, int b) {
    return a > b ? a : b;
}

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

bool isValid(int points[][2], int n, char* s, int maxDist) {
    bool tagsSeen[256] = {false};
    for (int i = 0; i < n; i++) {
        int x = points[i][0], y = points[i][1];
        if (max_val(abs_val(x), abs_val(y)) <= maxDist) {
            if (tagsSeen[(unsigned char)s[i]]) {
                return false;
            }
            tagsSeen[(unsigned char)s[i]] = true;
        }
    }
    return true;
}

int countPoints(int points[][2], int n, int maxDist) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (max_val(abs_val(points[i][0]), abs_val(points[i][1])) <= maxDist) {
            count++;
        }
    }
    return count;
}

int solution(int points[][2], int n, char* s) {
    if (n == 0) return 0;
    
    // Get all unique distances
    int distances[1000];
    int distCount = 0;
    bool seen[10001] = {false};
    
    for (int i = 0; i < n; i++) {
        int dist = max_val(abs_val(points[i][0]), abs_val(points[i][1]));
        if (!seen[dist + 5000]) {
            seen[dist + 5000] = true;
            distances[distCount++] = dist;
        }
    }
    
    qsort(distances, distCount, sizeof(int), compare);
    
    // Binary search on distances
    int left = 0, right = distCount - 1;
    int result = 0;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (isValid(points, n, s, distances[mid])) {
            result = countPoints(points, n, distances[mid]);
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse points array
    int points[1000][2];
    int n = 0;
    char *token = strtok(line, "[],");
    while (token != NULL && n < 1000) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ' ') {
            points[n/2][n%2] = atoi(token);
            n++;
        }
        token = strtok(NULL, "[],");
    }
    n /= 2;
    
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(points, s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Binary search takes O(log n) iterations, each checking O(n) points

⚡ Linearithmic

Space Complexity

O(n)

Store unique distances and hash set for tag validation

⚡ Linearithmic Space

3.4K Views

Medium Frequency

~25 min Avg. Time

89 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler