Scale Engineer

Maximize the Distance Between Points on a Square

Hard
#3080Time: 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.
Patterns
Greedy
Algorithms
Binary Search
Data structures
Array

Prompt

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)

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

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.

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem