# Maximum Points Inside the Square
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-points-inside-the-square)
Canonical: https://scaleengineer.com/dsa/problems/maximum-points-inside-the-square
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
**Companies:** [HashedIn](https://scaleengineer.com/companies/hashedin)
---
## Problem
You are given a 2Darray `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:**

![](https://assets.glich.co/dsa/maximum-points-inside-the-square/image0.png)

**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:**

![](https://assets.glich.co/dsa/maximum-points-inside-the-square/image1.png)

**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.

# Approaches
## Sort by Distance and Iterate
This approach calculates the effective distance of each point from the origin, which determines when it gets included in an expanding square. By sorting all points based on this distance, we can simulate the process of expanding the square and find the first moment a duplicate tag is introduced. The number of points included just before this collision is the answer.
**Time:** O(N log N), where N is the number of points. The dominant operation is sorting the `N` points based on their distance. The subsequent iteration is O(N). · **Space:** O(N) to store the list of point information (distance and tag) for sorting.
**Pros:** Conceptually straightforward simulation of an expanding square.; Correctly handles cases with multiple points at the same distance from the origin.
**Cons:** The O(N log N) time complexity from sorting can be suboptimal for very large inputs if a linear time solution exists.
### Explanation
For a point `(x, y)`, the smallest square centered at the origin that contains it has a half-side length of `max(|x|, |y|)`. Let's call this the point's "distance". The core idea is that as we increase the square's size, points are included in increasing order of their "distance". A square becomes invalid as soon as we include a point that has the same tag as a point already inside the square.

The algorithm proceeds as follows:
1. Create a list of objects or pairs, where each element contains the calculated "distance" for a point and its corresponding tag.
2. Sort this list in ascending order based on the distances. Points with the same distance can be ordered arbitrarily among themselves.
3. Iterate through the sorted list, processing points with the same distance as a single group.
4. Maintain a set of tags of points that are already included in our valid square (`seen_tags`).
5. For each group of points with the same distance `d`:
    a. First, check for duplicate tags within the group itself. If found, a square of half-side `d` is invalid. The answer is the number of points processed so far.
    b. Next, check if any tag in the current group is already present in `seen_tags`. If so, this also makes the square of half-side `d` invalid. The answer is the number of points processed so far.
    c. If the group is valid, add all its tags to `seen_tags` and add the group's size to the total count of points.
6. If the loop completes without finding any collisions, it means all `N` points can form a valid set. The answer is `N`.

This method correctly identifies the largest set of points that can be contained in a valid square by finding the critical distance at which a collision first occurs.

```java
class PointInfo {
    int dist;
    char tag;
    PointInfo(int dist, char tag) {
        this.dist = dist;
        this.tag = tag;
    }
}

public int maxPointsInsideSquare(int[][] points, String s) {
    int n = points.length;
    List<PointInfo> pointInfos = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        int dist = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
        pointInfos.add(new PointInfo(dist, s.charAt(i)));
    }

    Collections.sort(pointInfos, Comparator.comparingInt(p -> p.dist));

    Set<Character> seenTags = new HashSet<>();
    int count = 0;
    int i = 0;
    while (i < n) {
        int currentDist = pointInfos.get(i).dist;
        int j = i;
        // Find the end of the block with the same distance
        while (j < n && pointInfos.get(j).dist == currentDist) {
            j++;
        }

        // Process the block from i to j-1
        Set<Character> blockTags = new HashSet<>();
        for (int k = i; k < j; k++) {
            char tag = pointInfos.get(k).tag;
            // Check for collision within the block or with previously seen tags
            if (blockTags.contains(tag) || seenTags.contains(tag)) {
                return count;
            }
            blockTags.add(tag);
        }

        // No collision, add block tags to seen tags and update count
        seenTags.addAll(blockTags);
        count += (j - i);
        i = j;
    }

    return count;
}
```
### Algorithm
- Calculate `dist(i) = max(|points[i][0]|, |points[i][1]|)` for each point `i`.
- Create a list of pairs `(dist(i), s[i])`.
- Sort the list based on `dist(i)`.
- Initialize `count = 0` and an empty set `seen_tags`.
- Iterate through the sorted list, processing points with the same distance in groups.
- For each group, check for tag collisions within the group and with `seen_tags`.
- If a collision is found, return the current `count`.
- Otherwise, add the group's tags to `seen_tags`, update `count`, and proceed to the next group.
- If the loop finishes, return the total number of points.

## Group by Tag to Find Collision Limit
This approach focuses on directly finding the maximum possible size of a valid square. A square becomes invalid if it contains two points with the same tag. For each tag, the critical event is when the *second* point with that tag enters the square. The smallest of these critical distances over all tags determines the maximum size for *any* valid square.
**Time:** O(N + sum(n_c log n_c)), where `n_c` is the number of points with tag `c`. In the worst case (all points have the same tag), this is O(N log N). On average, it might be faster than O(N log N). · **Space:** O(N) to store the map where the total number of elements across all lists is N.
**Pros:** More direct than simulating the square's expansion.; Can be more efficient than the general sorting approach if the number of points per tag is small, as `sum(n_c log n_c)` can be less than `N log N`.
**Cons:** Worst-case time complexity is still O(N log N) if all points share the same tag.; Requires O(N) extra space for the map and lists.
### Explanation
The largest valid square is limited by the first tag collision. A collision for a tag `c` occurs when a square expands enough to include the second-closest point with tag `c`.
Let `dist(i) = max(|points[i][0]|, |points[i][1]|)`. For each tag `c`, if there are points `p_{c,1}, p_{c,2}, ...` with this tag, their distances are `d_{c,1}, d_{c,2}, ...`. If we sort these distances as `d'_{c,1} <= d'_{c,2} <= ...`, a square with half-side `r >= d'_{c,2}` will contain at least two points with tag `c` and will be invalid.
Therefore, the maximum half-side length for a valid square, let's call it `limit`, must be strictly less than the minimum of all `d'_{c,2}` values.

The algorithm is:
1. Group points by their tags. A `Map<Character, List<Integer>>` can be used to store the distances for each tag.
2. Iterate through all points, calculate their `dist`, and add it to the list corresponding to their tag in the map.
3. Initialize a `limit` variable to infinity.
4. Iterate through the map. For each tag that has two or more points:
    a. Sort the list of distances.
    b. The second element in the sorted list, `dists.get(1)`, is the collision distance for this tag.
    c. Update `limit = min(limit, dists.get(1))`.
5. Once the `limit` is found, the final step is to count how many points have a distance strictly less than this `limit`. Iterate through all points one last time, and if `dist(i) < limit`, increment a counter.
6. Return the final count. If no tag appears more than once, the `limit` remains infinity, and all points are counted.

```java
public int maxPointsInsideSquare(int[][] points, String s) {
    int n = points.length;
    Map<Character, List<Integer>> tagDists = new HashMap<>();
    for (int i = 0; i < n; i++) {
        int dist = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
        char tag = s.charAt(i);
        tagDists.computeIfAbsent(tag, k -> new ArrayList<>()).add(dist);
    }

    int limit = Integer.MAX_VALUE;
    for (List<Integer> dists : tagDists.values()) {
        if (dists.size() >= 2) {
            Collections.sort(dists);
            limit = Math.min(limit, dists.get(1));
        }
    }

    if (limit == Integer.MAX_VALUE) {
        return n;
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        int dist = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
        if (dist < limit) {
            count++;
        }
    }
    return count;
}
```
### Algorithm
- Create a map from tags to a list of distances.
- Populate the map by iterating through all points, calculating their distance, and adding it to the list for their tag.
- Initialize `limit = infinity`.
- For each tag with at least two points, sort its distance list and update `limit` with the second smallest distance.
- Initialize `count = 0`.
- Iterate through all points again. If a point's distance is less than `limit`, increment `count`.
- Return `count`.

## Optimal Linear Time Solution
This approach improves upon the previous one by avoiding the costly sorting step. Instead of collecting all distances for a tag and then sorting, we can find the two smallest distances for each tag in a single pass. This allows us to determine the collision limit in linear time.
**Time:** O(N), as we iterate through the points a constant number of times. · **Space:** O(N) to store the pre-calculated distances. The space for tracking minimums per tag is O(1) as the alphabet size is constant. If we re-calculate distances in the final counting loop, space complexity can be reduced to O(1).
**Pros:** Most efficient solution with linear time complexity.; Avoids comparison-based sorting.
**Cons:** Requires an extra pass or extra O(N) space to get the final count after determining the limit.
### Explanation
The key insight is that to find the collision distance for a tag, we only need its two smallest distances from the origin, not the entire sorted list of distances. We can find these two minimums efficiently.

The algorithm is as follows:
1. We use a data structure to keep track of the two smallest distances found so far for each of the 26 possible tags. An array of pairs or a map `Map<Character, int[]>` where `int[]` is of size 2, `[min1, min2]`, would work. Initialize all distances to infinity.
2. Iterate through all `N` points once. For each point `i`:
    a. Calculate its distance `d = max(|points[i][0]|, |points[i][1]|)`.
    b. Get its tag `c = s.charAt(i)`.
    c. Retrieve the current two minimums for tag `c`, `[min1, min2]`.
    d. If `d < min1`, it's the new smallest, so we update `min2 = min1` and `min1 = d`.
    e. Else if `d < min2`, it's the new second-smallest, so we update `min2 = d`.
3. After this single pass, we have the two smallest distances for every tag.
4. Now, find the overall collision `limit`. Initialize `limit = infinity`. Iterate through the 26 tags. The collision distance for a tag is its `min2`. Update `limit = min(limit, min2)` for each tag.
5. Finally, count the number of points inside the largest valid square. This is the number of points `i` whose distance `dist(i)` is strictly less than the calculated `limit`. This can be done by iterating through the points again. To avoid re-calculating distances, we can store them in an array during the first pass.

This approach processes each point a constant number of times, leading to a linear time solution.

```java
public int maxPointsInsideSquare(int[][] points, String s) {
    int n = points.length;
    // min1[c], min2[c] store the two smallest distances for tag c
    int[] min1 = new int[26];
    int[] min2 = new int[26];
    Arrays.fill(min1, Integer.MAX_VALUE);
    Arrays.fill(min2, Integer.MAX_VALUE);

    int[] dists = new int[n];

    for (int i = 0; i < n; i++) {
        int dist = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
        dists[i] = dist;
        int tagIndex = s.charAt(i) - 'a';

        if (dist < min1[tagIndex]) {
            min2[tagIndex] = min1[tagIndex];
            min1[tagIndex] = dist;
        } else if (dist < min2[tagIndex]) {
            min2[tagIndex] = dist;
        }
    }

    int limit = Integer.MAX_VALUE;
    for (int i = 0; i < 26; i++) {
        // min2 is the collision distance for this tag
        limit = Math.min(limit, min2[i]);
    }

    if (limit == Integer.MAX_VALUE) {
        return n;
    }

    int count = 0;
    for (int dist : dists) {
        if (dist < limit) {
            count++;
        }
    }
    return count;
}
```
### Algorithm
- Create two arrays, `min1` and `min2`, of size 26, initialized to infinity.
- Create an array `dists` of size `N` to store calculated distances.
- Iterate through the `N` points. For each point:
    - Calculate its distance `d`. Store it in `dists`.
    - Update the `min1` and `min2` arrays for the point's tag based on `d`.
- Initialize `limit = infinity`.
- Find the minimum of all values in the `min2` array. This is the `limit`.
- Count how many values in the `dists` array are less than `limit`.
- Return the count.

# Solutions
### Java

```java
class Solution {
public
  int maxPointsInsideSquare(int[][] points, String s) {
    TreeMap<Integer, List<Integer>> g = new TreeMap<>();
    for (int i = 0; i < points.length; ++i) {
      int x = points[i][0], y = points[i][1];
      int key = Math.max(Math.abs(x), Math.abs(y));
      g.computeIfAbsent(key, k->new ArrayList<>()).add(i);
    }
    boolean[] vis = new boolean[26];
    int ans = 0;
    for (var idx : g.values()) {
      for (int i : idx) {
        int j = s.charAt(i) - 'a';
        if (vis[j]) {
          return ans;
        }
        vis[j] = true;
      }
      ans += idx.size();
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxPointsInsideSquare(vector<vector<int>> &points, string s) {
    map<int, vector<int>> g;
    for (int i = 0; i < points.size(); ++i) {
      auto &p = points[i];
      int key = max(abs(p[0]), abs(p[1]));
      g[key].push_back(i);
    }
    bool vis[26]{};
    int ans = 0;
    for (auto &[_, idx] : g) {
      for (int i : idx) {
        int j = s[i] - 'a';
        if (vis[j]) {
          return ans;
        }
        vis[j] = true;
      }
      ans += idx.size();
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int: g = defaultdict(list) for i, (x, y) in enumerate(points): g[max(abs(x), abs(y))]. append(i) vis = set() ans = 0 for d in sorted(g): idx = g[d] for i in idx: if s[i] in vis: return ans vis . add(s[i]) ans += len(idx) return ans

```