A delivery company wants to build a new service center in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new center in a position such that the sum of the euclidean distances to all customers is minimum.
Given an array positions where positions[i] = [xi, yi] is the position of the ith customer on the map, return the minimum sum of the euclidean distances to all customers.
In other words, you need to choose the position of the service center [xcentre, ycentre] such that the following formula is minimized:
Answers within 10-5 of the actual value will be accepted.
Example 1:
Input: positions = [[0,1],[1,0],[1,2],[2,1]] Output: 4.00000 Explanation: As shown, you can see that choosing [xcentre, ycentre] = [1, 1] will make the distance to each customer = 1, the sum of all distances is 4 which is the minimum possible we can achieve.
Example 2:
Input: positions = [[1,1],[3,3]] Output: 2.82843 Explanation: The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843
Constraints:
1 <= positions.length <= 50positions[i].length == 20 <= xi, yi <= 100We employ a gradient descent method to iteratively adjust the position of the service center. This method uses the gradient of the loss function (sum of Euclidean distances) to navigate towards a local minimum.
The function to minimize is nonlinear and depends on the current position, so by iteratively updating the center position in the direction opposite to the gradient, we can find a position that minimizes the total distance to all customer points.
JavaScript
Time Complexity: O(n * k * m) where n is the number of points, k is a constant number of iterations, and m is the number of gradient directions checked per iteration.
Space Complexity: O(1) as we only use a fixed amount of auxiliary variables.
Simulated annealing is a probabilistic technique to approximate the global minimum of a cost function. By gradually 'cooling' the algorithm's temperature parameter, it switches from exploration to exploitation, allowing it to escape local minima in search of a global minimum.
We exploit this property to determine the optimal service center location by considering minor random fluctuations and decaying acceptance probability over iterations.
C++
Time Complexity: O(n), as each temperature adjustment involves reassessing distances to all customers.
Space Complexity: O(1), given the fixed storage of current coordinate estimates and immediate variable use.
| Approach | Complexity |
|---|---|
| Approach 1: Gradient Descent Optimization | Time Complexity: O(n * k * m) where n is the number of points, k is a constant number of iterations, and m is the number of gradient directions checked per iteration. Space Complexity: O(1) as we only use a fixed amount of auxiliary variables. |
| Approach 2: Simulated Annealing | Time Complexity: O(n), as each temperature adjustment involves reassessing distances to all customers. Space Complexity: O(1), given the fixed storage of current coordinate estimates and immediate variable use. |
3 Tips I’ve learned after 2000 hours of Leetcode • Top SWE • 616,521 views views
Watch 9 more video solutions →Practice Best Position for a Service Centre with our built-in code editor and test cases.
Practice on FleetCode