Minimize Manhattan Distances - Practice Coding Problems

Minimize Manhattan Distances - Problem

Array Math Geometry Sorting Ordered Set Hard

You are given an array points representing integer coordinates of some points on a 2D plane, where points[i] = [x_i, y_i].

The Manhattan distance between two points (x1, y1) and (x2, y2) is defined as |x1 - x2| + |y1 - y2|.

Return the minimum possible value for the maximum distance between any two points by removing exactly one point.

Input & Output

Example 1 — Basic Case

$ Input: points = [[3,10],[5,15],[10,2],[4,4]]

› Output: 12

💡 Note: Remove point [3,10]. The maximum distance among remaining points is between [5,15] and [10,2]: |5-10| + |15-2| = 5 + 13 = 18. However, removing [5,15] gives max distance 12 between [3,10] and [10,2]: |3-10| + |10-2| = 7 + 8 = 15. The optimal is actually 12.

Example 2 — Minimum Size

$ Input: points = [[1,1],[3,3]]

› Output: 0

💡 Note: With only 2 points, removing one leaves just 1 point, so maximum distance is 0.

Example 3 — Three Points

$ Input: points = [[1,1],[1,3],[3,3]]

› Output: 2

💡 Note: Remove [1,1]. Remaining points [1,3] and [3,3] have distance |1-3| + |3-3| = 2. This is optimal.

Constraints

3 ≤ points.length ≤ 10⁵
points[i].length == 2
-10⁸ ≤ points[i][0], points[i][1] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Array of 2D points with Manhattan distance metric

Process

Find optimal point to remove that minimizes maximum distance

Output

Minimum possible maximum distance after removal

Key Takeaway

🎯 Key Insight: Transform coordinates to efficiently identify critical points that could minimize the maximum distance when removed

Asked in

G Google 25 a Amazon 15 M Microsoft 12

The key insight is transforming Manhattan distance to Chebyshev distance using coordinate transformation (x+y, x-y). This reduces the problem to finding extreme points that are candidates for removal. Best approach is coordinate transformation with Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Coordinate Transformation	O(n²)	O(n)	Transform Manhattan distance to Chebyshev distance using coordinate rotation
Brute Force	O(n³)	O(1)	Try removing each point and calculate maximum Manhattan distance for remaining points

Coordinate Transformation — Algorithm Steps

Transform coordinates: (x,y) → (x+y, x-y)
Find points with extreme coordinates in transformed space
Test removing each extreme point and calculate result

Visualization

Tap to expand

Step-by-Step Walkthrough

Transform

Convert (x,y) to (x+y, x-y) coordinates

Find Extremes

Identify points with min/max u and v values

Test Candidates

Remove each extreme point and calculate result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int solution(int points[][2], int n) {
    if (n <= 2) return 0;
    
    // Find extreme points in transformed space
    int minU = INT_MAX, maxU = INT_MIN;
    int minV = INT_MAX, maxV = INT_MIN;
    int minUIdx = 0, maxUIdx = 0, minVIdx = 0, maxVIdx = 0;
    
    for (int i = 0; i < n; i++) {
        int u = points[i][0] + points[i][1];
        int v = points[i][0] - points[i][1];
        
        if (u < minU) { minU = u; minUIdx = i; }
        if (u > maxU) { maxU = u; maxUIdx = i; }
        if (v < minV) { minV = v; minVIdx = i; }
        if (v > maxV) { maxV = v; maxVIdx = i; }
    }
    
    int candidates[4] = {minUIdx, maxUIdx, minVIdx, maxVIdx};
    int numCandidates = 4;
    
    // Remove duplicates
    for (int i = 0; i < numCandidates; i++) {
        for (int j = i + 1; j < numCandidates; j++) {
            if (candidates[i] == candidates[j]) {
                for (int k = j; k < numCandidates - 1; k++) {
                    candidates[k] = candidates[k + 1];
                }
                numCandidates--;
                j--;
            }
        }
    }
    
    int minMaxDist = INT_MAX;
    
    for (int c = 0; c < numCandidates; c++) {
        int skipIdx = candidates[c];
        int maxDist = 0;
        for (int i = 0; i < n; i++) {
            if (i == skipIdx) continue;
            for (int j = i + 1; j < n; j++) {
                if (j == skipIdx) continue;
                int dist = abs_val(points[i][0] - points[j][0]) + abs_val(points[i][1] - points[j][1]);
                if (dist > maxDist) maxDist = dist;
            }
        }
        if (maxDist < minMaxDist) minMaxDist = maxDist;
    }
    
    return minMaxDist;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int points[1000][2];
    int n = 0;
    
    char *token = strtok(line, "[],");
    while (token != NULL && n < 1000) {
        if (strlen(token) > 0 && token[0] != '\n') {
            points[n][0] = atoi(token);
            token = strtok(NULL, "[],");
            if (token != NULL) {
                points[n][1] = atoi(token);
                n++;
            }
        }
        token = strtok(NULL, "[],");
    }
    
    printf("%d\n", solution(points, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Transform points in O(n), then test O(1) candidates each taking O(n²) time

⚠ Quadratic Growth

Space Complexity

O(n)

Store transformed coordinates and track extreme points

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Coordinate Transformation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler