1515. Best Position for a Service Centre

HardGeometryMathRandomized
Leetcode Link

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:

  1. 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 and y 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
  2. 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
  3. 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
  4. 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
  5. 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 Evaluator

Example 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).

  1. 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).

  2. 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
  3. 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).

  4. 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
  5. Termination Check: We check if the change in positions, dx and dy, are smaller than our epsilon eps. Let's say eps 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, where n is the number of positions. Hence, it has a time complexity of O(n).

  • The while loop does not have a fixed number of iterations, as it continues until the changes in x and y are smaller than eps. However, within this loop, every iteration involves a loop through all n 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, and dist) is constant, O(1).

  • The update of x and y 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, and dy 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?


Recommended Readings

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.