3143. Maximum Points Inside the Square LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3143. Maximum Points Inside the Square LeetCode Solution with the best time and space complexity. The solution to Maximum Points Inside the Square problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Points Inside the Square solution in C++
Maximum Points Inside the Square solution in Java
Maximum Points Inside the Square solution in Python
Additional Resources

3143. Maximum Points Inside the Square LeetCode Solution image

Problem Statement of Maximum Points Inside the Square

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.

Complexity Analysis

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

3143. Maximum Points Inside the Square LeetCode Solution in C++

class Solution {
 public:
  int maxPointsInsideSquare(vector<vector<int>>& points, string s) {
    int secondMinSize = INT_MAX;
    vector<int> minSizes(26, INT_MAX);

    for (int i = 0; i < points.size(); ++i) {
      const int x = points[i][0];
      const int y = points[i][1];
      const int sz = max(abs(x), abs(y));
      const int j = s[i] - 'a';
      if (minSizes[j] == INT_MAX) {
        minSizes[j] = sz;
      } else if (sz < minSizes[j]) {
        // This is because minSizes[j] is about to be replaced by a smaller
        // value, so it becomes a candidate for the second minimum size.
        secondMinSize = min(secondMinSize, minSizes[j]);
        minSizes[j] = sz;
      } else {
        // `sz` is not smaller than the current minimum size, but it could be
        // smaller than the current second minimum size.
        secondMinSize = min(secondMinSize, sz);
      }
    }

    return ranges::count_if(minSizes,
                            [&](int sz) { return sz < secondMinSize; });
  }
};
/* code provided by PROGIEZ */

3143. Maximum Points Inside the Square LeetCode Solution in Java

class Solution {
  public int maxPointsInsideSquare(int[][] points, String s) {
    int secondMinSize = Integer.MAX_VALUE;
    int[] minSizes = new int[26];
    Arrays.fill(minSizes, Integer.MAX_VALUE);

    for (int i = 0; i < points.length; ++i) {
      final int x = points[i][0];
      final int y = points[i][1];
      final int sz = Math.max(Math.abs(x), Math.abs(y));
      final int j = s.charAt(i) - 'a';
      if (minSizes[j] == Integer.MAX_VALUE) {
        minSizes[j] = sz;
      } else if (sz < minSizes[j]) {
        // This is because minSizes[j] is about to be replaced by a smaller
        // value, so it becomes a candidate for the second minimum size.
        secondMinSize = Math.min(secondMinSize, minSizes[j]);
        minSizes[j] = sz;
      } else {
        // `sz` is not smaller than the current minimum size, but it could be
        // smaller than the current second minimum size.
        secondMinSize = Math.min(secondMinSize, sz);
      }
    }

    final int finalSecondMinSize = secondMinSize;
    return (int) Arrays.stream(minSizes).filter(sz -> sz < finalSecondMinSize).count();
  }
}
// code provided by PROGIEZ

3143. Maximum Points Inside the Square LeetCode Solution in Python

class Solution:
  def maxPointsInsideSquare(self, points: list[list[int]], s: str) -> int:
    secondMinSize = math.inf
    minSizes = {}

    for (x, y), c in zip(points, s):
      sz = max(abs(x), abs(y))
      if c not in minSizes:
        minSizes[c] = sz
      elif sz < minSizes[c]:
        # This is because minSizes[j] is about to be replaced by a smaller
        # value, so it becomes a candidate for the second minimum size.
        secondMinSize = min(secondMinSize, minSizes[c])
        minSizes[c] = sz
      else:
        # `sz` is not smaller than the current minimum size, but it could be
        # smaller than the current second minimum size.
        secondMinSize = min(secondMinSize, sz)

    return sum(sz < secondMinSize for sz in minSizes.values())
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents