Abstract / Summary

Choose a position among given points to minimize the total distance to all points.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 36% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Geometry
• Math
• Randomized

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the geometric problem of finding a point that minimizes the sum of Euclidean distances to a set of given positions. It adopts a stochastic refinement strategy that starts from the centroid of the points and iteratively narrows the search region while sampling candidate locations. The algorithm terminates when the uncertainty of the search area falls below a very small threshold, guaranteeing a result with high precision.

Initialization

The first logical block computes the centroid of the input points, which serves as a strong initial guess for the optimal location. The code aggregates the x- and y-coordinates of all positions, divides each sum by the number of points, and stores the result in variables x and y.

x = y = 0
for p in positions:
    x += p[0]
    y += p[1]
x /= len(positions)
y /= len(positions)

By using the arithmetic mean, the algorithm leverages the fact that the centroid often lies close to the true minimizer, especially when the points are uniformly distributed.

Distance Computation

A nested helper function dist evaluates the total distance from any candidate point (x, y) to all input positions. It iterates over the list, computes the Euclidean distance for each point using the square root of the squared differences, and accumulates the sum.

def dist(x, y):
    s = 0
    for p in positions:
        s += sqrt((p[0] - x)**2 + (p[1] - y)**2)
    return s

Encapsulating this logic in a dedicated function keeps the main loop concise and allows repeated distance evaluations without duplicating code.

Stochastic Search Loop

The core of the algorithm is a while-loop that progressively reduces an uncertainty parameter, which defines the radius of random perturbations around the current best estimate. Inside the loop, the algorithm records the current best coordinates and distance, then performs a fixed number of random trials (guesses). For each trial, it draws offsets dx and dy uniformly from the interval [-uncertainty, +uncertainty], evaluates the distance at the perturbed location, and updates the best candidate if a lower total distance is found.

uncertainty = 10
guesses = 100
while uncertainty > 10**-12:
    bestx = x
    besty = y
    best  = dist(bestx, besty)
    for _ in range(guesses):
        dx = x + uniform(-uncertainty, +uncertainty)
        dy = y + uniform(-uncertainty, +uncertainty)
        current = dist(dx, dy)
        if best > current:
            best = current
            bestx = dx
            besty = dy
    x = bestx
    y = besty
    uncertainty *= 0.75

After completing the inner sampling, the algorithm adopts the best found coordinates as the new center and contracts the uncertainty by multiplying it by 0.75. This geometric decay continues until the uncertainty drops below 10⁻¹², at which point the loop exits and the final distance is returned.

return dist(x, y)

Edge Cases

The design implicitly handles several scenarios without additional branching. When the input consists of a single point, the centroid coincides with that point, and the distance function immediately returns zero, causing the loop to converge instantly. If multiple points share identical coordinates, the centroid calculation naturally reflects that redundancy, and the distance evaluation correctly aggregates zero contributions for overlapping points. The stochastic search accommodates clusters of points that are tightly packed, as the decreasing uncertainty quickly hones in on the dense region. Conversely, for widely dispersed points, the initial large uncertainty allows the algorithm to explore a broad area before focusing on the region that yields the minimal sum of distances.

Performance Optimizations

The algorithm incorporates several practical optimizations that enhance its efficiency. Starting from the centroid reduces the number of random iterations needed to approach the optimum, because the initial guess is already close to the solution for many distributions. The fixed number of random samples per iteration (guesses = 100) provides a balance between exploration and computational cost, avoiding excessive evaluations while still offering sufficient coverage of the search space. The geometric reduction of the uncertainty (uncertainty *= 0.75) ensures rapid convergence: each iteration shrinks the search radius, leading to fewer required iterations to reach the precision threshold. By reusing the best coordinates from the previous iteration as the new center, the algorithm avoids resetting the search region, thereby preserving progress made in earlier steps. Finally, the distance function is called only when necessary-once for the current best and once per random trial-preventing redundant calculations. These choices collectively yield a method that converges quickly to a high-precision solution while keeping the number of expensive square-root operations manageable.

Imagine there are several toys scattered across a flat rug and the goal is to find a single spot on the floor where it is as easy as possible for someone to reach all of the toys. This code acts like a little explorer searching for that special spot.

First, the explorer finds the very middle of all the toys by averaging where they are located. This gives the search a great place to start. Because the explorer wants to be precise, it picks a starting area around this middle point.

Inside the loop, the explorer acts like it is looking for a hidden treasure. It takes random steps in different directions within its current area to see if it can find a spot where the total distance to all the toys gets shorter. If a new spot is indeed better, the explorer moves there.

After checking a hundred of these random spots, the explorer decides that this new spot is the target. Then, it makes its search area smaller and smaller, zooming in with more focus, just like a camera lens getting a sharper picture. Following this process of checking random spots and zooming in, the explorer eventually settles on the best position where the combined distance to all the toys is as small as it can possibly be.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++			Python	Java			TS
	WalkCCC	C++			Python	Java
	leetcode.ca	C++			Python	Java		Go	TS
	Progiez	C++			Python	Java
github	black-shadows	C++
	charles-wangkai					Java
	everthis		JS
	fsq				Python
	JoshCrozier		JS
	keineahnung2345	C++
	martianoff			Scala
	suxrobGM						C#
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	Python
JoshCrozier	JavaScript
keineahnung2345	C++
martianoff	Scala
suxrobGM	C#

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality