Skip to main content
Talentd

Best Position for a Service Centre - Solution & Explanation

HardArrayMathGeometryRandomized12 min readAsked at: Citadel
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive several customer coordinates on a 2D plane. The task is to place a service center so that the sum of Euclidean distances from the center to all customers is minimized. Unlike Manhattan-distance problems, the Euclidean metric makes the objective function continuous and non-linear, so typical discrete search strategies do not work directly.

Approach 1: Gradient Descent Optimization (O(n × iterations) time, O(1) space)

The total distance function is continuous across the plane, which allows you to treat the problem as numerical optimization. Start from an initial guess (often the centroid of all points). Compute the gradient of the distance function with respect to x and y, then move the candidate point in the direction that decreases the total distance. After each step, reduce the learning rate to stabilize convergence. Each iteration scans all points and accumulates gradient components, giving O(n) work per step. This approach fits naturally when working with math and geometry optimization problems where the solution lies in continuous space.

The key insight: the minimum occurs where the gradient approaches zero. By repeatedly updating the position using small steps, the algorithm converges toward the geometric median. Precision improves as the step size shrinks. Because the search happens in continuous space rather than over a grid, you avoid exponential brute-force exploration.

Approach 2: Simulated Annealing (O(n × iterations) time, O(1) space)

Simulated annealing treats the coordinate as a candidate solution and randomly explores nearby positions. Start from an initial point (again, the centroid works well). At each step, generate random neighboring positions and compute the change in total distance. If the new position improves the objective, accept it. If it is worse, accept it with a probability controlled by a temperature parameter. Gradually cool the temperature so the search transitions from exploration to exploitation.

This randomized search helps escape local minima and works well for continuous optimization problems. Each candidate evaluation requires summing distances to all points, so the cost per iteration is O(n). The approach connects to randomized algorithms and still relies heavily on geometric distance calculations from the array of coordinates.

Recommended for interviews: Gradient descent is typically preferred. It demonstrates understanding of continuous optimization and geometric median concepts while remaining relatively simple to implement. Simulated annealing is useful when discussing randomized optimization strategies, but interviewers usually expect the deterministic gradient-descent style search. Showing both indicates strong problem-solving depth.

Approach 1: Approach 1: Gradient Descent Optimization

We employ a gradient descent method to iteratively adjust the position of the service center. This method uses the gradient of the loss function (sum of Euclidean distances) to navigate towards a local minimum.

The function to minimize is nonlinear and depends on the current position, so by iteratively updating the center position in the direction opposite to the gradient, we can find a position that minimizes the total distance to all customer points.

  • Initially set the center to the average of the given positions.
  • Iteratively adjust the center's position by probing small steps in each direction.
  • Reduce the step size over iterations to ensure convergence.
  • Continue until the adjustments become negligible, indicating convergence to a local minimum.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n * k * m) where n is the number of points, k is a constant number of iterations, and m is the number of gradient directions checked per iteration.

Space Complexity: O(1) as we only use a fixed amount of auxiliary variables.

Try this approach in the editor →

Approach 2: Approach 2: Simulated Annealing

Simulated annealing is a probabilistic technique to approximate the global minimum of a cost function. By gradually 'cooling' the algorithm's temperature parameter, it switches from exploration to exploitation, allowing it to escape local minima in search of a global minimum.

We exploit this property to determine the optimal service center location by considering minor random fluctuations and decaying acceptance probability over iterations.

  • Initialize the temperature and calculate the initial center as the mean of positions.
  • Iterably perform small, random adjustments and evaluate their impact on total distance.
  • Adjust temperature allowing for occasionally accepting worse solutions to enable the algorithm to ‘jump’ out of local minima.
  • As the temperature reduces, the algorithm converges to a solution held to be a global minimum.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(n), as each temperature adjustment involves reassessing distances to all customers.

Space Complexity: O(1), given the fixed storage of current coordinate estimates and immediate variable use.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Gradient Descent Optimization

Time Complexity: O(n * k * m) where n is the number of points, k is a constant number of iterations, and m is the number of gradient directions checked per iteration.

Space Complexity: O(1) as we only use a fixed amount of auxiliary variables.

Approach 2: Simulated Annealing

Time Complexity: O(n), as each temperature adjustment involves reassessing distances to all customers.

Space Complexity: O(1), given the fixed storage of current coordinate estimates and immediate variable use.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Gradient Descent OptimizationO(n × iterations)O(1)Deterministic continuous optimization; typical interview-friendly solution
Simulated AnnealingO(n × iterations)O(1)When randomized search helps escape local minima or when discussing probabilistic optimization

Video Solution

1515. Best Position for a Service Centre (Leetcode Hard) • Programming Live with Larry • 1,959 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Best Position for a Service Centre easy or hard?
Best Position for a Service Centre is classified as Hard because it requires continuous optimization rather than standard discrete algorithms. Understanding geometric median concepts and implementing iterative convergence correctly makes it challenging for many candidates.
Best Position for a Service Centre Python/Java solution
Python and Java implementations typically use iterative optimization such as gradient descent or simulated annealing. Each iteration computes Euclidean distances using sqrt calculations and updates the candidate coordinates until the movement step becomes very small.
How to solve Best Position for a Service Centre in O(n)?
A strict O(n) algorithm is not practical because the solution requires iterative numerical optimization. Each iteration processes all points in O(n), and the algorithm converges after a fixed number of iterations. This results in O(n × iterations) overall time.
What is the best approach for Best Position for a Service Centre?
Gradient descent optimization is the most common approach. It treats the objective function (sum of Euclidean distances) as a continuous surface and iteratively moves the candidate point toward the minimum. Each iteration computes gradients across all points, giving O(n × iterations) time and O(1) space.
Is Best Position for a Service Centre asked at Google/Amazon/Meta?
This problem reflects concepts commonly discussed in interviews at companies like Google and Meta, especially when evaluating knowledge of geometry optimization and numerical methods. Variants related to geometric median and facility location sometimes appear in advanced interview rounds.
What data structure is used in Best Position for a Service Centre?
The primary structure is an array of coordinate pairs representing customer positions. The solution relies more on geometric distance calculations and numerical optimization than on complex data structures.
What is the time complexity of Best Position for a Service Centre?
Most practical solutions run in O(n × iterations) time because each optimization step evaluates the distance from the candidate point to all n locations. Space complexity is O(1) since only the current coordinates and distance sums are stored.

Ready to solve this problem?

Practice Best Position for a Service Centre with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays