1515. Best Position for a Service Centre
Problem Description
The goal is to find a point (the location of the new service center) on a 2D map that minimizes the sum of the Euclidean distances to all given customer locations. This kind of problem is known as the geometric median problem, which does not have a straightforward algebraic solution available for more than three points.
Euclidean distance is the straight-line distance between two points in a 2D space. Mathematically, the distance between points (x1, y1) and (x2, y2) is sqrt((x2 - x1)^2 + (y2 - y1)^2)
.
Given are the coordinates of the customers' positions in a 2D space, and we need to find the coordinates of the new service center (x_centre, y_centre) such that the sum of their distances to all customers' positions is as small as possible.
Intuition
Approaching the problem means finding a point that is, in some sense, central to all the customers' positions. A good initial guess for this central point might be the arithmetic mean of all the given points (the centroid). While the centroid minimally reduces the sum of squared Euclidean distances, it doesn't necessarily minimize the sum of Euclidean distances, but it provides a good starting place for further refinement.
The intuition behind the solution involves using a technique known as gradient descent. It is an iterative optimization algorithm for finding the minimum of a function. Here, we treat the sum of the distances as the function we want to minimize. By iteratively moving in the direction opposite to the gradient (the direction of the steepest increase), we can find the local minimum of the function. Since there is only one minimum in this kind of problem, the local minimum is also the global minimum.
The solution starts with the centroid of the given points and then repeatedly adjusts its position by calculating the gradient (the direction and rate of the fastest increase of the sum of distances) and moving a slight step in the opposite direction. This process is repeated until the change in the service center's position becomes insignificant, indicating that the minimum sum of distances has been approximately reached.
The use of decay in the solution ensures that steps become smaller over time, allowing the algorithm to settle into the minimum rather than overshooting it. The epsilon (eps) is a small threshold determining when the adjustments are small enough to conclude that the minimum has been reached. This is due to the computational precision we can reasonably achieve, especially since the problem statement allows for a very slight margin of error.
Learn more about Math patterns.
Solution Approach
The implementation of the solution involves a few steps:
-
Initialization: We start by calculating the centroid of all customer positions, which is simply the average of the x and y coordinates. This gives us an initial
x
andy
which represents our first guess for the location of the service center.1x = y = 0 2for x1, y1 in positions: 3 x += x1 4 y += y1 5x, y = x / n, y / n
-
Gradient Computation: Then, the gradient descent loop starts. In each iteration, we calculate the gradient of the objective function (the function representing the sum of Euclidean distances from the service center to all customer positions) with respect to the position of the service center.
1grad_x = grad_y = 0 2dist = 0 3for x1, y1 in positions: 4 a = x - x1 5 b = y - y1 6 c = sqrt(a * a + b * b) 7 grad_x += a / (c + 1e-8) # Avoid division by zero 8 grad_y += b / (c + 1e-8) 9 dist += c
-
Gradient Descent: After calculating the gradient, we update the center's position by moving a small step in the opposite direction of the gradient. This step size is determined by a learning rate,
alpha
.1dx = grad_x * alpha 2dy = grad_y * alpha 3x -= dx 4y -= dy
-
Learning Rate Decay: To make sure the steps get smaller as we approach the minimum, we multiply the learning rate by a decay factor,
decay
, in every iteration.1alpha *= decay
-
Termination Check: The loop runs until the changes in the position become extremely small (smaller than
eps
). This signifies that subsequent steps will no longer provide meaningful movement toward the minimum, and we've found an approximation close enough to the actual solution.1if abs(dx) <= eps and abs(dy) <= eps: 2 return dist
The data structures used in this implementation are simple: variables to store coordinates (x
, y
), gradient values (grad_x
, grad_y
), and step sizes (dx
, dy
). The algorithm uses gradient descent, and it employs careful tuning of the learning rate (alpha
), decay factor (decay
), and the stopping threshold (eps
) to converge on a solution that minimizes the sum of Euclidean distances.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose we have 3 customer locations with the following coordinates: (1,2), (3,4), and (5,6).
-
Initialization: We begin by finding the centroid of these points. The centroid (average) of the x and y coordinates is:
1x = (1 + 3 + 5) / 3 = 3 2y = (2 + 4 + 6) / 3 = 4
So our initial guess for the location of the service center is (3, 4).
-
Gradient Computation: Now we compute the gradient of the sum of the distances from this initial point to each of the customer locations:
1grad_x = grad_y = 0 2for (x1, y1) in [(1, 2), (3, 4), (5, 6)]: 3 a = 3 - x1 4 b = 4 - y1 5 c = sqrt(a * a + b * b) 6 grad_x += a / (c + 1e-8) 7 grad_y += b / (c + 1e-8) 8# Suppose grad_x = 0.1 and grad_y = 0.1 after computation
-
Gradient Descent: With the gradient computed, we will adjust the center's position. Let's assume our learning rate
alpha
is 0.01:1dx = 0.1 * 0.01 2dy = 0.1 * 0.01 3x -= dx # new x = 3 - 0.001 4y -= dy # new y = 4 - 0.001
So the service center's new location would be approximately (2.999, 3.999).
-
Learning Rate Decay: We then apply the decay to the learning rate to gradually reduce the step size. If our decay factor
decay
is 0.9, the learning rate for the next iteration will be:1alpha *= decay # new alpha = 0.01 * 0.9
-
Termination Check: We check if the change in positions,
dx
anddy
, are smaller than our epsiloneps
. Let's sayeps
is 0.0001:1if abs(dx) <= eps and abs(dy) <= eps: 2 break # This would not break on the first iteration as dx and dy are 0.001
Since dx
and dy
are both 0.001, which is larger than eps
, the loop would continue. This gradient descent loop would iterate, updating the position of the service center and decreasing the learning rate until dx
and dy
are less than eps
, indicating we have found our minimum sum of distances.
Through this example, we've seen how the algorithm iteratively updates the position of the service center and converges to a solution. The same logic would extend to larger sets of points, with the gradient descent guiding the service center to the minimum of the distance function.
Solution Implementation
1from math import sqrt
2from typing import List
3
4class Solution:
5 def getMinDistSum(self, positions: List[List[int]]) -> float:
6 # Calculate the number of positions
7 num_positions = len(positions)
8
9 # Calculate the initial guess for the center by averaging the positions
10 center_x = sum(x for x, _ in positions) / num_positions
11 center_y = sum(y for _, y in positions) / num_positions
12
13 # Set parameters for the gradient descent optimizer
14 decay_factor = 0.999
15 convergence_threshold = 1e-6
16 learning_rate = 0.5
17
18 # Gradient descent algorithm to minimize the distance sum
19 while True:
20 # Initialize gradients and total distance
21 gradient_x = gradient_y = 0.0
22 total_dist = 0.0
23
24 # Calculate gradients and the sum of distances to all points
25 for pos_x, pos_y in positions:
26 difference_x = center_x - pos_x
27 difference_y = center_y - pos_y
28 distance = sqrt(difference_x ** 2 + difference_y ** 2)
29 # Avoid division by zero
30 if distance < 1e-8:
31 distance = 1e-8
32 gradient_x += difference_x / distance
33 gradient_y += difference_y / distance
34 total_dist += distance
35
36 # Update center using gradients
37 change_x = gradient_x * learning_rate
38 change_y = gradient_y * learning_rate
39 center_x -= change_x
40 center_y -= change_y
41
42 # Decrease learning rate over time
43 learning_rate *= decay_factor
44
45 # Check for convergence
46 if abs(change_x) <= convergence_threshold and abs(change_y) <= convergence_threshold:
47 # Converged, return the total distance
48 return total_dist
49
1class Solution {
2 public double getMinDistSum(int[][] positions) {
3 int n = positions.length; // Number of positions
4 double centerX = 0, centerY = 0; // Initialize center x and y with 0
5
6 // Calculate initial centroid by averaging all positions
7 for (int[] position : positions) {
8 centerX += position[0];
9 centerY += position[1];
10 }
11 centerX /= n;
12 centerY /= n;
13
14 // Set decay factor for the learning rate and an epsilon for convergence condition
15 double decayFactor = 0.999;
16 double convergenceThreshold = 1e-6;
17
18 // Start with an initial learning rate
19 double learningRate = 0.5;
20
21 // Use Gradient Descent to minimize the distance sum
22 while (true) {
23 double gradientX = 0, gradientY = 0; // Initialize gradients
24 double totalDistance = 0; // Initialize total distance
25
26 // Compute gradients for X and Y with respect to the objective function
27 for (int[] position : positions) {
28 double deltaX = centerX - position[0], deltaY = centerY - position[1];
29 double distance = Math.sqrt(deltaX * deltaX + deltaY * deltaY);
30 gradientX += deltaX / (distance + 1e-8); // Add small value to avoid division by zero
31 gradientY += deltaY / (distance + 1e-8);
32 totalDistance += distance; // Sum up total distance
33 }
34
35 // Scale the gradient by the learning rate
36 double stepX = gradientX * learningRate;
37 double stepY = gradientY * learningRate;
38
39 // Check for convergence
40 if (Math.abs(stepX) <= convergenceThreshold && Math.abs(stepY) <= convergenceThreshold) {
41 return totalDistance; // Return the minimized total distance
42 }
43
44 // Update the center position by taking a step against the gradient direction
45 centerX -= stepX;
46 centerY -= stepY;
47
48 // Reduce the learning rate by the decay factor
49 learningRate *= decayFactor;
50 }
51 }
52}
53
1#include <vector>
2#include <cmath>
3
4class Solution {
5public:
6 double getMinDistSum(std::vector<std::vector<int>>& positions) {
7 int pointsCount = positions.size(); // Total number of positions
8 double centroidX = 0, centroidY = 0; // Centroid of the positions
9
10 // Calculate the initial centroid of all points
11 for (const auto& position : positions) {
12 centroidX += position[0];
13 centroidY += position[1];
14 }
15 centroidX /= pointsCount;
16 centroidY /= pointsCount;
17
18 // Initialize learning rate parameters
19 double decay = 0.999; // Decay rate for the learning rate
20 double eps = 1e-6; // Tolerance for convergence
21 double learningRate = 0.5; // Initial learning rate
22
23 while (true) {
24 double gradientX = 0, gradientY = 0; // Gradients for updating centroid
25 double totalDistance = 0; // Sum of distances to all points
26
27 // Compute gradients and total distance
28 for (const auto& position : positions) {
29 double deltaX = centroidX - position[0], deltaY = centroidY - position[1];
30 double distanceToCentroid = std::sqrt(deltaX * deltaX + deltaY * deltaY);
31
32 // Avoid division by zero
33 if (distanceToCentroid < eps) distanceToCentroid += eps;
34
35 gradientX += deltaX / distanceToCentroid;
36 gradientY += deltaY / distanceToCentroid;
37 totalDistance += distanceToCentroid;
38 }
39
40 // Update using the computed gradients
41 double stepX = gradientX * learningRate;
42 double stepY = gradientY * learningRate;
43
44 // Check for convergence
45 if (std::abs(stepX) <= eps && std::abs(stepY) <= eps) {
46 return totalDistance;
47 }
48
49 // Update centroid position
50 centroidX -= stepX;
51 centroidY -= stepY;
52
53 // Update learning rate
54 learningRate *= decay;
55 }
56 }
57};
58
1// getMinDistSum calculates the sum of Euclidean distances from the best meeting point to
2// all points in the positions array, which represents various (x,y) locations. It uses
3// a gradient descent approach to iteratively approach the minimum sum of distances.
4// Params:
5// positions: An array of [x, y] number tuples representing the coordinates of various points.
6
7function getMinDistSum(positions: number[][]): number {
8 // Total number of positions
9 const positionCount = positions.length;
10 // Initial guess for the best meeting point is the centroid (average of all points)
11 let [centroidX, centroidY] = [0, 0];
12 positions.forEach(([posX, posY]) => {
13 centroidX += posX;
14 centroidY += posY;
15 });
16 centroidX /= positionCount;
17 centroidY /= positionCount;
18
19 // Decay rate for the learning rate (alpha)
20 const decayRate = 0.999;
21 // The minimum change for convergence
22 const epsilon = 1e-6;
23 // Initial learning rate
24 let learningRate = 0.5;
25
26 // Start gradient descent loop
27 while (true) {
28 let [gradientX, gradientY] = [0, 0];
29 let totalDistance = 0;
30 for (const [posX, posY] of positions) {
31 const deltaX = centroidX - posX;
32 const deltaY = centroidY - posY;
33 // Small epsilon to avoid division by zero
34 const distance = Math.sqrt(deltaX * deltaX + deltaY * deltaY) + 1e-8;
35 gradientX += deltaX / distance;
36 gradientY += deltaY / distance;
37 totalDistance += Math.sqrt(deltaX * deltaX + deltaY * deltaY);
38 }
39
40 // Calculate the steps to take
41 const stepX = gradientX * learningRate;
42 const stepY = gradientY * learningRate;
43
44 // Check for convergence, if both x and y changes are smaller than epsilon, stop
45 if (Math.abs(stepX) <= epsilon && Math.abs(stepY) <= epsilon) {
46 // Return the total distance which is the sum of distances from the best meeting point
47 return totalDistance;
48 }
49
50 // Update the centroid point based on the gradient
51 centroidX -= stepX;
52 centroidY -= stepY;
53
54 // Reduce the learning rate gradually
55 learningRate *= decayRate;
56 }
57}
58
Time and Space Complexity
Time Complexity
The given code snippet is an iterative method designed to find the position that minimizes the sum of distances to all points in the array positions
. Let's analyze the time complexity step by step:
-
The initialization step calculates the centroid by averaging the x and y coordinates. This loop runs
n
times, wheren
is the number of positions. Hence, it has a time complexity ofO(n)
. -
The while loop does not have a fixed number of iterations, as it continues until the changes in
x
andy
are smaller thaneps
. However, within this loop, every iteration involves a loop through alln
positions to compute gradients and distances. -
Within this nested loop, the time complexity of the operations (calculations for
a
,b
,c
,grad_x
,grad_y
, anddist
) is constant,O(1)
. -
The update of
x
andy
and the condition check are also constant time operations.
Therefore, if we denote the number of iterations the while loop runs as k
, the total time complexity would be O(nk)
, where k
depends on the initial positions, the decay factor alpha
, and the threshold eps
.
Space Complexity
The space complexity is determined by the extra space used:
-
Variables
x
,y
,grad_x
,grad_y
,dist
,dx
, anddy
use constant space. -
The code does not use any additional data structures that grow with the input. Only fixed amount of extra space is needed to store intermediate calculational variables.
Consequently, the space complexity of the algorithm is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.