We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize the Distance Between Points on a Square

Number: 3781

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a square with side length side (with corners (0,0), (0,side), (side,0) and (side,side)) and a list of unique points (each guaranteed to lie on the square’s boundary), choose k of these points so that the minimum Manhattan distance between any two chosen points is as large as possible. Return this maximum possible minimum distance.

Key Insights

  • The points lie on the boundary so they have an intrinsic cyclic (or “perimeter”) order.
  • The problem asks for maximizing a “minimum” pairwise distance; such problems are often solved using binary search on the answer.
  • For a candidate distance d, we must check if some subset of k points exists such that every pair has Manhattan distance at least d.
  • Converting each point to its “perimeter coordinate” (i.e. the distance along the boundary from a fixed starting corner) allows us to “order” them; however, note that the Manhattan distance between arbitrary boundary points is computed from their coordinates – so while the ordering helps iterate through candidates, distance checks use the actual Manhattan metric.
  • A greedy selection procedure (with a slight “rotate‐and‐try” over the circle) can be used as a feasibility check within a binary search over possible d.

Space and Time Complexity

Time Complexity: O(log(maxDistance) * n² * k) in the worst case, where maxDistance is 2*side, n is the number of points and k ≤ 25. In practice the constant factors are small and n is at most 15×10³. Space Complexity: O(n) (we store an extended list of 2n points for handling the cyclic wrap-around).

Solution

We solve the problem by binary searching on the possible minimum Manhattan distance d. The maximum possible Manhattan distance between any two boundary points is 2 * side (e.g. from (0,0) to (side,side)) so our search space is [0, 2 * side]. For each candidate d we use a feasibility check: can we pick k points (using a greedy procedure) so that every newly picked point is at least d Manhattan distance away from every previously picked one?

Because the points are on the boundary we first assign each point a “perimeter coordinate” (pos) that represents its distance traveling clockwise around the square starting at (0,0). The mapping is as follows:

  • If y == 0 (bottom edge): pos = x.
  • Else if x == side (right edge): pos = side + y.
  • Else if y == side (top edge): pos = 2 * side + (side - x).
  • Else (x == 0, left edge): pos = 3 * side + (side - y).

Sort the points by pos. Because the boundary is cyclic, we “extend” the list by appending each point again with pos shifted by 4 * side (the total perimeter). Then for each possible starting point (from the original sorted list) we try to greedily pick points (by going through the extended list until the next point would be more than one full circle ahead). For each candidate, we include a point only if its Manhattan distance (computed directly from the (x,y) coordinates) from all previously selected points is at least d. If we can select k such points then candidate d is feasible. Based on the feasibility, we adjust our binary search.

The trickiest part is to correctly handle the cyclic order and perform the distance check among all chosen points.

Code Solutions

Below are sample solutions in Python, JavaScript, C++ and Java. Each solution is written with line‐by‐line comments.

# Python solution with detailed comments

import math

def compute_perimeter_pos(point, side):
    x, y = point
    # Determine the position along the boundary (clockwise from (0,0))
    if y == 0:
        return x
    elif x == side:
        return side + y
    elif y == side:
        return 2 * side + (side - x)
    else:  # x == 0
        return 3 * side + (side - y)

def manhattan(p1, p2):
    # Calculate Manhattan distance between two points
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def feasible(d, points, side, k):
    n = len(points)
    # Build list of (pos, point)
    pts = []
    for pt in points:
        pos = compute_perimeter_pos(pt, side)
        pts.append((pos, pt))
    # Sort by perimeter coordinate
    pts.sort(key=lambda x: x[0])
    # Extend list to handle circular wrap-around
    ext = pts + [(pos + 4 * side, pt) for (pos, pt) in pts]
    
    # Try every starting index from the original list
    for start in range(n):
        count = 1  # start by picking the starting point
        selected = [pts[start][1]]
        start_pos = pts[start][0]
        # iterate over extended list from start+1 while within one full circle
        for i in range(start + 1, len(ext)):
            # if we have completed a full circle, break
            if ext[i][0] > start_pos + 4 * side:
                break
            candidate = ext[i][1]
            valid = True
            # Check candidate's Manhattan distance with all selected points
            for sel in selected:
                if manhattan(candidate, sel) < d:
                    valid = False
                    break
            if valid:
                selected.append(candidate)
                count += 1
                if count >= k:
                    return True
    return False

def maximizeMinDistance(side, points, k):
    # Binary search over possible Manhattan distance d
    low, high = 0, 2 * side  # Maximum possible Manhattan distance on the square
    answer = 0
    while low <= high:
        mid = (low + high) // 2
        if feasible(mid, points, side, k):
            answer = mid  # mid is feasible; try to see if we can go higher
            low = mid + 1
        else:
            high = mid - 1
    return answer

# Example usage:
# side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4 -> expected output 2
#print(maximizeMinDistance(2, [[0,2],[2,0],[2,2],[0,0]], 4))
← Back to All Questions