LeetCode Problem 3464

Difficulty: 🔴 Hard
Topics: Array, Math, Binary Search, Geometry, Sorting

Solution

LeetCode 3464 - Maximize the Distance Between Points on a Square

Problem Understanding

We are given a square of side length side. Every point in the input lies somewhere on the boundary of this square. We must choose exactly k points from the given set.

For any two selected points, we can compute their Manhattan distance:

$$|x_1 - x_2| + |y_1 - y_2|$$

Among all pairs of selected points, there will be one pair with the smallest Manhattan distance. Our goal is to make this minimum distance as large as possible.

In other words, if we select k points, define:

$$D = \min_{i \neq j} \text{ManhattanDistance}(p_i,p_j)$$

We want to maximize D.

The input size provides several important clues:

• points.length can be as large as 15000, so checking all subsets is impossible.
• k ≤ 25, which is surprisingly small.
• All points lie on the perimeter of a square.
• Coordinates can be as large as 10^9.

The most important observation is that although the square is two dimensional, every point lies on a one dimensional perimeter. This allows us to transform the geometry problem into a circular ordering problem.

Important edge cases include:

• Points located at corners.
• Multiple points concentrated on one edge.
• Cases where the optimal answer is 0 or 1.
• Cases where the chosen points must wrap around the perimeter.
• Very large side lengths, where coordinate compression or grid based approaches are impossible.

Approaches

Brute Force

A brute force solution would enumerate every subset of size k.

For each subset:

1. Compute every pairwise Manhattan distance.
2. Find the minimum pair distance.
3. Keep the maximum over all subsets.

This is correct because it directly evaluates every possible selection.

However, the number of subsets is:

$$\binom{n}{k}$$

which is astronomically large even for moderate values of n.

Therefore brute force is completely infeasible.

Key Insight

All points lie on the perimeter of a square.

We can map every boundary point onto a single position along the perimeter measured clockwise from (0,0).

Let perimeter length be:

$$P = 4 \times side$$

Each point becomes a number in [0, P).

After sorting these positions, the perimeter becomes a circle.

A crucial geometric fact is:

For two boundary points, if their clockwise perimeter distance is d, then their Manhattan distance is at least min(d, P-d).

Using the square geometry, the official solution exploits a stronger property: after mapping points onto the perimeter, feasibility of a candidate distance can be checked through circular spacing constraints.

This naturally suggests:

1. Binary search the answer.
2. Check whether we can choose k points whose pairwise Manhattan distance is at least mid.

Because k ≤ 25, we can afford a sophisticated feasibility check.

The accepted solution uses:

• perimeter linearization
• sorting
• binary search
• jump pointers
• trying each point as the first selected point

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(C(n,k) · k²)	O(k)	Enumerates all subsets
Optimal	O(n log n log side)	O(n log n)	Binary search plus circular feasibility check

Algorithm Walkthrough

Perimeter Mapping

Convert every boundary point into a perimeter coordinate.

Starting at (0,0) and moving clockwise:

• Bottom edge: x
• Right edge: side + y
• Top edge: 3*side - x
• Left edge: 4*side - y

This produces a unique position on the perimeter.

Sort Positions

Store all perimeter coordinates and sort them.

Now the perimeter becomes a circular array.

Binary Search

The answer ranges from:

• minimum possible distance: 0
• maximum possible distance: 2 * side

Binary search for the largest feasible value d.

Feasibility Check

For a candidate distance d:

1. Duplicate the sorted perimeter array by appending each position plus the perimeter length.
2. For every position, find the first later position whose perimeter distance is at least d.
3. Build binary lifting jump tables.
4. Try each original point as the first chosen point.
5. Use jump pointers to determine whether k points can be selected with consecutive perimeter gaps at least d.
6. Verify that the final selected point is also at least d away from the starting point around the circle.

If any starting point succeeds, then distance d is feasible.

Why Binary Search Works

If distance d is feasible, then every smaller distance is also feasible.

If distance d is not feasible, then every larger distance is also infeasible.

This monotonic property makes binary search valid.

Why It Works

The perimeter mapping preserves the circular order of boundary points. The feasibility test guarantees that every neighboring selected point along the perimeter is separated sufficiently. The final wrap around check ensures the first and last selected points also satisfy the distance requirement. Therefore every pair of adjacent selected points on the circle is valid, which is sufficient to guarantee the required minimum distance. Because feasibility is monotonic, binary search finds the largest valid distance.

