3464. Maximize the Distance Between Points on a Square

HardGeometryArrayMathBinary SearchSorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer side, which represents the edge length of a square. The square's four corners are located at (0, 0), (0, side), (side, 0), and (side, side) on a Cartesian plane.

In addition, you are given a positive integer k and a 2D integer array points. Each entry points[i] = [xi, yi] is the coordinate of a point that lies on the boundary (perimeter) of the square.

Your task is to choose k points from points so that the minimum Manhattan distance between any two chosen points is as large as possible.

In other words, among all the ways to pick k points, look at the smallest pairwise Manhattan distance in each selection, and return the maximum value this smallest distance can reach.

The Manhattan distance between two points (xi, yi) and (xj, yj) is defined as |xi - xj| + |yi - yj|.

Return the maximum possible minimum Manhattan distance among the k selected points.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Binary Search?

This problem maps to Binary Search through a short path in the full flowchart.

The problem asks to maximize the minimum Manhattan distance, which is monotonic in feasibility, so binary search on the answer combined with a greedy check works.

Open in Flowchart

Intuition

The key phrase in this problem is "maximize the minimum distance." Whenever we see a problem that asks us to maximize a minimum (or minimize a maximum), it is a strong hint that we can use binary search on the answer.

Why does binary search work here? Notice the monotonic property: if we can successfully pick k points whose pairwise minimum distance is at least d, then we can certainly also pick k points whose pairwise minimum distance is at least any smaller value d' < d. Conversely, if a distance d is impossible to achieve, any larger distance is also impossible. This monotonicity lets us binary search over the candidate answer d and, for each guess, just ask a simpler yes/no question: "Can we select k points such that every pair is at least d apart?"

The next challenge is that the points lie on the boundary of a square, which is awkward to reason about in 2D. However, there is a neat observation: for any two points on the perimeter, walking along the boundary from one to the other, the Manhattan distance equals the boundary (perimeter) distance, as long as we travel the shorter arc. This is because moving along an edge changes only one coordinate at a time, and turning a corner is exactly the point where the Manhattan path switches direction. So we can "unfold" the square's perimeter into a 1D circular axis of total length 4 * side.

To do this unfolding, we map every boundary point to a single value based on which edge it sits on, walking around the perimeter in order:

On the left edge (x = 0), the value is y;
On the top edge (y = side), the value is side + x;
On the right edge (x = side), the value is 3 * side - y;
On the bottom edge (otherwise), the value is 4 * side - x.

After this mapping and sorting, the problem becomes: place k markers on a circle of circumference 4 * side so that adjacent markers are at least d apart. Because it is a circle (the last point must also be at least d away from the first when wrapping around), we try each point as a starting point, then greedily jump forward to the nearest point that is at least d away, repeating k - 1 times. Greedy works because, to fit as many points as possible, always taking the earliest valid next point leaves the most room for the remaining picks.

We use a binary search (bisect) inside the greedy step to quickly find the next reachable point, and we cap the reachable end at start + 4 * side - d to guarantee the wrap-around gap back to the start point also respects the distance d. If any starting point lets us place all k markers, then d is feasible, and we push the binary search higher; otherwise, we lower it.

Pattern Learn more about Math, Binary Search and Sorting patterns.

Solution Approach

We use Binary Search on the answer + Coordinate Mapping + Greedy to solve this problem.

Step 1: Map 2D Boundary Points to a 1D Axis

To avoid dealing with awkward 2D geometry, we "unfold" the square's perimeter into a single 1D axis of length 4 * side. Walking clockwise (or counter-clockwise) around the boundary, we convert each point (x, y) into one number according to which edge it lies on:

If x == 0 (left edge), the mapped value is y;
If y == side (top edge), the mapped value is side + x;
If x == side (right edge), the mapped value is 3 * side - y;
Otherwise (bottom edge), the mapped value is 4 * side - x.

After mapping every point, we store the results in nums and sort it. Now the points are arranged on a circular axis with total circumference 4 * side, where the Manhattan distance between two points equals their distance along this axis (taking the shorter arc).

Step 2: Binary Search on the Answer

Since we want to maximize the minimum distance, we binary search over the candidate distance lo in the range [1, side]:

l, r = 1, side
while l < r:
    mid = (l + r + 1) >> 1
    if check(mid):
        l = mid
    else:
        r = mid - 1
return l

Notice that mid = (l + r + 1) >> 1 rounds up. This is the correct form when the update is l = mid, and it prevents an infinite loop when l and r are adjacent. If check(mid) returns True, the distance is achievable, so we try larger values by moving l up; otherwise, we shrink to r = mid - 1.

