Choose K pickup locations minimizing L1 distance

Q: Choose K pickup locations minimizing L1 distance

This question evaluates facility-location and spatial optimization skills under the Manhattan (L1) metric, testing algorithm design, combinatorial optimization, and handling geometric data.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Coding: K Shuttle Pickup Locations (L1)

You are given the coordinates of N people on a 2D grid. You want to open K shuttle pickup locations (pickup points) so that the sum of Manhattan (L1) distances from each person to their nearest pickup location is minimized.

Input

An integer N (number of people).
An array points of length N , where points[i] = (xi, yi) are integer coordinates.
An integer K (number of pickup locations).

Output

Return the minimum possible total L1 distance :

$\sum_{i=1}^{N} \min_{j=1..K} (|x_i - X_j| + |y_i - Y_j|)$

where $(X_j, Y_j)$ are the chosen pickup locations.

Clarifications / assumptions (state in your solution)

Are pickup locations required to be at integer coordinates?
Are pickup locations required to be chosen from existing people’s coordinates, or can they be anywhere?

Constraints (you may assume)

Provide an algorithm appropriate for interview constraints (e.g., N up to a few thousand, K up to N).