Python Solution

from typing import List
from bisect import bisect_left

class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        perimeter = side * 4

        def pos(x: int, y: int) -> int:
            if y == 0:
                return x
            if x == side:
                return side + y
            if y == side:
                return 3 * side - x
            return 4 * side - y

        arr = sorted(pos(x, y) for x, y in points)
        n = len(arr)

        def can(dist: int) -> bool:
            ext = arr + [x + perimeter for x in arr]
            m = len(ext)

            nxt = [0] * m
            j = 0

            for i in range(m):
                if j < i + 1:
                    j = i + 1
                while j < m and ext[j] - ext[i] < dist:
                    j += 1
                nxt[i] = j

            LOG = 6  # since k <= 25

            jump = [nxt]
            for _ in range(1, LOG):
                prev = jump[-1]
                cur = [m] * m
                for i in range(m):
                    if prev[i] < m:
                        cur[i] = prev[prev[i]]
                jump.append(cur)

            for start in range(n):
                cur = start
                need = k - 1

                bit = 0
                while need:
                    if need & 1:
                        cur = jump[bit][cur]
                        if cur >= m:
                            break
                    need >>= 1
                    bit += 1

                if cur >= start + n:
                    continue

                if ext[cur] - ext[start] > perimeter - dist:
                    continue

                return True

            return False

        left, right = 0, 2 * side

        while left < right:
            mid = (left + right + 1) // 2

            if can(mid):
                left = mid
            else:
                right = mid - 1

        return left

Implementation Explanation

The first section converts every boundary point into a perimeter coordinate. This transforms the square boundary into a circular one dimensional structure.

The array is sorted so that perimeter order is preserved.

Inside can(dist), we duplicate the perimeter array. The duplicated portion allows us to represent circular intervals as ordinary contiguous intervals.

For every position we compute nxt[i], the first point whose perimeter coordinate differs by at least dist.

Binary lifting is then constructed over these transitions. Since k ≤ 25, only six levels are required because:

$$2^5 = 32$$

For every possible starting point, binary lifting quickly jumps through k-1 selections. If we can place all selected points within one perimeter revolution and the wrap around gap also satisfies the distance requirement, the candidate distance is feasible.

Finally, binary search finds the maximum feasible distance.

Go Solution

package main

import (
	"sort"
)

func maxDistance(side int, points [][]int, k int) int {
	perimeter := 4 * side

	pos := func(x, y int) int {
		if y == 0 {
			return x
		}
		if x == side {
			return side + y
		}
		if y == side {
			return 3*side - x
		}
		return 4*side - y
	}

	arr := make([]int, len(points))
	for i, p := range points {
		arr[i] = pos(p[0], p[1])
	}

	sort.Ints(arr)
	n := len(arr)

	can := func(dist int) bool {
		ext := make([]int, 2*n)
		copy(ext, arr)
		for i := 0; i < n; i++ {
			ext[n+i] = arr[i] + perimeter
		}

		m := len(ext)

		nxt := make([]int, m)

		j := 0
		for i := 0; i < m; i++ {
			if j < i+1 {
				j = i + 1
			}
			for j < m && ext[j]-ext[i] < dist {
				j++
			}
			nxt[i] = j
		}

		LOG := 6

		jump := make([][]int, LOG)
		jump[0] = nxt

		for lv := 1; lv < LOG; lv++ {
			jump[lv] = make([]int, m)
			for i := 0; i < m; i++ {
				if jump[lv-1][i] < m {
					jump[lv][i] = jump[lv-1][jump[lv-1][i]]
				} else {
					jump[lv][i] = m
				}
			}
		}

		for start := 0; start < n; start++ {
			cur := start
			need := k - 1

			bit := 0
			for need > 0 {
				if need&1 == 1 {
					cur = jump[bit][cur]
					if cur >= m {
						break
					}
				}
				need >>= 1
				bit++
			}

			if cur >= start+n {
				continue
			}

			if ext[cur]-ext[start] > perimeter-dist {
				continue
			}

			return true
		}

		return false
	}

	left, right := 0, 2*side

	for left < right {
		mid := (left + right + 1) / 2

		if can(mid) {
			left = mid
		} else {
			right = mid - 1
		}
	}

	return left
}

Go Specific Notes

The Go implementation follows the same logic as the Python version. All arithmetic safely fits within 32 bit signed integers because the largest perimeter is 4 × 10^9, but using Go's native int is still safe on LeetCode's 64 bit environment.

