398. Maximize the Distance Between Points on a Square

Enumerate every size-k subset of points and compute its minimum pairwise Manhattan distance. Take the maximum across subsets. Combinatorial blow-up makes this useful only for tiny inputs.

Approach

1. Generate every C(n, k) subset.
2. For each subset, compute pairwise distances in O(k²) and track its minimum.
3. Take the maximum of those minima.

Complexity

• Time: O(C(n, k) · k²).
• Space: O(k) for the subset.

import java.util.*;

class Solution {
    public int maximizeSquareDist(int side, int[][] points, int k) {
        int n = points.length;
        int best = 0;
        int[] indices = new int[k];
        best = combine(points, indices, 0, 0, n, k);
        return best;
    }

    private int combine(int[][] points, int[] indices, int start, int depth, int n, int k) {
        if (depth == k) {
            int minDist = Integer.MAX_VALUE;
            for (int i = 0; i < k; i++) {
                for (int j = i + 1; j < k; j++) {
                    int dist = Math.abs(points[indices[i]][0] - points[indices[j]][0])
                             + Math.abs(points[indices[i]][1] - points[indices[j]][1]);
                    minDist = Math.min(minDist, dist);
                }
            }
            return minDist;
        }
        int best = 0;
        for (int i = start; i <= n - (k - depth); i++) {
            indices[depth] = i;
            best = Math.max(best, combine(points, indices, i + 1, depth + 1, n, k));
        }
        return best;
    }
}

Two ideas plug together. First, if we can pick k points pairwise ≥ d apart, we can also pick them pairwise ≥ d - 1 apart — the answer is monotonic in d, so we can binary-search it. Second, all points lie on the square's boundary, so we can lay them out on a 1-D "perimeter line" by walking around the square; the greedy choice — given a starting point, repeatedly take the next point at distance ≥ d — works because cyclic order around the boundary is fixed.

Why the answer is monotonic

The feasibility predicate f(d) = "can we pick k points with all pairwise Manhattan distances ≥ d?" satisfies: if f(d) is true, then f(d') is true for every d' ≤ d (the same selection works). So f is a step function — true for d ≤ ans, false for d > ans. Binary search finds the largest d where f(d) is still true.

The search range is [0, 2 · side] because the largest possible Manhattan distance between two boundary points of an s × s square is 2s (corner to opposite corner).

Mapping the boundary to a number line

Walk clockwise around the perimeter starting at (0, 0):

• Bottom edge y = 0, x from 0 to side: perimeter position s = x.
• Right edge x = side, y from 0 to side: perimeter position s = side + y.
• Top edge y = side, x from side down to 0: perimeter position s = 2·side + (side - x).
• Left edge x = 0, y from side down to 0: perimeter position s = 3·side + (side - y).

Each boundary point gets a unique s in [0, 4·side). Sort points by s.

Feasibility check (greedy)

For a candidate d, try every point as the starting point. From the start, walk forward in the sorted order and greedily pick the first point whose Manhattan distance to the previously-picked point is ≥ d. Continue until we've picked k points or wrap around.

Why greedy works: once points are ordered cyclically, skipping a candidate that satisfies d and trying a later one only postpones progress — we never gain a feasible selection by being less aggressive.

Steps

1. Sort points by perimeter position.
2. Binary search lo = 0, hi = 2·side.
3. While lo < hi:
   • mid = (lo + hi + 1) // 2 (upper mid for largest-true search).
   • If check(mid) succeeds, lo = mid. Else hi = mid - 1.
4. Return lo.

check(d):

for start in 0..n-1:
    cnt = 1, last = start
    for _ in range(k - 1):
        for step in 1..n-1:
            nxt = (last + step) % n
            if nxt == start: break       # wrapped without finding enough
            if manhattan(pts[nxt], pts[last]) >= d:
                last = nxt; cnt += 1; break
    if cnt == k: return True
return False

Walk-through

side = 2, k = 4, points = [[0,2],[2,0],[2,2],[0,0]] — the four corners.

Perimeter positions:

• (0,0): bottom edge, s = 0.
• (2,0): bottom-right corner, s = 2.
• (2,2): right edge top, s = 4.
• (0,2): top edge left, s = 6.

Sorted: [(0,0), (2,0), (2,2), (0,2)]. Pairwise Manhattan distances are all 2 between adjacent corners and 4 between opposite ones.

Binary search:

• mid = 2: starting from (0,0), picking neighbours at distance ≥ 2 → all 4 corners qualify. Feasible.
• mid = 3: every adjacent pair has distance 2 < 3, so we can't pick 4 corners. Infeasible.

So ans = 2. ✓

Edge cases

• k == n: must pick all points; the answer is the smallest pairwise distance — but the algorithm still finds it via binary search.
• All points colinear on one edge: every chosen pair is on the same line, distances reduce to 1-D differences along that edge.
• d = 0: trivially feasible — any k distinct points work.

Complexity

• Time: O(n² · log(side)) — binary search has O(log(side)) iterations; each check runs O(n²) in the worst case (every start, then a walk of up to n steps).
• Space: O(n) — the sorted point list.

Why this is hard

The trick is recognising that points on a boundary form a cyclic 1-D arrangement, so we can binary-search the answer and check feasibility greedily. Without that observation, the natural attempt is C(n, k) brute force — way too slow.