Step 3: The `check` Function (Greedy on a Circle)

For a candidate distance lo, the check function decides whether we can pick k points so that every adjacent pair is at least lo apart.

Because the points form a circle, the first and last selected points must also satisfy the distance constraint when wrapping around. To handle this, we try every point as the starting point start:

We set end = start + side * 4 - lo. This is the furthest position the last selected point may reach, guaranteeing the wrap-around gap from the last point back to start is at least lo.
Starting from cur = start, we perform k - 1 greedy jumps. In each jump, we use bisect_left(nums, cur + lo) to find the nearest point that is at least lo away from cur:

j = bisect_left(nums, cur + lo)
if j == len(nums) or nums[j] > end:
    ok = False
    break
cur = nums[j]

If no such point exists (j == len(nums)), or the found point exceeds end (nums[j] > end), this starting point fails.
Otherwise, we advance cur to that point and continue.
If we successfully complete all k - 1 jumps from some starting point, then lo is feasible and we return True.

The greedy choice—always jumping to the earliest valid next point—is optimal because leaving as much room as possible for the remaining picks maximizes our chance of fitting all k points.

Complexity Analysis

Let n be the number of points.

Time Complexity: O(n * k * log n * log(side)). The binary search on the answer contributes log(side). Each check call tries n starting points, each performing k - 1 jumps, and every jump uses a bisect costing log n.
Space Complexity: O(n) for the nums array.

Example Walkthrough

Let's trace through a small concrete example to see how Binary Search + Coordinate Mapping + Greedy works together.

Input:

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

These are exactly the four corners of the square. Since we must pick k = 4 points and there are only 4 available, we have no choice but to take all of them. Let's verify what the algorithm computes.

Step 1: Map 2D Boundary Points to a 1D Axis

The perimeter circumference is 4 * side = 8. We unfold each point using the edge rules:

Point `(x, y)`	Which edge?	Rule applied	Mapped value
`(0, 0)`	left (`x == 0`)	`y`	`0`
`(0, 2)`	left (`x == 0`)	`y`	`2`
`(2, 2)`	top (`y == side`) wins after left check fails... actually `x == side`	right (`x == side`)	`3*2 - 2 = 4`
`(2, 0)`	right (`x == side`)	`3*2 - 0 = 6`	`6`

Sorted: nums = [0, 2, 4, 6].

Notice how the four corners land evenly spaced on a circle of circumference 8: positions 0, 2, 4, 6. The gap between consecutive points (including the wrap from 6 back to 0, which is 8 - 6 = 2) is exactly 2.

Step 2: Binary Search on the Answer

We search for the largest feasible minimum distance in range [1, side] = [1, 2].

l = 1, r = 2
mid = (1 + 2 + 1) >> 1 = 2
Call check(2).

Step 3: The `check(2)` Function (Greedy on a Circle)

We try each point as the starting point. Let's start with start = nums[0] = 0.

end = start + side*4 - lo = 0 + 8 - 2 = 6. The last selected point may reach at most position 6.
We need k - 1 = 3 greedy jumps. Begin with cur = 0.

Jump 1: Find nearest point >= cur + lo = 0 + 2 = 2.

bisect_left(nums, 2) → index 1, nums[1] = 2.
2 <= end (6) ✓. Set cur = 2.

Jump 2: Find nearest point >= 2 + 2 = 4.

bisect_left(nums, 4) → index 2, nums[2] = 4.
4 <= 6 ✓. Set cur = 4.

Jump 3: Find nearest point >= 4 + 2 = 6.

bisect_left(nums, 6) → index 3, nums[3] = 6.
6 <= 6 ✓. Set cur = 6.

All 3 jumps succeeded → we placed all 4 points {0, 2, 4, 6}, each adjacent pair at least 2 apart, and the wrap-around gap (6 back to 0) is 8 - 6 = 2 >= 2. So check(2) returns True.

Back to Binary Search

Since check(2) is True:

l = mid = 2.
Now l == r == 2, loop ends.

Return l = 2.

Why This Is Correct

The four chosen points map to 0, 2, 4, 6 on the circle. Their pairwise Manhattan distances correspond to arc distances; the minimum adjacent gap is 2, and there's no way to do better because we are forced to take all four corners. The algorithm correctly reports 2.

