Maximum points inside the square

Array Hash Table String Binary Search Sorting

39.2% acceptance

Feb 24, 2026

170

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_points_inside_square(points: Vec<Vec<i32>>, s: String) -> i32 {
    let tags: Vec<u8> = s.bytes().collect();
    let n = points.len();
    // Chebyshev distance = max(|x|, |y|) = half-side-length needed to include this point
    let mut pts: Vec<(i32, u8)> = (0..n)
      .map(|i| (points[i][0].abs().max(points[i][1].abs()), tags[i]))
      .collect();
    pts.sort_unstable();

    let mut seen = [false; 26];
    let mut count = 0i32;
    let mut i = 0;
    while i < pts.len() {
      let key = pts[i].0;
      let mut j = i;
      let mut group = [false; 26];
      let mut ok = true;
      while j < pts.len() && pts[j].0 == key {
        let t = (pts[j].1 - b'a') as usize;
        if seen[t] || group[t] {
          ok = false;
        }
        group[t] = true;
        j += 1;
      }
      if !ok {
        break;
      }
      for t in 0..26 {
        if group[t] {
          seen[t] = true;
        }
      }
      count += (j - i) as i32;
      i = j;
    }
    count
  }
}