Easy | Beats 100%🔥 | Fast | Beginner Friendly (Used GPT To Come Up to this Approach)
Intuition

Problem Goal:

You need to select k points from the boundary of a square such that the minimum Manhattan distance between any two selected points is
### **Intuition**

1. **Problem Goal**:
   - You need to select `k` points from the boundary of a square such that the **minimum Manhattan distance** between any two selected points is **maximized**.

2. **Key Insight**:
   - The boundary of the square is **circular**, meaning the distance between the last and first point must also be considered.
   - To handle this, you **map the 2D points to a 1D linear sequence** and **extend the sequence** to simulate the circular boundary.

3. **Binary Search**:
   - Use binary search to find the **maximum possible minimum distance** (`p`) between any two selected points.
   - For each candidate distance `p`, you check if it's possible to select `k` points such that no two points are closer than `p`.

4. **Feasibility Check**:
   - `isValid` function iterates over all possible starting points and uses **binary search** to find the next valid point that is at least `p` distance away.
   - This ensures that the **circular boundary** is handled correctly.

---

### **Approach**


#### **1. Linear Mapping**
- You map each 2D point on the boundary of the square to a 1D linear sequence using the `map` function.
- This simplifies the problem by converting it into a **1D problem**.

#### **2. Extended Sequence**
- You extend the linear sequence by appending a copy of itself shifted by `4 * side`.
- This simulates the **circular boundary** of the square, ensuring that the distance between the last and first point is considered.

#### **3. Binary Search**
- You perform binary search on the possible values of the minimum distance (`p`).
- The search range is from `0` to `2 * side` (the maximum possible distance).

#### **4. Feasibility Check**
- For each candidate distance `p`, you check if it's possible to select `k` points such that no two points are closer than `p`.
- You iterate over all possible starting points and use **binary search** to find the next valid point that is at least `p` distance away.
- This ensures that the **circular boundary** is handled correctly.

#### **5. Return the Result**
- The maximum valid candidate distance is returned as the result.

---

### **Why `isValid` Function Works**

Your `isValid` function is **correct** because:
1. It iterates over all possible starting points (`i` from `0` to `n-1`).
2. For each starting point, it uses **binary search** to find the next valid point that is at least `p` distance away.
3. It ensures that the **circular boundary** is handled by checking the distance between the last selected point and the first point in the extended sequence.

---

### **Example Walkthrough**

#### **Input**:
```
side = 2
points = [[0,0],[1,2],[2,0],[2,2],[2,1]]
k = 4
```

#### **Steps**:
1. **Linear Mapping**:
   - Map the points to a 1D sequence: `[0, 5, 2, 7, 6]`.

2. **Extended Sequence**:
   - Extend the sequence: `[0, 5, 2, 7, 6, 8, 13, 10, 15, 14]`.

3. **Binary Search**:
   - Perform binary search on the possible distances (`0` to `4`).

4. **Feasibility Check**:
   - For each candidate distance `p`, check if it's possible to select `k` points such that no two points are closer than `p`.

5. **Result**:
   - The maximum valid candidate distance is `1`.

#### **Output**:
```
1
```

---

# Complexity

### **Time Complexity (TC)**

1. **Linear Mapping**:
   - The `map` function is called for each of the `n` points, so this step takes \(O(n)\).

2. **Sorting**:
   - Sorting the linear sequence takes \(O(n log n)\).

3. **Extended Sequence**:
   - Creating the extended sequence takes \(O(n)\).

4. **Binary Search**:
   - The binary search on the possible distances runs in \(O(log (\{max distance}))\), where the maximum distance is \(2 times \{side}\).

5. **Feasibility Check**:
   - For each candidate distance `p`, the `isValid` function performs:
     - A loop over the first `n` points (\(O(n)\)).
     - For each point, it performs a binary search to find the next valid point (\(O(log n)\)).
   - Therefore, the total time complexity for the feasibility check is \(O(n log n)\).

6. **Overall Time Complexity**:
   - The dominant factor is the feasibility check, which is performed for each candidate distance during the binary search.
   - **Total TC**: \(O(n log n . log ({max distance}))\).

---

### **Space Complexity (SC)**

1. **Linear Sequence**:
   - The `linearSeq` array stores the mapped values of the points, taking \(O(n)\) space.

2. **Extended Sequence**:
   - The `extendSeq` function creates a new array of size \(2n\), taking \(O(n)\) space.

3. **Other Variables**:
   - The binary search and feasibility check use constant extra space.

4. **Overall Space Complexity**:
   - **Total SC**: \(O(n)\).

---

# Code
```java []
public class Solution {
    public int maxDistance(int side, int[][] points, int k) {
        int n = points.length;
        long[] linearSeq = new long[n];
        for (int i = 0; i < n; i++) {
            linearSeq[i] = map(points[i], side);
        }
        Arrays.sort(linearSeq);
        linearSeq = extendSeq(linearSeq, side);

        int st = 0, end = 2 * side, ans = -1;
        while (st <= end) {
            int mid = st + (end - st) / 2;
            if (isValid(linearSeq, side, k, mid)) {
                ans = mid;
                st = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return ans;
    }

    public long map(int[] points, int side) {
        int x = points[0];
        int y = points[1];
        if (y == 0) {
            return x;
        }
        if (x == side) {
            return side + y;
        }
        if (y == side) {
            return 3L * side - x;
        }
        return 4L * side - y;
    }

    public long[] extendSeq(long[] seq, int side) {
        int n = seq.length;
        long[] newSeq = new long[2 * n];
        for (int i = 0; i < n; i++) {
            newSeq[i] = seq[i];
            newSeq[n + i] = seq[i] + (4L * side);
        }
        return newSeq;
    }

    public boolean isValid(long[] linearSeq, int side, int k, long p) {
        int n = linearSeq.length / 2;
        for (int i = 0; i < n; i++) {
            long initPos = linearSeq[i];
            int idx = i;
            int count = 1;
            for (int j = 1; j < k; j++) {
                long minDist = initPos + p;
                int nxtIdx = binarySearch(linearSeq, idx + 1, i + n, minDist);
                if (nxtIdx == i + n) {
                    count = -1;
                    break;
                }
                idx = nxtIdx;
                initPos = linearSeq[idx];
                count++;
            }
            if (count == k && (linearSeq[i] + 4L * side - initPos) >= p) {
                return true;
            }
        }
        return false;
    }

    public int binarySearch(long[] seq, int st, int end, long tar) {
        while (st < end) {
            int mid = st + (end - st) / 2;
            if (seq[mid] >= tar) {
                end = mid;
            } else {
                st = mid + 1;
            }
        }
        return st;
    }
}
```
['Binary Search', 'Greedy', 'Ordered Map', 'Sorting', 'Java']