This example highlights the three core ideas: the mapping flattens awkward 2D boundary geometry into clean 1D positions, the greedy jump packs points by always taking the earliest valid next position, and the binary search zeroes in on the largest achievable minimum distance.

Solution Implementation

1from bisect import bisect_left
2from typing import List
3
4
5class Solution:
6    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
7        # Map each perimeter point to a 1D coordinate, measuring the clockwise
8        # distance from the top-left corner (0, side) is implied by the edges:
9        #   - left edge   (x == 0):       coordinate = y
10        #   - top edge    (y == side):    coordinate = side + x
11        #   - right edge  (x == side):    coordinate = side * 3 - y
12        #   - bottom edge (otherwise):    coordinate = side * 4 - x
13        perimeter_coords: List[int] = []
14        for x, y in points:
15            if x == 0:
16                perimeter_coords.append(y)
17            elif y == side:
18                perimeter_coords.append(side + x)
19            elif x == side:
20                perimeter_coords.append(side * 3 - y)
21            else:
22                perimeter_coords.append(side * 4 - x)
23
24        # Sort coordinates so we can binary search for the next valid point.
25        perimeter_coords.sort()
26        total_length = side * 4
27
28        def check(min_gap: int) -> bool:
29            # Determine whether we can choose k points so that every pair of
30            # consecutive chosen points is at least `min_gap` apart along the
31            # perimeter.
32            for start in perimeter_coords:
33                # The farthest coordinate still allowed for the final point so
34                # that the wrap-around gap back to `start` is also >= min_gap.
35                end = start + total_length - min_gap
36                current = start
37                feasible = True
38
39                # Greedily pick the remaining k - 1 points.
40                for _ in range(k - 1):
41                    # Find the first point at least `min_gap` away from current.
42                    next_index = bisect_left(perimeter_coords, current + min_gap)
43                    # No valid point or it exceeds the allowed end boundary.
44                    if next_index == len(perimeter_coords) or perimeter_coords[next_index] > end:
45                        feasible = False
46                        break
47                    current = perimeter_coords[next_index]
48
49                if feasible:
50                    return True
51            return False
52
53        # Binary search on the maximum achievable minimum gap.
54        left, right = 1, side
55        while left < right:
56            mid = (left + right + 1) >> 1
57            if check(mid):
58                left = mid          # mid is achievable, try larger.
59            else:
60                right = mid - 1     # mid too large, shrink.
61        return left
62

1class Solution {
2    // Length of one side of the square boundary
3    private int sideLength;
4    // Perimeter positions of all points, mapped onto a 1-D coordinate (clockwise)
5    private long[] perimeterPositions;
6    // Number of points we need to select
7    private int selectCount;
8
9    public int maxDistance(int side, int[][] points, int k) {
10        this.sideLength = side;
11        this.selectCount = k;
12        int pointCount = points.length;
13        this.perimeterPositions = new long[pointCount];
14
15        // Map each point on the square's border to a 1-D position along the perimeter.
16        // Walking clockwise starting from the bottom-left corner (0, 0):
17        //   - Left edge   (x == 0):      position = y
18        //   - Top edge    (y == side):   position = side + x
19        //   - Right edge  (x == side):   position = 3 * side - y
20        //   - Bottom edge (otherwise):   position = 4 * side - x
21        for (int i = 0; i < pointCount; i++) {
22            int x = points[i][0];
23            int y = points[i][1];
24            if (x == 0) {
25                perimeterPositions[i] = (long) y;
26            } else if (y == side) {
27                perimeterPositions[i] = (long) side + x;
28            } else if (x == side) {
29                perimeterPositions[i] = (long) side * 3 - y;
30            } else {
31                perimeterPositions[i] = (long) side * 4 - x;
32            }
33        }
34
35        // Sort positions so we can binary-search along the perimeter.
36        Arrays.sort(perimeterPositions);
37
38        // Binary search on the answer: the maximum achievable minimum distance.
39        // The feasible distance lies within [1, side].
40        int left = 1, right = side;
41        while (left < right) {
42            int mid = (left + right + 1) >> 1;
43            if (canSelect(mid)) {
44                // mid is achievable, try for a larger minimum distance.
45                left = mid;
46            } else {
47                // mid is too large, reduce the search range.
48                right = mid - 1;
49            }
50        }
51        return left;
52    }
53
54    /**
55     * Greedily checks whether we can pick {@code selectCount} points such that
56     * every pair of consecutive picked points (along the perimeter) is at least
57     * {@code minGap} apart.
58     *
59     * @param minGap the candidate minimum gap to validate
60     * @return true if such a selection exists, false otherwise
61     */
62    private boolean canSelect(int minGap) {
63        long perimeter = (long) sideLength * 4;
64
65        // Try each point as the starting point of the selection.
66        for (int i = 0; i < perimeterPositions.length; i++) {
67            long start = perimeterPositions[i];
68            // The last selected point must stay within (start + perimeter - minGap)
69            // so the wrap-around gap between the last and first point is >= minGap.
70            long end = start + perimeter - minGap;
71            long current = start;
72            boolean valid = true;
73
74            // Greedily pick the next (selectCount - 1) points.
75            for (int j = 0; j < selectCount - 1; j++) {
76                // The next eligible point must be at least minGap ahead of current.
77                long target = current + minGap;
78                int idx = lowerBound(perimeterPositions, target);
79
80                // No point is far enough, or the next point exceeds the allowed end.
81                if (idx == perimeterPositions.length || perimeterPositions[idx] > end) {
82                    valid = false;
83                    break;
84                }
85                current = perimeterPositions[idx];
86            }
87
88            if (valid) {
89                return true;
90            }
91        }
92        return false;
93    }
94
95    /**
96     * Returns the index of the first element in {@code arr} that is
97     * greater than or equal to {@code target} (standard lower-bound search).
98     *
99     * @param arr    a sorted array to search in
100     * @param target the value to lower-bound
101     * @return the index of the first element >= target, or arr.length if none
102     */
103    private int lowerBound(long[] arr, long target) {
104        int left = 0, right = arr.length;
105        while (left < right) {
106            int mid = (left + right) >>> 1;
107            if (arr[mid] < target) {
108                left = mid + 1;
109            } else {
110                right = mid;
111            }
112        }
113        return left;
114    }
115}
116

