Best Position for a Service Centre
HardPrompt
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.
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach treats the problem as finding the minimum point on a 2D surface. We start at an arbitrary point (e.g., the center of the coordinate space [50, 50]) and iteratively try to move to a neighboring point with a lower total distance. If we find a better neighbor, we move there. If all neighbors are worse, it means we are at a local minimum for the current step size. We then reduce the step size to explore the vicinity of the current point more finely. This process is repeated until the step size becomes smaller than the required precision.
Algorithm
- Initialize the service center position
(x, y)to a starting point, for instance, the center of the bounding box(50.0, 50.0). - Initialize a
stepsize, for example,50.0. - Calculate the initial minimum distance
min_distfor the starting(x, y). - Define the directions to check:
(0, 1),(0, -1),(1, 0),(-1, 0). - Loop while
stepis greater than a small epsilon (e.g.,1e-7):- Repeatedly search for a better point at the current step size by checking the four cardinal directions.
- If a neighbor
(new_x, new_y)offers a smaller total distance, move the current point to this neighbor(x, y) = (new_x, new_y)and continue searching from there. - If no neighbor offers improvement, break the inner search loop.
- Reduce the step size, e.g.,
step /= 2.
- Return the final
min_dist.
Walkthrough
The core idea is to perform a local search on a grid. We start with a large step size and a candidate center point. We explore the neighbors of this point (up, down, left, right). If any neighbor results in a smaller sum of Euclidean distances, we move our candidate center to that neighbor and repeat the exploration from the new point. If no neighbor offers improvement, we've found the best point for the current step size. We then shrink the step size (e.g., by half) and repeat the process. This allows us to first find the general area of the minimum and then zoom in to find a more precise location. The process terminates when the step size is negligibly small. Since the objective function is convex, this hill-climbing method is guaranteed to find the global minimum.
class Solution { public double getMinDistSum(int[][] positions) { double current_x = 50.0; double current_y = 50.0; double step = 50.0; int[] dx = {0, 0, 1, -1}; int[] dy = {1, -1, 0, 0}; double minTotalDist = calculateTotalDistance(current_x, current_y, positions); while (step > 1e-7) { boolean movedInIteration = true; while(movedInIteration) { movedInIteration = false; for (int i = 0; i < 4; i++) { double next_x = current_x + step * dx[i]; double next_y = current_y + step * dy[i]; double dist = calculateTotalDistance(next_x, next_y, positions); if (dist < minTotalDist) { minTotalDist = dist; current_x = next_x; current_y = next_y; movedInIteration = true; } } } step /= 2.0; } return minTotalDist; } private double calculateTotalDistance(double x, double y, int[][] positions) { double totalDist = 0; for (int[] pos : positions) { totalDist += Math.sqrt(Math.pow(x - pos[0], 2) + Math.pow(y - pos[1], 2)); } return totalDist; }}Complexity
Time
O(N * K) where N is the number of customer positions and K is the total number of steps taken. The number of steps K depends on the initial position, the step reduction factor, and the geometry of the points. It's generally larger than for more sophisticated methods.
Space
O(1) extra space, besides the storage for the input.
Trade-offs
Pros
Relatively simple to understand and implement.
Guaranteed to find the global minimum because the objective function is convex.
Cons
Can be slow to converge if the starting point is far from the minimum or if the function's landscape forms a long, narrow valley.
It only explores four directions at each step, which is less efficient than moving along the true gradient.
Solutions
Solution
class Solution {public double getMinDistSum(int[][] positions) { int n = positions.length; double x = 0, y = 0; for (int[] p : positions) { x += p[0]; y += p[1]; } x /= n; y /= n; double decay = 0.999; double eps = 1 e - 6; double alpha = 0.5; while (true) { double gradX = 0, gradY = 0; double dist = 0; for (int[] p : positions) { double a = x - p[0], b = y - p[1]; double c = Math.sqrt(a * a + b * b); gradX += a / (c + 1 e - 8); gradY += b / (c + 1 e - 8); dist += c; } double dx = gradX * alpha, dy = gradY * alpha; if (Math.abs(dx) <= eps && Math.abs(dy) <= eps) { return dist; } x -= dx; y -= dy; alpha *= decay; } }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.