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:

1
2
3
4

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:

1
2
3
4

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 <= 50
  • positions[i].length == 2
  • 0 <= 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

   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

  1. Start with a large search area with lower precision (e.g., the whole grid, center at (50, 50)).
  2. Iteratively search a grid of candidate points around the current center, with a given step size (delta).
  3. Update the center to the point with the smallest total distance.
  4. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#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;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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), where delta_0 is the initial search range (e.g., 100), epsilon is the final precision (e.g., 1e-5), and n is the number of positions. For each zoom level, we check a grid of points, and the number of levels is O(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

  1. Start at the centroid (average x and y of all positions).
  2. Try moving in each of the four directions (up, down, left, right) by the current step size.
  3. Move to the best direction if it reduces the total distance.
  4. If no improvement, halve the step size.
  5. Repeat until the step size is very small (e.g., < 1e-6).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#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;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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)), where n is the number of positions, R is the initial search range (e.g., 100), and epsilon is the final precision. Each step checks 4 directions, and the number of steps is O(log(R/epsilon)).
  • 🧺 Space complexity: O(1) (ignoring input), as only a few variables are used for the search.