Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1638. Best Position for a Service Centre

My accepted Python solution to LeetCode problem 1638, Best Position for a Service Centre, running in 107ms.

  • Difficulty: Hard
  • Python
  • Runtime 107ms
  • Memory 17.4MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 107ms, memory 17.4MB, accepted 2025-12-24.

python
class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:
        import math
        
        # Start from centroid
        x = sum(p[0] for p in positions) / len(positions)
        y = sum(p[1] for p in positions) / len(positions)
        
        def total_dist(cx, cy):
            return sum(math.sqrt((cx - px)**2 + (cy - py)**2) for px, py in positions)
        
        # Gradient descent with decreasing step size
        step = 100.0
        
        while step > 1e-7:
            improved = False
            for dx, dy in [(0, step), (0, -step), (step, 0), (-step, 0)]:
                nx, ny = x + dx, y + dy
                if total_dist(nx, ny) < total_dist(x, y):
                    x, y = nx, ny
                    improved = True
                    break
            
            if not improved:
                step /= 2
        
        return total_dist(x, y)

Source