1class Solution {
2public:
3    int maxDistance(int side, vector<vector<int>>& points, int k) {
4        // Map each point on the square's perimeter to a 1D coordinate.
5        // Walking clockwise: left edge -> top edge -> right edge -> bottom edge.
6        vector<long long> perimeterPositions;
7        for (auto& point : points) {
8            int x = point[0];
9            int y = point[1];
10            if (x == 0) {
11                // Left edge: position equals y, range [0, side]
12                perimeterPositions.push_back((long long) y);
13            } else if (y == side) {
14                // Top edge: position equals side + x, range [side, 2*side]
15                perimeterPositions.push_back((long long) side + x);
16            } else if (x == side) {
17                // Right edge: position equals 3*side - y, range [2*side, 3*side]
18                perimeterPositions.push_back((long long) side * 3 - y);
19            } else {
20                // Bottom edge (y == 0): position equals 4*side - x, range [3*side, 4*side]
21                perimeterPositions.push_back((long long) side * 4 - x);
22            }
23        }
24        // Sort positions so we can binary search along the perimeter.
25        sort(perimeterPositions.begin(), perimeterPositions.end());
26
27        // The total perimeter length of the square.
28        const long long perimeterLength = (long long) side * 4;
29
30        // Check whether we can select k points such that the minimum gap
31        // between consecutive chosen points (along the perimeter) is at least minGap.
32        auto canSelect = [&](int minGap) -> bool {
33            for (long long startPos : perimeterPositions) {
34                // 'end' is the furthest position the last chosen point may reach,
35                // ensuring the wrap-around gap back to startPos is also >= minGap.
36                long long end = startPos + perimeterLength - minGap;
37                long long current = startPos;
38                bool valid = true;
39
40                // Greedily pick the next k-1 points, each at least minGap apart.
41                for (int i = 0; i < k - 1; ++i) {
42                    auto it = lower_bound(perimeterPositions.begin(),
43                                          perimeterPositions.end(),
44                                          current + minGap);
45                    // No valid next point, or it overshoots the allowed end.
46                    if (it == perimeterPositions.end() || *it > end) {
47                        valid = false;
48                        break;
49                    }
50                    current = *it;
51                }
52
53                if (valid) {
54                    return true;
55                }
56            }
57            return false;
58        };
59
60        // Binary search on the answer: the largest achievable minimum gap.
61        int left = 1, right = side;
62        while (left < right) {
63            int mid = (left + right + 1) >> 1;
64            if (canSelect(mid)) {
65                // 'mid' is feasible; try for a larger minimum gap.
66                left = mid;
67            } else {
68                // 'mid' is too large; reduce the upper bound.
69                right = mid - 1;
70            }
71        }
72        return left;
73    }
74};
75

