Show problems as
Classic problem #3464HardArrayMathBinary SearchGeometrySorting

Maximize the Distance Between Points on a Square

Real-world version: Spreading Marks Round a Square Fence
Tracked in this browser only
Read Maximize the Distance Between Points on a Square on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A square fence has its corners at (0, 0), (side, 0), (side, side) and (0, side). Candidate posts are given as points, each [x, y] lying on the fence itself, and all of them are distinct.

Choose k of the posts. The spread of a choice is the smallest distance between any two posts chosen, measured as the difference in x plus the difference in y.

Return the largest spread any choice of k posts can have.

Examples

Example 1

Input
side = 12, points = [[0, 0], [12, 0], [12, 12], [0, 12], [6, 0], [12, 6]], k = 4
Output
12

Taking the four corners leaves every neighbouring pair 12 apart, and no choice of four posts spreads them further.

Example 2

Input
side = 2, points = [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2], [1, 2], [0, 2], [0, 1]], k = 8
Output
1

Every post on the fence has to be taken, and the closest neighbouring pair sits one apart.

Example 3

Input
side = 1000000000, points = [[0, 0], [1000000000, 0], [1000000000, 1000000000], [0, 1000000000]], k = 4
Output
1000000000

Only the four corners are on offer, so the spread is the side length itself.

Constraints

  • 1 <= side <= 10^9
  • 4 <= points.length <= 1000
  • points[i].length == 2
  • Every point lies on the fence
  • All the points are different
  • 4 <= k <= points.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_distance(side: int, points: list[list[int]], k: int) -> int:
Java
public int maxDistance(int side, int[][] points, int k)

More on the same topics