Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: Minimize Manhattan Distances

Understand how to minimize the maximum Manhattan distance between points in a 2D plane by removing exactly one point. Explore the role of coordinate sums and differences in simplifying the distance calculation. Learn to identify candidate points based on extreme values, enabling efficient removal without brute forcing every possibility. This lesson also covers an O(n) time and O(1) space solution to optimize large datasets.

We'll cover the following...

Statement

You are given an array, points, where each element in points[i] =[xj,yi]= [x_j, y_i] represents the integer coordinates of a point in a 2D plane. The distance between any two points is defined as the Manhattan distanceThe Manhattan distance between two cells (x1, y1) and (x2, y2) is |x_1 - x_2| + |y_1 - y_2|..

Your task is to determine and return the smallest possible value for the maximum distance between any two points after removing exactly one point from the array.

Constraints:

  • 3≤3 \leq points.length ≤103\leq 10^3 ...