# Maximize the Distance Between Points on a Square
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximize-the-distance-between-points-on-a-square)
Canonical: https://scaleengineer.com/dsa/problems/maximize-the-distance-between-points-on-a-square
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
You are given an integer `side`, representing the edge length of a square with corners at `(0, 0)`, `(0, side)`, `(side, 0)`, and `(side, side)` on a Cartesian plane.

You are also given a **positive** integer `k` and a 2D integer array `points`, where `points[i] = [xi, yi]` represents the coordinate of a point lying on the **boundary** of the square.

You need to select `k` elements among `points` such that the **minimum** Manhattan distance between any two points is **maximized**.

Return the **maximum** possible **minimum** Manhattan distance between the selected `k` points.

The Manhattan Distance between two cells `(xi, yi)` and `(xj, yj)` is `|xi - xj| + |yi - yj|`.

**Example 1:**

**Input:** side = 2, points = \[\[0,2\],\[2,0\],\[2,2\],\[0,0\]\], k = 4

**Output:** 2

**Explanation:**

![](https://assets.glich.co/dsa/maximize-the-distance-between-points-on-a-square/image0.png)

Select all four points.

**Example 2:**

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

**Output:** 1

**Explanation:**

![](https://assets.glich.co/dsa/maximize-the-distance-between-points-on-a-square/image1.png)

Select the points `(0, 0)`, `(2, 0)`, `(2, 2)`, and `(2, 1)`.

**Example 3:**

**Input:** side = 2, points = \[\[0,0\],\[0,1\],\[0,2\],\[1,2\],\[2,0\],\[2,2\],\[2,1\]\], k = 5

**Output:** 1

**Explanation:**

![](https://assets.glich.co/dsa/maximize-the-distance-between-points-on-a-square/image2.png)

Select the points `(0, 0)`, `(0, 1)`, `(0, 2)`, `(1, 2)`, and `(2, 2)`.

**Constraints:**

* `1 <= side <= 109`
* `4 <= points.length <= min(4 * side, 15 * 103)`
* `points[i] == [xi, yi]`
* The input is generated such that:  
  * `points[i]` lies on the boundary of the square.
  * All `points[i]` are **unique**.
* `4 <= k <= min(25, points.length)`

# Approaches
## Approach 1: Binary Search with Backtracking
The problem asks to maximize the minimum distance, which is a classic pattern for binary search on the answer. We can binary search for the minimum distance `d`. For a given `d`, we need to determine if it's possible to select `k` points such that the Manhattan distance between any two is at least `d`. This check, let's call it `canPlace(d)`, can be solved using backtracking.
**Time:** O(C(n, k) * k * log(side)) in the worst case, where C(n, k) is the number of combinations. This is prohibitively slow. · **Space:** O(k) for the recursion stack and storing the current selection.
**Pros:** Conceptually simple and intuitive.; A direct translation of the problem statement into a search algorithm.
**Cons:** The time complexity is exponential in `k` and polynomial in `n`, which is too slow for the given constraints (`n` up to 15000, `k` up to 25).; Likely to cause a Time Limit Exceeded (TLE) error.
### Explanation
The overall algorithm is to binary search for the answer `d` in the range `[0, 2 * side]`. The `canPlace(d)` function is the core of this approach.

To implement `canPlace(d)`, we can define a recursive backtracking function that tries to build a valid set of `k` points. We first sort the points to have a consistent order, for example, lexicographically.

The backtracking function, say `solve(k_needed, start_index, current_selection)`, would try to find `k_needed` more points starting from `start_index` in the sorted `points` array, given the `current_selection`.

- The base case for the recursion is when `k_needed` is 0, which means we have successfully found `k` points, so we return `true`.
- If we run out of points to consider (`start_index` reaches the end) before finding `k` points, we return `false`.
- In the recursive step, we iterate from `start_index` to the end of the points array. For each point `p_i`, we check if it's compatible with all points already in `current_selection` (i.e., its Manhattan distance to each is at least `d`).
- If `p_i` is compatible, we add it to our selection and recurse to find `k_needed - 1` points from the rest of the array (`solve(k_needed - 1, i + 1, ...)`).
- If the recursive call returns `true`, we propagate `true` up. Otherwise, we backtrack by removing `p_i` and continue exploring other options.

This approach explores different combinations of `k` points, pruning branches that are invalid. However, its worst-case time complexity is exponential, making it too slow for the given constraints.
### Algorithm
1. Binary search for the answer `d` in the range `[0, 2 * side]`.
2. For each `d`, call `canPlace(d)` to check feasibility.
   - `canPlace(d)` uses a backtracking helper function `solve(count, start_index, selection)`.
   - Sort the input `points` array lexicographically.
   - `solve(count, start_index, selection)`:
     - If `count == k`, a valid set is found, return `true`.
     - If `n - start_index < k - count`, not enough points remain, return `false`.
     - Iterate `i` from `start_index` to `n-1`:
       - Check if `points[i]` is at least distance `d` from all points in `selection`.
       - If it is, add `points[i]` to `selection` and call `solve(count + 1, i + 1, selection)`.
       - If the recursive call is successful, return `true`.
       - Backtrack: remove `points[i]` from `selection`.
     - If the loop finishes, no solution found from this path, return `false`.
3. If `canPlace(d)` is true, we try for a larger `d` (`low = mid + 1`); otherwise, we need a smaller `d` (`high = mid - 1`).

## Approach 2: Binary Search with O(n^2) Dynamic Programming
This approach also uses binary search on the answer `d`. The `canPlace(d)` check is improved by using dynamic programming. The problem of selecting `k` points with a minimum distance `d` can be modeled as finding the longest path in a Directed Acyclic Graph (DAG).
**Time:** O(n^2 * log(side)). The `canPlace` function takes O(n^2) due to the nested loops for the DP. The binary search adds a `log(side)` factor. · **Space:** O(n) to store the `dp` array.
**Pros:** Polynomial time complexity, much better than exponential backtracking.; Guaranteed to find the optimal solution for `canPlace(d)`.
**Cons:** The `O(n^2)` complexity for `canPlace(d)` is still too slow given `n` can be up to 15,000.; Will likely result in TLE for larger test cases.
### Explanation
First, we sort the points lexicographically. This gives us a processing order and ensures the graph we build is a DAG. Let the sorted points be `p_0, p_1, ..., p_{n-1}`.

We can define a DAG where the vertices are the points, and a directed edge exists from `p_j` to `p_i` if `j < i` and the Manhattan distance between them is at least `d`. The problem then becomes finding if there is a path of length `k-1` (which involves `k` vertices) in this DAG.

This can be solved with dynamic programming. Let `dp[i]` be the maximum number of points in a valid sequence (all pairwise distances >= `d`) ending at point `p_i`.
The recurrence relation is:
`dp[i] = 1 + max({0} U {dp[j] | j < i and dist(p_i, p_j) >= d})`

We compute `dp[i]` for `i` from 0 to `n-1`. For each `i`, we iterate through all `j < i` to find the maximum `dp[j]` that satisfies the distance condition. If the maximum value in the `dp` array is `k` or more, it means we can find such a set of `k` points, and `canPlace(d)` is true.

The overall algorithm is:
1. Binary search for `d`.
2. Inside `canPlace(d)`:
   a. Sort points lexicographically.
   b. Initialize `dp` array of size `n` with all 1s.
   c. For `i` from 1 to `n-1`:
      For `j` from 0 to `i-1`:
         If `dist(p_i, p_j) >= d`:
            `dp[i] = max(dp[i], 1 + dp[j])`
   d. Check if `max(dp)` is at least `k`.
### Algorithm
1. Binary search for the answer `d` in the range `[0, 2 * side]`.
2. For each `d`, call `canPlace(d)`.
   - `canPlace(d)`:
     - Sort the `points` array lexicographically.
     - Create a `dp` array of size `n`, where `n` is the number of points. Initialize `dp[i] = 1` for all `i`.
     - Iterate `i` from 1 to `n-1`:
       - Iterate `j` from 0 to `i-1`:
         - If `manhattanDist(points[i], points[j]) >= d`:
           - Update `dp[i] = max(dp[i], 1 + dp[j])`.
     - Find the maximum value in the `dp` array. If it's `>= k`, return `true`. Otherwise, return `false`.
3. Adjust the binary search range based on the result of `canPlace(d)`.

## Approach 3: Binary Search with Optimized O(n log² n) DP
This approach optimizes the `O(n^2)` DP transition using a coordinate transformation and a 2D data structure. The goal is to speed up the calculation of `dp[i]` from `O(n)` to something faster, like `O(log^2 n)` or `O(log n)`.
**Time:** O(n log²(n) * log(side)). The `canPlace` function takes O(n log² n) due to `n` operations (query/update) on the 2D data structure, each taking O(log² n). The binary search adds the `log(side)` factor. · **Space:** O(n log² n) for the dynamic 2D data structure. Coordinate compression requires O(n) space.
**Pros:** Highly efficient, with a quasi-linearithmic time complexity.; Solves the problem within typical time limits for competitive programming.
**Cons:** Complex to implement, requiring advanced data structures like a dynamic 2D segment tree or similar.; Higher constant factors in runtime compared to simpler approaches.
### Explanation
The core idea is to optimize the query `max({dp[j] | j < i and dist(p_i, p_j) >= d})`.

**Coordinate Transformation:**
The Manhattan distance `|x_i - x_j| + |y_i - y_j|` is equivalent to the L-infinity distance `max(|u_i - u_j|, |v_i - v_j|)` in a transformed coordinate system where `u = x + y` and `v = x - y`. So, `dist(p_i, p_j) >= d` is equivalent to `max(|u_i - u_j|, |v_i - v_j|) >= d`.
This condition holds if `u_j <= u_i - d` OR `u_j >= u_i + d` OR `v_j <= v_i - d` OR `v_j >= v_i + d`.

**DP with 2D Data Structure:**
We still sort points lexicographically and compute `dp[i]` as the max length of a valid sequence ending at `p_i`. To find the max `dp[j]` for `j < i` satisfying the distance condition, we query a 2D data structure that stores `dp` values in the `(u, v)` plane.

For each point `p_i`, we need to find the maximum `dp[j]` over `j < i` where `p_j` lies in the union of four half-planes in the `(u, v)` space. This can be done by querying for the maximum in four corresponding rectangular regions. For example, `u_j <= u_i - d` corresponds to the region `(-inf, -inf)` to `(u_i - d, +inf)`.

A standard 2D segment tree would require `O(n^2)` space after coordinate compression, which is too much. We can use a dynamic 2D segment tree (or a segment tree of Fenwick trees) which only creates nodes as needed. This reduces the space complexity.

**Algorithm for `canPlace(d)`:**
1. Sort points lexicographically.
2. Transform all points `(x, y)` to `(u, v) = (x+y, x-y)`.
3. Collect all `u, v` coordinates and their query boundaries (e.g., `u_i-d`, `v_i+d`) and perform coordinate compression.
4. Initialize a dynamic 2D data structure (e.g., segment tree) for range max queries.
5. Iterate `i` from 0 to `n-1`:
   a. Query the 2D DS to find the max `dp` value in the four valid regions for `p_i` based on its `(u_i, v_i)` values.
   b. `dp[i] = 1 + max_queried_dp`.
   c. Update the 2D DS at `(u_i, v_i)` with the new value `dp[i]`.
   d. If `dp[i] >= k`, return `true`.
6. If the loop finishes, return `false`.

This approach brings the complexity of `canPlace(d)` down to `O(n log^2 n)`, making the whole solution efficient enough to pass.
### Algorithm
1. Binary search for the answer `d`.
2. `canPlace(d)`:
   a. Sort `points` lexicographically.
   b. For each point `p_i(x_i, y_i)`, compute transformed coordinates `u_i = x_i + y_i`, `v_i = x_i - y_i`.
   c. Collect all `u` and `v` coordinates and their query boundaries (`u_i 1 d`, `v_i 1 d`) and compress them into a smaller integer range.
   d. Initialize a dynamic 2D data structure (e.g., a 2D segment tree) that supports point updates and range max queries on the compressed `(u, v)` space.
   e. Initialize `dp` array of size `n`.
   f. Iterate `i` from 0 to `n-1`:
      i. Determine the query ranges in compressed coordinates for `u_j 2 u_i-d`, `u_j 3 u_i+d`, `v_j 2 v_i-d`, `v_j 3 v_i+d`.
      ii. Query the 2D DS for the maximum `dp` value in these four regions.
      iii. Let the result be `max_prev_dp`. Set `dp[i] = 1 + max_prev_dp`.
      iv. Update the 2D DS at compressed `(u_i, v_i)` with value `dp[i]`.
      v. If `dp[i] >= k`, return `true`.
   g. Return `false`.