Skip to main content
Talentd

Maximum Points Inside the Square - Solution & Explanation

MediumArrayHash TableStringBinary Search15 min readAsked at: Hashedin
Practice this problem

Problem Statement

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.

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.

 

Example 1:

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

Output: 2

Explanation:

The square of side length 4 covers two points points[0] and points[1].

Example 2:

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

Output: 1

Explanation:

The square of side length 2 covers one point, which is points[0].

Example 3:

Input: points = [[1,1],[-1,-1],[2,-2]], s = "ccd"

Output: 0

Explanation:

It's impossible to make any valid squares centered at the origin such that it covers only one point among points[0] and points[1].

 

Constraints:

  • 1 <= s.length, points.length <= 105
  • points[i].length == 2
  • -109 <= points[i][0], points[i][1] <= 109
  • s.length == points.length
  • points consists of distinct coordinates.
  • s consists only of lowercase English letters.

Approach Overview

Problem Overview: You are given 2D points and a string where each character labels a point. The square is centered at the origin and grows equally in all directions. Count the maximum number of points that can lie inside the square such that no two included points share the same label.

Approach 1: Dynamic Programming with Distance Tracking (O(n) time, O(k) space)

Each point enters the square when the side length reaches max(|x|, |y|), which is the Chebyshev distance from the origin. Compute this distance for every point. Maintain a hash structure that stores the smallest distance seen for each label. If the same label appears again, the square cannot grow beyond the larger of the two distances without including duplicates. Track the minimum such "bad" distance. Finally, count how many points have distance strictly smaller than that limit. This approach relies heavily on hash table lookups and linear scanning of the array of points.

Approach 2: Greedy with Sorting (O(n log n) time, O(n) space)

Compute the Chebyshev distance for every point and pair it with its label. Sort the points by distance so they enter the square in order of expansion. Iterate through the sorted list while keeping a set of used labels. If the current label has not appeared, add it and continue expanding the square. The moment a duplicate label appears, the square cannot include that point or any point farther away. The answer is the number of points processed before this conflict. This greedy reasoning works because the square grows monotonically, and sorted order guarantees earlier points are always closer. Sorting can be implemented using standard sorting algorithms available in most languages.

Recommended for interviews: The greedy + sorting approach is the one most interviewers expect. It shows that you recognized the geometric constraint (max(|x|, |y|)) and transformed the problem into an ordered expansion of the square. A brute-force expansion would be inefficient, while the greedy ordering gives a clear O(n log n) solution. The hash-based distance tracking optimization improves it further to O(n) by avoiding sorting once you understand the constraint.

Approach 1: Dynamic Programming

This approach utilizes dynamic programming to store and reuse solutions to subproblems, providing an optimized and efficient solution to the problem. We'll create a table to hold the results of subproblems and fill this table iteratively based on the relationships between them.

The C solution uses an array to store results of subproblems. We iterate over the array and apply a recurring relation to fill it up. Once the array is filled, the final element contains the answer.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) since we iterate through a loop n times.
Space Complexity: O(n) because we store n results in the dp array.

Try this approach in the editor →

Approach 2: Greedy Algorithm

This approach uses a greedy strategy, making a series of choices that are locally optimal, as each step appears to be the best decision one can make at that moment with the hope of finding a global optimum.

In this C solution, we iterate through decisions based on the simplest immediate choice which would ideally derive the globally optimal solution for the situation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

Approach 3: Hash Table + Sorting

For a point (x, y), we can map it to the first quadrant with the origin as the center, i.e., (max(|x|, |y|), max(|x|, |y|)). In this way, we can map all points to the first quadrant and then sort them according to the distance from the point to the origin.

We can use a hash table g to store the distance from all points to the origin, and then sort them according to the distance. For each distance d, we put all points with a distance of d together, and then traverse these points. If there are two points with the same label, then this square is illegal, and we directly return the answer. Otherwise, we add these points to the answer.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the number of points.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming

Time Complexity: O(n) since we iterate through a loop n times.
Space Complexity: O(n) because we store n results in the dp array.

Greedy Algorithm

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

Hash Table + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming / Distance TrackingO(n)O(k)Best when you want the optimal linear solution using label distance tracking.
Greedy with SortingO(n log n)O(n)Good for interviews when reasoning about expanding squares and ordered points.

Video Solution

3143. Maximum Points Inside the Square | Binary Search | Sorting | O(n) time • Aryan Mittal • 4,178 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Maximum Points Inside the Square easy or hard?
Maximum Points Inside the Square is rated Medium difficulty. The challenge comes from recognizing the Chebyshev distance that defines when a point enters the square and handling duplicate labels efficiently using hashing or greedy ordering.
Maximum Points Inside the Square Python/Java solution
Both Python and Java implementations follow the same logic: compute max(|x|, |y|) for each point, track the earliest distance for every label, detect duplicate conflicts, and count points with distance below the conflict threshold. The algorithm remains O(n) in optimized implementations.
How to solve Maximum Points Inside the Square in O(n)?
Compute the Chebyshev distance max(|x|, |y|) for every point and store the smallest distance for each label. When the same label appears again, record the minimum distance where the conflict occurs. After scanning all points, count how many have distance smaller than that limit. This avoids sorting and achieves O(n) time.
What is the best approach for Maximum Points Inside the Square?
The optimal approach tracks the Chebyshev distance max(|x|, |y|) for each point and records the first occurrence of each label. When a duplicate label appears, the square cannot grow beyond the conflicting distance. This method runs in O(n) time with O(k) space where k is the number of unique labels.
Is Maximum Points Inside the Square asked at Google/Amazon/Meta?
Problems involving geometric constraints, hashing, and greedy expansion patterns commonly appear in interviews at companies like Amazon, Google, and Meta. Variants that combine coordinate geometry with hash sets or sorting are particularly common in coding interviews.
What data structure is used in Maximum Points Inside the Square?
The main data structure is a hash table that maps each label to its first encountered distance from the origin. Arrays store the points and computed distances, while some implementations also use sorting to process points in increasing distance order.
What is the time complexity of Maximum Points Inside the Square?
The optimized hash-based distance tracking solution runs in O(n) time because each point is processed once and label lookups are constant time. A simpler greedy approach that sorts points by distance runs in O(n log n) due to the sorting step.

Ready to solve this problem?

Practice Maximum Points Inside the Square with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximize the Distance Between Points on a Square