Skip to content

3143. Maximum Points Inside the Square 👍

  • Time: $O(n)$
  • Space: $O(26) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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; });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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())