1/**
2 * Find the maximum possible minimum distance among k selected points
3 * placed on the perimeter of a square.
4 *
5 * @param side - The length of the square's side.
6 * @param points - Array of [x, y] coordinates lying on the square's perimeter.
7 * @param k - The number of points to select.
8 * @returns The maximized minimum distance between selected consecutive points.
9 */
10function maxDistance(side: number, points: number[][], k: number): number {
11    // Unroll the square perimeter into a single 1D axis (clockwise).
12    // Total perimeter length is side * 4.
13    const positions: number[] = [];
14    for (const [x, y] of points) {
15        if (x === 0) {
16            // Left edge: position equals y (range [0, side]).
17            positions.push(y);
18        } else if (y === side) {
19            // Top edge: continue from the left edge's end.
20            positions.push(side + x);
21        } else if (x === side) {
22            // Right edge: continue after the top edge.
23            positions.push(side * 3 - y);
24        } else {
25            // Bottom edge: the final segment back to the origin.
26            positions.push(side * 4 - x);
27        }
28    }
29    // Sort positions along the perimeter for binary search lookups.
30    positions.sort((a, b) => a - b);
31
32    /**
33     * Find the leftmost index in a sorted array whose value is >= target.
34     * (Native replacement for Lodash's _.sortedIndex.)
35     *
36     * @param arr - A sorted array of numbers.
37     * @param target - The value to locate.
38     * @returns The insertion index for target.
39     */
40    const lowerBound = (arr: number[], target: number): number => {
41        let left = 0;
42        let right = arr.length;
43        while (left < right) {
44            const mid = (left + right) >> 1;
45            if (arr[mid] < target) {
46                left = mid + 1;
47            } else {
48                right = mid;
49            }
50        }
51        return left;
52    };
53
54    /**
55     * Check whether we can select k points such that every pair of
56     * consecutive chosen points is at least `minDistance` apart,
57     * while staying within the circular perimeter.
58     *
59     * @param minDistance - The candidate minimum distance to verify.
60     * @returns True if a valid selection of k points exists.
61     */
62    const check = (minDistance: number): boolean => {
63        const perimeter = side * 4;
64        // Try each position as the starting point.
65        for (const start of positions) {
66            // The last allowed position so the loop closes with >= minDistance gap.
67            const end = start + perimeter - minDistance;
68            let current = start;
69            let ok = true;
70            // Greedily pick the remaining k - 1 points.
71            for (let i = 0; i < k - 1; i++) {
72                // Find the next point at least minDistance away.
73                const next = lowerBound(positions, current + minDistance);
74                // Fail if no such point exists or it exceeds the closing bound.
75                if (next === positions.length || positions[next] > end) {
76                    ok = false;
77                    break;
78                }
79                current = positions[next];
80            }
81            if (ok) {
82                return true;
83            }
84        }
85        return false;
86    };
87
88    // Binary search for the largest feasible minimum distance.
89    let left = 1;
90    let right = side;
91    while (left < right) {
92        // Bias toward the upper half since we maximize.
93        const mid = (left + right + 1) >> 1;
94        if (check(mid)) {
95            left = mid;
96        } else {
97            right = mid - 1;
98        }
99    }
100    return left;
101}
102

Time and Space Complexity

Time Complexity: O(n × log(side) × n × log n), where n is the length of the points array.
- First, mapping each point to its perimeter coordinate takes O(n), and sorting nums takes O(n log n).
- The outer binary search runs over the range [1, side], requiring O(log(side)) iterations.
- Each iteration calls check(mid). Inside check, the outer loop iterates over all n starting points, and for each start, the inner loop runs up to k - 1 times. Each inner step performs a bisect_left, costing O(log n).
- In the worst case, k can be on the order of n, so a single check call costs O(n × k × log n) = O(n² × log n).
- Combining the binary search with the cost of check, the total time complexity is O(n × log(side) × n × log n).
Space Complexity: O(n). The auxiliary array nums stores one perimeter coordinate per point, requiring O(n) space. The sorting may use additional O(n) space, and no other data structures grow with the input size.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Handling the Wrap-Around with `bisect_left`

The most subtle and dangerous bug in this solution lies in the circular nature of the perimeter. When we map points onto a 1D axis of length 4 * side, the points form a circle, not a straight line. The greedy bisect_left(perimeter_coords, current + min_gap) only searches forward in the sorted array—it never "wraps around" past the largest coordinate back to the smallest.

