LeetCode 1515 - Best Position for a Service Centre

The problem asks us to find the optimal location for a service center on a 2D map such that the total Euclidean distance

leetcodehardarraymathgeometryrandomized

LeetCode Problem 1515

Difficulty: 🔴 Hard
Topics: Array, Math, Geometry, Randomized

Solution

Problem Understanding

The problem asks us to find the optimal location for a service center on a 2D map such that the total Euclidean distance from the center to all customers is minimized. We are given the coordinates of customers as a list positions, where each element is a 2-element list [x, y]. The goal is to return the minimal sum of Euclidean distances from a point [xcentre, ycentre] to all the given customer positions.

The input constraints are modest: up to 50 customer positions, each with coordinates between 0 and 100. This rules out the need for extreme optimization, but it also suggests that a naive brute-force grid search could be too slow if implemented without care. The solution must also provide precision within 1e-5, so any iterative approximation must converge carefully.

Important edge cases include when all customers are at the same location (the center should coincide with that point), when customers form a line or cluster in one area, and when customers are widely spread across the allowed coordinate space.

Approaches

A brute-force approach would involve searching every possible point on the 2D plane within the bounding rectangle of all customer coordinates. For each candidate point, we would compute the sum of distances to all customers and track the minimum. This guarantees correctness, but the complexity is too high: even discretizing coordinates to 0.01 precision across a 100x100 grid results in 10 million candidate points, which multiplied by 50 distance calculations each is prohibitive.

The key insight is that the sum of Euclidean distances forms a convex function in 2D space. Convexity allows us to use gradient descent or iterative optimization techniques to approximate the minimum efficiently. In this problem, a variant of Weiszfeld's algorithm or simulated annealing / hill climbing works well. We initialize the center at the average of all points and iteratively move it slightly in the direction that reduces the total distance, stopping once changes are smaller than a threshold.

Approach Time Complexity Space Complexity Notes
Brute Force O((range/precision)^2 * n) O(1) Enumerates all possible points on a fine grid; too slow
Gradient Descent / Iterative Optimization O(n * iterations) O(1) Uses convexity; starts at centroid and iteratively improves

Algorithm Walkthrough

  1. Compute an initial estimate of the center by averaging all customer coordinates. This gives a reasonable starting point.
  2. Define a step size (learning rate) that controls how far we move the center in each iteration.
  3. Compute the gradient-like direction: for small perturbations in x and y, calculate whether moving slightly in that direction decreases the total distance.
  4. Move the center in the direction that decreases the distance.
  5. Reduce the step size gradually to refine the approximation and avoid overshooting the minimum.
  6. Repeat steps 3-5 until the improvement in total distance is less than a small threshold (e.g., 1e-6), indicating convergence.

Why it works: Because the sum of Euclidean distances is convex, any local minimum is a global minimum. The iterative process moves the center closer to the optimal point at each step, ensuring convergence to the global minimum with sufficient iterations and a decaying step size.

Python Solution

from typing import List
import math

class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:
        n = len(positions)
        # Start from centroid
        x = sum(p[0] for p in positions) / n
        y = sum(p[1] for p in positions) / n
        
        step = 1.0
        eps = 1e-6
        while step > eps:
            best_dx, best_dy = 0.0, 0.0
            curr_dist = sum(math.hypot(x - px, y - py) for px, py in positions)
            for dx, dy in [(step, 0), (-step, 0), (0, step), (0, -step)]:
                new_x, new_y = x + dx, y + dy
                new_dist = sum(math.hypot(new_x - px, new_y - py) for px, py in positions)
                if new_dist < curr_dist:
                    curr_dist = new_dist
                    best_dx, best_dy = dx, dy
            if best_dx == 0 and best_dy == 0:
                step /= 2
            else:
                x += best_dx
                y += best_dy
        return curr_dist

This code initializes the service center at the centroid of all customer positions. It iteratively explores small moves in four cardinal directions, keeping the move that reduces total distance. If no move improves the distance, the step size is halved to refine the search. This continues until the step size is very small, ensuring convergence to an accurate approximation.

Go Solution

import (
    "math"
)

func getMinDistSum(positions [][]int) float64 {
    n := len(positions)
    x, y := 0.0, 0.0
    for _, p := range positions {
        x += float64(p[0])
        y += float64(p[1])
    }
    x /= float64(n)
    y /= float64(n)
    
    step := 1.0
    eps := 1e-6
    
    for step > eps {
        bestDX, bestDY := 0.0, 0.0
        currDist := 0.0
        for _, p := range positions {
            dx := x - float64(p[0])
            dy := y - float64(p[1])
            currDist += math.Hypot(dx, dy)
        }
        moves := [][2]float64{{step,0},{-step,0},{0,step},{0,-step}}
        for _, m := range moves {
            newX, newY := x+m[0], y+m[1]
            newDist := 0.0
            for _, p := range positions {
                dx := newX - float64(p[0])
                dy := newY - float64(p[1])
                newDist += math.Hypot(dx, dy)
            }
            if newDist < currDist {
                currDist = newDist
                bestDX, bestDY = m[0], m[1]
            }
        }
        if bestDX == 0 && bestDY == 0 {
            step /= 2
        } else {
            x += bestDX
            y += bestDY
        }
    }
    total := 0.0
    for _, p := range positions {
        total += math.Hypot(x-float64(p[0]), y-float64(p[1]))
    }
    return total
}

The Go implementation mirrors the Python logic. Float64 is used for precision, and slices represent customer coordinates. Care is taken to sum distances in floating-point arithmetic.

Worked Examples

Example 1: positions = [[0,1],[1,0],[1,2],[2,1]]

Start at centroid: (0+1+1+2)/4 = 1, (1+0+2+1)/4 = 1. The total distance to all points is exactly 4, and no small move reduces it further. The algorithm converges immediately.

Example 2: positions = [[1,1],[3,3]]

Centroid: (1+3)/2 = 2, (1+3)/2 = 2. Distance to first: sqrt((2-1)^2 + (2-1)^2) = sqrt(2). Distance to second: sqrt((2-3)^2 + (2-3)^2) = sqrt(2). Total = 2.82843, which is minimal.

Complexity Analysis

Measure Complexity Explanation
Time O(n * iterations) Each iteration computes distances to all n points; iterations are small and step decays exponentially
Space O(1) Only a few variables are stored, independent of input size

The time complexity is acceptable due to the small n (<=50) and convergence occurring within a few hundred iterations typically.

Test Cases

# Provided examples
assert abs(Solution().getMinDistSum([[0,1],[1,0],[1,2],[2,1]]) - 4.0) < 1e-5
assert abs(Solution().getMinDistSum([[1,1],[3,3]]) - 2.82843) < 1e-5

# Single customer
assert abs(Solution().getMinDistSum([[0,0]]) - 0.0) < 1e-5

# Two customers in line
assert abs(Solution().getMinDistSum([[0,0],[2,0]]) - 2.0) < 1e-5

# Clustered points
assert abs(Solution().getMinDistSum([[0,0],[0,1],[1,0],[1,1]]) - 4*math.hypot(0.5,0.5)) < 1e-5

# Widely spread points
assert abs(Solution().getMinDistSum([[0,0],[100,100]]) - math.hypot(50,50)*2) < 1e-5
Test Why
Provided examples Valid