Skip to main content
Talentd

Maximize the Distance Between Points on a Square - Solution & Explanation

HardArrayMathBinary SearchGeometry14 min readAsked at: Google, Bloomberg
Practice this problem

Problem Statement

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:

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:

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:

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)

Approach Overview

Problem Overview: You are given points on the boundary of a square and must choose k of them such that the minimum distance between any pair is maximized. Since all points lie on the perimeter, the key idea is to convert the 2D boundary into a 1D circular distance problem and then search for the largest feasible spacing.

Approach 1: Brute Force Combination Check (Exponential Time, O(C(n,k) * k))

Generate every combination of k points and compute the minimum pairwise distance within that subset. Track the maximum of these minimum distances. Distance is measured along the square boundary, so each pair requires perimeter distance computation. This approach is straightforward but infeasible for large n because combinations grow exponentially. Space complexity is O(k) for recursion or combination storage.

Approach 2: Perimeter Mapping + Binary Search (O(n log n + n log P))

Each boundary point can be mapped to a single scalar position along the square’s perimeter. For a square of side L, compute the distance from a fixed corner while walking clockwise. After mapping, sort these positions using sorting. The problem becomes selecting k positions on a circular line so that the minimum gap between consecutive chosen points is maximized.

Use binary search on the answer. For a candidate minimum distance d, greedily attempt to pick points while maintaining at least d separation along the perimeter. Because the perimeter forms a cycle, duplicate the array (append positions + perimeter length) to simulate wraparound and check feasibility from each starting point. This greedy feasibility check runs in O(n). Binary search over the distance range (0 to perimeter) gives total time O(n log P) with O(n) extra space.

The geometry component is only used to convert coordinates into perimeter distance; after that the algorithm behaves like a classic spacing optimization problem. See related techniques in arrays and geometry problems.

Recommended for interviews: The perimeter mapping plus binary search approach. Interviewers expect you to recognize the "maximize the minimum distance" pattern and apply binary search with a greedy feasibility check. Mentioning the brute force approach first shows understanding of the objective, but the binary search optimization demonstrates strong algorithmic reasoning.

Solution

Since the problem asks to maximize the minimum distance, we can use binary search on the answer to find the optimal solution.

First, to simplify the logic, we map the 2D coordinates (x, y) on the square's boundary to a 1D axis [0, 4 times side). The mapping rules are as follows:

  • If x = 0, the mapped value is y;
  • If y = side, the mapped value is side + x;
  • If x = side, the mapped value is 3 times side - y;
  • Otherwise, the mapped value is 4 times side - x.

After mapping, sort all the points to obtain the array nums. Since the points are selected on the perimeter of the square, this is essentially a circular (ring) problem.

During the binary search, for a given minimum distance lo, we use a check function to verify its feasibility:

  • Iterate through each point in nums as the starting point start.
  • The endpoint for selecting points is end = start + 4 times side - lo, ensuring that the wrap-around distance from the last selected point back to start is at least lo.
  • Then, greedily perform k-1 jumps, each time using binary search to quickly locate the next point that is at least lo away from the current position.
  • If it is possible to select k points within the end limit, then the distance lo is feasible.

The time complexity is O(n log (side) cdot n log n) and the space complexity is O(n), where n is the length of the points array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force CombinationO(C(n,k) * k)O(k)Small inputs where n and k are tiny or for validating logic
Perimeter Mapping + SortingO(n log n)O(n)Preprocessing step to convert 2D boundary points into ordered perimeter positions
Binary Search with Greedy PlacementO(n log P)O(n)Optimal solution when maximizing minimum distance on circular perimeter

Video Solution

Maximize the Distance Between Points on a Square | Super Detailed Intuition | Leetcode 3464 | MIK • codestorywithMIK • 5,681 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximize the Distance Between Points on a Square easy or hard?
Maximize the Distance Between Points on a Square is categorized as a Hard problem because it combines geometry preprocessing, circular array handling, and binary search on the answer. Recognizing the perimeter mapping and feasibility check pattern is the main challenge.
Maximize the Distance Between Points on a Square Python/Java solution
Implement the solution by mapping each point to its perimeter coordinate, sorting the array, and applying binary search on the minimum distance. During each check, greedily place points while ensuring at least the candidate spacing. This implementation works consistently across Python, Java, C++, and Go with the same algorithmic structure.
How to solve Maximize the Distance Between Points on a Square in O(n log n)?
First convert each point on the square boundary into a single perimeter distance measured from a fixed corner. Sort these values and binary search the maximum minimum distance between chosen points. For each candidate distance, greedily pick points while maintaining the spacing constraint and simulate circular wraparound by duplicating the perimeter array.
What is the best approach for Maximize the Distance Between Points on a Square?
The most efficient approach maps each boundary point to its position along the square’s perimeter, sorts those positions, and performs binary search on the minimum allowed distance. A greedy feasibility check verifies whether k points can be placed with at least that spacing. This reduces the problem to O(n log n + n log P) time where P is the perimeter.
Is Maximize the Distance Between Points on a Square asked at Google/Amazon/Meta?
Problems involving maximizing minimum distance using binary search and greedy checks appear frequently in interviews at companies like Google, Amazon, and Meta. Variants include aggressive cows, router placement, and circular spacing problems, all using the same binary search on answer pattern.
What data structure is used in Maximize the Distance Between Points on a Square?
The core data structure is a sorted array of perimeter positions. Binary search is applied on the answer space, and a greedy scan over the array verifies feasibility. Geometry is only used during preprocessing to convert 2D coordinates into 1D perimeter distances.
What is the time complexity of Maximize the Distance Between Points on a Square?
The optimal algorithm runs in O(n log n + n log P). Sorting the perimeter positions takes O(n log n), and binary searching the answer performs O(log P) iterations with an O(n) greedy feasibility check each time. Space complexity is O(n) for storing mapped positions.

Ready to solve this problem?

Practice Maximize the Distance Between Points on a Square with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Number of Integers to Choose From a Range II

Next

Maximum Points Inside the Square