Slices are used instead of Python lists, and binary lifting tables are represented as a two dimensional slice.

Worked Examples

Example 1

Input:

side = 2
points = [[0,2],[2,0],[2,2],[0,0]]
k = 4

Perimeter mapping:

Point	Position
(0,0)	0
(2,0)	2
(2,2)	4
(0,2)	6

Sorted array:

Index	Position
0	0
1	2
2	4
3	6

Perimeter length:

P = 8

Binary search tests d = 2.

The gaps are:

2, 2, 2, 2

All satisfy the requirement.

Trying d = 3 fails because adjacent positions differ by only 2.

Therefore the answer is:

2

Example 2

Input:

side = 2
points = [[0,0],[1,2],[2,0],[2,2],[2,1]]
k = 4

Mapped positions:

Point	Position
(0,0)	0
(2,0)	2
(2,1)	3
(2,2)	4
(1,2)	5

Sorted positions:

[0,2,3,4,5]

Distance 2 is not feasible because one of the required gaps becomes only 1.

Distance 1 is feasible.

Answer:

1

Example 3

Input:

side = 2
points = [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]]
k = 5

Mapped positions:

[0,2,3,4,5,6,7]

Trying d = 2 fails because five points cannot be placed with all gaps at least 2.

Trying d = 1 succeeds.

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n log side)	Sorting plus binary search, each feasibility check is linear up to logarithmic lifting factors
Space	O(n log k)	Extended array and jump tables

The dominant cost comes from sorting the perimeter positions and running the feasibility test during binary search. Since k ≤ 25, the binary lifting depth remains constant, making the practical complexity very efficient for n = 15000.

Test Cases

sol = Solution()

assert sol.maxDistance(
    2,
    [[0,2],[2,0],[2,2],[0,0]],
    4
) == 2  # example 1

assert sol.maxDistance(
    2,
    [[0,0],[1,2],[2,0],[2,2],[2,1]],
    4
) == 1  # example 2

assert sol.maxDistance(
    2,
    [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]],
    5
) == 1  # example 3

assert sol.maxDistance(
    1,
    [[0,0],[1,0],[1,1],[0,1]],
    4
) == 1  # smallest square

assert sol.maxDistance(
    10,
    [[0,0],[10,0],[10,10],[0,10]],
    4
) == 10  # corners only

assert sol.maxDistance(
    100,
    [[0,0],[100,0],[100,100],[0,100],[50,0]],
    4
) == 100  # ignore extra point

assert sol.maxDistance(
    5,
    [[0,0],[1,0],[2,0],[3,0],[4,0],[5,0],[5,5],[0,5]],
    4
) >= 1  # dense edge points

assert sol.maxDistance(
    10,
    [[0,0],[10,0],[10,10],[0,10],[5,0],[10,5],[5,10],[0,5]],
    4
) == 10  # choose corners

Test Summary

Test	Why
Example 1	Basic corner configuration
Example 2	Distance constrained by nearby points
Example 3	Larger selection count
Smallest square	Minimum valid side length
Four corners only	Symmetric optimal arrangement
Extra interior perimeter point	Verifies ignoring unnecessary points
Dense edge distribution	Stress on spacing logic
Corners plus midpoints	Ensures optimal subset selection

Edge Cases

All Four Corners

A common mistake is assuming perimeter distance and Manhattan distance are identical. At the corners, geometry behaves differently because shortest Manhattan paths can cut through the square interior. The implementation correctly handles this because the feasibility logic is derived from the square boundary geometry rather than treating the perimeter as a simple cycle graph.

Many Points Concentrated on One Edge

Thousands of points may appear on a single edge while only a few appear elsewhere. A greedy local strategy can easily become trapped by choosing points too early. The implementation avoids this by binary searching the answer and globally checking feasibility through jump pointers.

Wrap Around Selections

The first selected point and last selected point are adjacent on the circular perimeter. Many solutions correctly enforce distances between consecutive forward selections but forget this final circular constraint. The implementation explicitly verifies the wrap around gap with:

ext[cur] - ext[start] <= perimeter - dist

which guarantees the circular spacing requirement is also satisfied.

Very Large Coordinates

The side length can reach 10^9, making coordinate based grids or dynamic programming over positions impossible. The implementation only stores perimeter coordinates and performs arithmetic operations on them, so it scales comfortably even for the largest coordinate values.