Why this matters: Consider a starting point near the end of the sorted array. After a few jumps, current + min_gap may exceed the maximum coordinate, so bisect_left returns len(perimeter_coords) and the search fails—even if a valid point exists at the beginning of the array (which, on the circle, is genuinely min_gap away when wrapping). However, because the code fixes end = start + total_length - min_gap and only moves forward, it never explores the wrapped region.

Is this actually a bug here? No—and understanding why is crucial. By trying every point as start and constraining the final point to end = start + total_length - min_gap, the algorithm effectively "linearizes" the circle from each possible starting position. Since one of the k chosen points must be the "first" in clockwise order, iterating all starts guarantees we capture the correct circular arrangement. The pitfall is "fixing" this by adding manual wrap-around logic (e.g., appending coord + total_length duplicates), which double-counts and breaks correctness.

Solution: Trust the "try every start + bounded end" pattern. Do not add wrapped duplicates to perimeter_coords. The boundary check perimeter_coords[next_index] > end is what enforces the wrap-around gap correctly.

end = start + total_length - min_gap   # enforces wrap gap implicitly
# ...
if next_index == len(perimeter_coords) or perimeter_coords[next_index] > end:
    feasible = False   # correct: no need to wrap manually
    break

Pitfall 2: Wrong Binary Search Midpoint Rounding

Because the update is left = mid (not left = mid + 1), you must round the midpoint up:

mid = (left + right + 1) >> 1   # correct

If you mistakenly write mid = (left + right) >> 1 (rounding down) while keeping left = mid, you get an infinite loop when left and right become adjacent (right = left + 1): mid evaluates to left, check passes, left = mid leaves left unchanged, and the loop never terminates.

Solution: Match the rounding direction to the assignment:

left = mid → round up: (left + right + 1) >> 1
right = mid → round down: (left + right) >> 1

Pitfall 3: Misjudging the Manhattan-to-Perimeter Distance Equivalence

The mapping assumes the arc distance along the perimeter equals the Manhattan distance between two boundary points. This is only true on the same edge or adjacent edges within a certain range. For two points on opposite edges, the straight Manhattan distance can be smaller than the perimeter arc.

Example: Points (0, 0) and (side, 0) (bottom corners). Manhattan distance is side. But mapped coordinates are 0 and 4*side - side = 3*side, giving an arc distance of 3*side (or side the short way). The shorter arc here coincidentally matches, but for interior-edge opposite points it may not.

Why the solution still works: This problem's structure (boundary points + maximizing the minimum gap) means that the binding constraint is almost always between nearby points along the perimeter, where arc distance equals Manhattan distance. The greedy spacing naturally avoids clustering, so the dangerous "opposite edge" cases rarely become the minimum.

Solution: Be aware that this equivalence is a problem-specific simplification. If you adapt this code to a variant where opposite-edge distances dominate, you must compute true Manhattan distances rather than relying solely on the 1D arc mapping.

Pitfall 4: Forgetting That Only `k - 1` Jumps Are Needed

A common off-by-one error is looping k times instead of k - 1. The start point counts as the first selected point, so only k - 1 additional points must be placed.

for _ in range(k - 1):   # correct: start is already point #1
    ...

Using range(k) would demand one extra point and incorrectly reject feasible candidates.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of these pictures shows the visit order of a depth-first search?

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering

3464. Maximize the Distance Between Points on a Square

Problem Description

How We Pick the Algorithm

Why Binary Search?

Intuition

Solution Approach

Step 1: Map 2D Boundary Points to a 1D Axis

Step 2: Binary Search on the Answer

Step 3: The check Function (Greedy on a Circle)

Complexity Analysis

Example Walkthrough

Step 1: Map 2D Boundary Points to a 1D Axis

Step 2: Binary Search on the Answer

Step 3: The check(2) Function (Greedy on a Circle)

Back to Binary Search

Why This Is Correct

Solution Implementation

Time and Space Complexity

Common Pitfalls

Pitfall 1: Incorrectly Handling the Wrap-Around with bisect_left

Pitfall 2: Wrong Binary Search Midpoint Rounding

Pitfall 3: Misjudging the Manhattan-to-Perimeter Distance Equivalence

Pitfall 4: Forgetting That Only k - 1 Jumps Are Needed

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings

Step 3: The `check` Function (Greedy on a Circle)

Step 3: The `check(2)` Function (Greedy on a Circle)

Pitfall 1: Incorrectly Handling the Wrap-Around with `bisect_left`

Pitfall 4: Forgetting That Only `k - 1` Jumps Are Needed