aximize the Distance Between Points on a Square || Beat 100% Time and Space
Beat 100% Time and Space Complexity Solution for "Maximize the Distance Between Points on a Square"This solution efficiently solves the problem usingbinary sear
# Beat 100% Time and Space Complexity Solution for "Maximize the Distance Between Points on a Square"

This solution efficiently solves the problem using **binary search** and **greedy selection** to maximize the minimum Manhattan distance between `k` points on the boundary of a square. By leveraging the circular nature of the square's perimeter and mapping points to a 1D coordinate system, the solution achieves optimal performance.

---

## Intuition

The problem involves selecting `k` points from a set of boundary points on a square such that the **minimum Manhattan distance** between any two selected points is maximized. The key observation is that the Manhattan distance between points on the boundary can be represented as the difference in their 1D coordinates along the perimeter of the square. This allows us to:

1. Map the 2D boundary points to a 1D circular coordinate system.
2. Use binary search to determine the maximum possible minimum distance (`d`) between selected points.
3. Greedily select points while ensuring the minimum distance constraint is satisfied.

---

## Approach

1. **Mapping to 1D Perimeter**:
   - Each point on the square's boundary is mapped to its corresponding position along the perimeter (a 1D coordinate system).
   - The perimeter is treated as a circular array to handle wrap-around cases.

2. **Binary Search**:
   - Perform binary search on the candidate minimum distance `d`.
   - For each candidate `d`, check if it's possible to select `k` points such that the minimum distance between consecutive points is at least `d`.

3. **Greedy Selection**:
   - Use a greedy algorithm to select points starting from each possible starting point.
   - Ensure the selected points satisfy the minimum distance constraint by iterating through the sorted 1D coordinates.

4. **Circular Handling**:
   - Extend the 1D coordinate array to simulate the circular nature of the square's perimeter.
   - Check the wrap-around distance from the last selected point back to the first point.

5. **Optimization**:
   - Use binary search to efficiently narrow down the maximum possible minimum distance.
   - Leverage lower bound (binary search) to find the next valid point during greedy selection.

---

## Complexity

- **Time Complexity**: $ O(n \cdot k \cdot \log(\text{side})) $
  - Binary search runs in $ O(\log(\text{side})) $.
  - For each candidate distance, we perform greedy selection in $ O(n \cdot k) $, where `n` is the number of points and `k` is the number of points to select.
  
- **Space Complexity**: $ O(n) $
  - Additional space is used for the 1D coordinate array and its extended version.

---

## Code

```java
import java.util.*;

class Solution {
    public int maxDistance(int side, int[][] points, int k) {
        int n = points.length;
        long L = 4L * side; // Total perimeter of the square.
        long[] t = new long[n];
        
        // Map each point to its 1D perimeter coordinate.
        for (int i = 0; i < n; i++) {
            int x = points[i][0], y = points[i][1];
            t[i] = mapPoint(side, x, y);
        }
        Arrays.sort(t);
        
        // Build extended array to handle the circular nature.
        long[] ext = new long[2 * n];
        for (int i = 0; i < n; i++) {
            ext[i] = t[i];
            ext[i + n] = t[i] + L;
        }
        
        // Binary search on candidate minimum Manhattan distance d.
        int lo = 0, hi = 2 * side, ans = 0;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (canPlace(ext, n, k, L, mid)) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return ans;
    }
    
    // Map a boundary point (x, y) to its 1D perimeter coordinate.
    private long mapPoint(int side, int x, int y) {
        // Bottom edge: y == 0 → t = x.
        if (y == 0) return x;
        // Right edge: x == side → t = side + y.
        if (x == side) return side + y;
        // Top edge: y == side → t = 3*side - x.
        if (y == side) return 3L * side - x;
        // Left edge: x == 0 → t = 4*side - y.
        return 4L * side - y;
    }
    
    // Check if it's possible to select k points (from the circular list) such that
    // the minimum gap between consecutive selected points (in circular order) is at least d.
    private boolean canPlace(long[] ext, int n, int k, long L, int d) {
        // Try each possible starting index (from the original sorted array, indices 0 to n-1)
        for (int i = 0; i < n; i++) {
            int count = 1;
            long pos = ext[i];
            int idx = i;
            // We need to pick k points in one full circle: consider indices in [i+1, i+n)
            for (int cnt = 1; cnt < k; cnt++) {
                long target = pos + d;
                int nextIdx = lowerBound(ext, idx + 1, i + n, target);
                if (nextIdx >= i + n) {
                    count = -1;
                    break;
                }
                idx = nextIdx;
                pos = ext[idx];
                count++;
            }
            // Check wrap-around: gap from last chosen point to (first + L) must be at least d.
            if (count == k && (ext[i] + L - pos) >= d)
                return true;
        }
        return false;
    }
    
    // Standard lower_bound: returns the smallest index in arr[low, high) where arr[index] >= target.
    private int lowerBound(long[] arr, int low, int high, long target) {
        int l = low, r = high;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}
['Binary Search', 'Greedy', 'Geometry', 'Sorting', 'Java']