Best Position for a Service Centre - Video Solutions

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.