Best Position for a Service Centre
HardUpdated: Aug 1, 2025
Practice on:
Problem
A delivery company wants to build a new service center in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new center in a position such that the sum of the euclidean distances to all customers is minimum.
Given an array positions where positions[i] = [xi, yi] is the position of the ith customer on the map, return the minimum sum of the euclidean distances to all customers.
In other words, you need to choose the position of the service center [xcentre, ycentre] such that the following formula is minimized:
Answers within 10-5 of the actual value will be accepted.
Examples
Example 1:
Input:
positions = [[0,1],[1,0],[1,2],[2,1]]
Output:
4.00000
Explanation: As shown, you can see that choosing [xcentre, ycentre] = [1, 1] will make the distance to each customer = 1, the sum of all distances is 4 which is the minimum possible we can achieve.
Example 2:
Input:
positions = [[1,1],[3,3]]
Output:
2.82843
Explanation: The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843
Constraints
1 <= positions.length <= 50positions[i].length == 20 <= xi, yi <= 100
Variation of Problem - Best Position for Reddit Offline Kiosk Problem
Reddit is so successful online, that it has decided to open an offline kiosk for people to get their physical front page of the internet - now we just need to decide where to build it. Fortunately we have already located the perfect city to put our first test kiosk, and like all cities, it happens to be a perfect grid. We also happen to know the locations of all of our happy customers as intersections on the grid. Given this customer data, what is the best place to put our kiosk?
Here is an ascii grid demonstrating this problem. Streets are lines, and locations of customers are smiley faces. The asterisk is an example place for a kiosk on the grid.
0 1 2 3 4 5 6 7 8
0+--+--+--+--+--+--+--+--+
| | | | | | | | |
1+--+--+--+--+--+--+--+--+
| | | | | | | | |
2+--+--☻--+--+--+--+--☻--+
| | | | | | | | |
3+--+--+--+--☻--+--+--+--+
| | | | | | | | |
4+--+--+--+--+-[*]-+--+--+
| | | | | | | | |
5+--+--+--☻--+--+--+--+--+
| | | | | | | | |
6+--+--+--+--+--+--+--+--+
| | | | | | | | |
7+--+--☻--+--+--+--+--+--+
| | | | | | | | |
8+--+--+--+--+--+--+--+--+
Input 1 (locations):
{(2,2), (7,2), (4,3), (3,5), (2,7)}
Output 1 (any optimal location):
(3,3)
Input 2 (locations):
[(2, 2), (7, 2), (3, 4), (3, 5), (2, 7)]
Output 2 (any optimal location):
(4,3)
Note: there might be more than one optimal solutions, your program can return any one of them.
Source - [8], [9]
Solution
The math solution for this problem is to find the geometric median, which can be done using the Weiszfeld's algorithm. But we can use approximation solutiont to solve this and Leetcode will accept it. I believe that Leetcode did this on purpose so non-math solutions are accepted during the contest.
Method 1 – Grid Search Approximation (Zoom-In Heuristic)
Intuition
The optimal position to minimize the sum of Euclidean distances to all points is the geometric median. There is no closed-form solution for the geometric median in 2D, but we can approximate it efficiently.
The idea is to start with a large search area and iteratively "zoom in" on the region with the smallest total distance, reducing the search step each time. This is similar to a multi-resolution grid search or hill climbing, and works well for this problem's constraints.
Approach
- Start with a large search area with lower precision (e.g., the whole grid, center at (50, 50)).
- Iteratively search a grid of candidate points around the current center, with a given step size (
delta). - Update the center to the point with the smallest total distance.
- Reduce the step size (zoom in) and repeat until the step is very small (e.g., < 1e-5). Once get the closest point, we search around this point with higher precision.
This process efficiently narrows down to a point that is very close to the true geometric median.
Summary:
- Search a big area with low precision
- Zoom in on the best region with higher precision
Code
C++
#include <vector>
#include <cmath>
using namespace std;
class Solution {
public:
double getMinDistSum(vector<vector<int>>& positions) {
const double TGT_DELTA = 1e-5;
double ans = 1e18, centerX = 50, centerY = 50, delta = 50;
double minX = centerX, minY = centerY;
int zoom = 5;
while (delta >= TGT_DELTA) {
for (double x = centerX - delta; x <= centerX + delta; x += delta / zoom) {
for (double y = centerY - delta; y <= centerY + delta; y += delta / zoom) {
double dist = 0;
for (auto& p : positions)
dist += hypot(p[0] - x, p[1] - y);
if (dist < ans) {
ans = dist;
minX = x;
minY = y;
}
}
}
centerX = minX;
centerY = minY;
delta /= zoom;
}
return ans;
}
};
Go
import "math"
func getMinDistSum(positions [][]int) float64 {
tgtDelta := 1e-5
ans := 1e18
centerX, centerY, delta := 50.0, 50.0, 50.0
minX, minY := centerX, centerY
zoom := 5.0
for delta >= tgtDelta {
for x := centerX - delta; x <= centerX + delta; x += delta / zoom {
for y := centerY - delta; y <= centerY + delta; y += delta / zoom {
dist := 0.0
for _, p := range positions {
dist += math.Hypot(float64(p[0])-x, float64(p[1])-y)
}
if dist < ans {
ans = dist
minX, minY = x, y
}
}
}
centerX, centerY = minX, minY
delta /= zoom
}
return ans
}
Java
class Solution {
public double getMinDistSum(int[][] positions) {
final double TGT_DELTA = 1e-5;
double ans = Double.MAX_VALUE;
double centerX = 50, centerY = 50, delta = 50;
double minX = centerX, minY = centerY;
int zoom = 5;
while (delta >= TGT_DELTA) {
for (double x = centerX - delta; x <= centerX + delta; x += delta / zoom) {
for (double y = centerY - delta; y <= centerY + delta; y += delta / zoom) {
double dist = 0;
for (int[] p : positions)
dist += Math.hypot(p[0] - x, p[1] - y);
if (dist < ans) {
ans = dist;
minX = x;
minY = y;
}
}
}
centerX = minX;
centerY = minY;
delta /= zoom;
}
return ans;
}
}
Kotlin
class Solution {
fun getMinDistSum(positions: Array<IntArray>): Double {
val tgtDelta = 1e-5
var ans = 1e18
var centerX = 50.0; var centerY = 50.0; var delta = 50.0
var minX = centerX; var minY = centerY
val zoom = 5.0
while (delta >= tgtDelta) {
var x = centerX - delta
while (x <= centerX + delta) {
var y = centerY - delta
while (y <= centerY + delta) {
var dist = 0.0
for (p in positions) dist += kotlin.math.hypot(p[0] - x, p[1] - y)
if (dist < ans) {
ans = dist; minX = x; minY = y
}
y += delta / zoom
}
x += delta / zoom
}
centerX = minX; centerY = minY; delta /= zoom
}
return ans
}
}
Python
import math
class Solution:
def getMinDistSum(self, positions: list[list[int]]) -> float:
tgt_delta = 1e-5
ans = float('inf')
center_x, center_y, delta = 50.0, 50.0, 50.0
min_x, min_y = center_x, center_y
zoom = 5
while delta >= tgt_delta:
x = center_x - delta
while x <= center_x + delta:
y = center_y - delta
while y <= center_y + delta:
dist = sum(math.hypot(p[0] - x, p[1] - y) for p in positions)
if dist < ans:
ans = dist
min_x, min_y = x, y
y += delta / zoom
x += delta / zoom
center_x, center_y = min_x, min_y
delta /= zoom
return ans
Rust
impl Solution {
pub fn get_min_dist_sum(positions: Vec<Vec<i32>>) -> f64 {
let tgt_delta = 1e-5;
let mut ans = 1e18;
let (mut center_x, mut center_y, mut delta) = (50.0, 50.0, 50.0);
let (mut min_x, mut min_y) = (center_x, center_y);
let zoom = 5.0;
while delta >= tgt_delta {
let mut x = center_x - delta;
while x <= center_x + delta {
let mut y = center_y - delta;
while y <= center_y + delta {
let mut dist = 0.0;
for p in &positions {
dist += ((p[0] as f64 - x).hypot(p[1] as f64 - y));
}
if dist < ans {
ans = dist;
min_x = x;
min_y = y;
}
y += delta / zoom;
}
x += delta / zoom;
}
center_x = min_x;
center_y = min_y;
delta /= zoom;
}
ans
}
}
TypeScript
class Solution {
getMinDistSum(positions: number[][]): number {
let tgtDelta = 1e-5;
let ans = 1e18;
let centerX = 50, centerY = 50, delta = 50;
let minX = centerX, minY = centerY;
let zoom = 5;
while (delta >= tgtDelta) {
for (let x = centerX - delta; x <= centerX + delta; x += delta / zoom) {
for (let y = centerY - delta; y <= centerY + delta; y += delta / zoom) {
let dist = 0;
for (const p of positions)
dist += Math.hypot(p[0] - x, p[1] - y);
if (dist < ans) {
ans = dist;
minX = x;
minY = y;
}
}
}
centerX = minX;
centerY = minY;
delta /= zoom;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O((delta_0/epsilon)^2 * n), wheredelta_0is the initial search range (e.g., 100),epsilonis the final precision (e.g., 1e-5), andnis the number of positions. For each zoom level, we check a grid of points, and the number of levels isO(log(delta_0/epsilon)). - 🧺 Space complexity:
O(1)(ignoring input), as only a few variables are used for the search.
Method 2 – Hill Climbing (Modified Binary Search)
Intuition
This method uses a hill climbing or greedy local search approach. We start from an initial guess (the centroid/average of all points), and iteratively move in the direction (north, south, east, west) that most reduces the total distance. If no direction improves the result, we reduce the step size and repeat, until the step is very small.
This is a fast and practical way to approximate the geometric median, and converges quickly for small input sizes.
Approach
- Start at the centroid (average x and y of all positions).
- Try moving in each of the four directions (up, down, left, right) by the current step size.
- Move to the best direction if it reduces the total distance.
- If no improvement, halve the step size.
- Repeat until the step size is very small (e.g., < 1e-6).
Code
C++
#include <vector>
#include <cmath>
using namespace std;
class Solution {
public:
double getMinDistSum(vector<vector<int>>& positions) {
const double MIN_STEP = 1e-6;
const int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
double cx = 0, cy = 0;
int n = positions.size();
for (auto& p : positions) { cx += p[0]; cy += p[1]; }
cx /= n; cy /= n;
auto totalDist = [&](double x, double y) {
double d = 0;
for (auto& p : positions) d += hypot(p[0] - x, p[1] - y);
return d;
};
double step = 50.0, ans = totalDist(cx, cy);
while (step > MIN_STEP) {
bool moved = false;
for (int d = 0; d < 4; ++d) {
double nx = cx + dirs[d][0] * step, ny = cy + dirs[d][1] * step;
double nd = totalDist(nx, ny);
if (nd < ans) {
ans = nd; cx = nx; cy = ny; moved = true;
}
}
if (!moved) step /= 2;
}
return ans;
}
};
Go
import "math"
func getMinDistSum(positions [][]int) float64 {
minStep := 1e-6
dirs := [][2]float64{{-1,0},{1,0},{0,-1},{0,1}}
n := float64(len(positions))
cx, cy := 0.0, 0.0
for _, p := range positions { cx += float64(p[0]); cy += float64(p[1]) }
cx /= n; cy /= n
totalDist := func(x, y float64) float64 {
d := 0.0
for _, p := range positions { d += math.Hypot(float64(p[0])-x, float64(p[1])-y) }
return d
}
step := 50.0; ans := totalDist(cx, cy)
for step > minStep {
moved := false
for _, dir := range dirs {
nx, ny := cx+dir[0]*step, cy+dir[1]*step
nd := totalDist(nx, ny)
if nd < ans {
ans = nd; cx = nx; cy = ny; moved = true
}
}
if !moved { step /= 2 }
}
return ans
}
Java
class Solution {
public double getMinDistSum(int[][] positions) {
final double MIN_STEP = 1e-6;
final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
double cx = 0, cy = 0;
int n = positions.length;
for (int[] pos : positions) { cx += pos[0]; cy += pos[1]; }
cx /= n; cy /= n;
double step = 50.0;
double ans = totalDistance(positions, cx, cy);
while (step > MIN_STEP) {
boolean moved = false;
for (int[] dir : DIRS) {
double nx = cx + dir[0] * step, ny = cy + dir[1] * step;
double nd = totalDistance(positions, nx, ny);
if (nd < ans) {
ans = nd; cx = nx; cy = ny; moved = true;
}
}
if (!moved) step /= 2;
}
return ans;
}
private double totalDistance(int[][] positions, double x, double y) {
double d = 0;
for (int[] pos : positions) d += Math.hypot(pos[0] - x, pos[1] - y);
return d;
}
}
Kotlin
class Solution {
fun getMinDistSum(positions: Array<IntArray>): Double {
val minStep = 1e-6
val dirs = arrayOf(
doubleArrayOf(-1.0, 0.0), doubleArrayOf(1.0, 0.0),
doubleArrayOf(0.0, -1.0), doubleArrayOf(0.0, 1.0)
)
var cx = 0.0; var cy = 0.0
for (p in positions) { cx += p[0]; cy += p[1] }
cx /= positions.size; cy /= positions.size
var step = 50.0
var ans = totalDist(positions, cx, cy)
while (step > minStep) {
var moved = false
for (dir in dirs) {
val nx = cx + dir[0] * step
val ny = cy + dir[1] * step
val nd = totalDist(positions, nx, ny)
if (nd < ans) {
ans = nd; cx = nx; cy = ny; moved = true
}
}
if (!moved) step /= 2
}
return ans
}
private fun totalDist(positions: Array<IntArray>, x: Double, y: Double): Double {
var d = 0.0
for (p in positions) d += kotlin.math.hypot(p[0] - x, p[1] - y)
return d
}
}
Python
import math
class Solution:
def getMinDistSum(self, positions: list[list[int]]) -> float:
min_step = 1e-6
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
n = len(positions)
cx = sum(p[0] for p in positions) / n
cy = sum(p[1] for p in positions) / n
def total_dist(x, y):
return sum(math.hypot(p[0] - x, p[1] - y) for p in positions)
step = 50.0
ans = total_dist(cx, cy)
while step > min_step:
moved = False
for dx, dy in dirs:
nx, ny = cx + dx * step, cy + dy * step
nd = total_dist(nx, ny)
if nd < ans:
ans = nd; cx = nx; cy = ny; moved = True
if not moved:
step /= 2
return ans
Rust
impl Solution {
pub fn get_min_dist_sum(positions: Vec<Vec<i32>>) -> f64 {
let min_step = 1e-6;
let dirs = [(-1.0,0.0),(1.0,0.0),(0.0,-1.0),(0.0,1.0)];
let n = positions.len() as f64;
let mut cx = positions.iter().map(|p| p[0] as f64).sum::<f64>() / n;
let mut cy = positions.iter().map(|p| p[1] as f64).sum::<f64>() / n;
let total_dist = |x: f64, y: f64| -> f64 {
positions.iter().map(|p| ((p[0] as f64 - x).hypot(p[1] as f64 - y))).sum()
};
let mut step = 50.0;
let mut ans = total_dist(cx, cy);
while step > min_step {
let mut moved = false;
for (dx, dy) in dirs.iter() {
let nx = cx + dx * step;
let ny = cy + dy * step;
let nd = total_dist(nx, ny);
if nd < ans {
ans = nd; cx = nx; cy = ny; moved = true;
}
}
if !moved { step /= 2.0; }
}
ans
}
}
TypeScript
class Solution {
getMinDistSum(positions: number[][]): number {
const minStep = 1e-6;
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
const n = positions.length;
let cx = positions.reduce((s, p) => s + p[0], 0) / n;
let cy = positions.reduce((s, p) => s + p[1], 0) / n;
function totalDist(x: number, y: number): number {
return positions.reduce((acc, p) => acc + Math.hypot(p[0] - x, p[1] - y), 0);
}
let step = 50.0;
let ans = totalDist(cx, cy);
while (step > minStep) {
let moved = false;
for (const [dx, dy] of dirs) {
const nx = cx + dx * step, ny = cy + dy * step;
const nd = totalDist(nx, ny);
if (nd < ans) {
ans = nd; cx = nx; cy = ny; moved = true;
}
}
if (!moved) step /= 2;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n * log(R/epsilon)), wherenis the number of positions,Ris the initial search range (e.g., 100), andepsilonis the final precision. Each step checks 4 directions, and the number of steps isO(log(R/epsilon)). - 🧺 Space complexity:
O(1)(ignoring input), as only a few variables are used for the search.