1515. Best Position for a Service Centre LeetCode Solution

In this guide, you will get 1515. Best Position for a Service Centre LeetCode Solution with the best time and space complexity. The solution to Best Position for a Service Centre problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Best Position for a Service Centre solution in C++
Best Position for a Service Centre solution in Java
Best Position for a Service Centre solution in Python
Additional Resources

1515. Best Position for a Service Centre LeetCode Solution image

Problem Statement of Best Position for a Service Centre

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 <= 50
positions[i].length == 2
0 <= xi, yi <= 100

Complexity Analysis

Time Complexity:
Space Complexity:

1515. Best Position for a Service Centre LeetCode Solution in C++

class Solution {
 public:
  double getMinDistSum(vector<vector<int>>& positions) {
    constexpr double kErr = 1e-6;
    double currX = 50;
    double currY = 50;
    double ans = distSum(positions, currX, currY);
    double step = 1;

    while (step > kErr) {
      bool shouldDecreaseStep = true;
      for (const auto& [dx, dy] : vector<pair<double, double>>{
               {0, step}, {0, -step}, {step, 0}, {-step, 0}}) {
        const double x = currX + dx;
        const double y = currY + dy;
        const double newDistSum = distSum(positions, x, y);
        if (newDistSum < ans) {
          ans = newDistSum;
          currX = x;
          currY = y;
          shouldDecreaseStep = false;
        }
      }
      if (shouldDecreaseStep)
        step /= 10;
    }

    return ans;
  }

 private:
  double distSum(const vector<vector<int>>& positions, double a, double b) {
    double sum = 0;
    for (const vector<int>& p : positions)
      sum += sqrt(pow(a - p[0], 2) + pow(b - p[1], 2));
    return sum;
  }
};
/* code provided by PROGIEZ */

1515. Best Position for a Service Centre LeetCode Solution in Java

class Solution {
  public double getMinDistSum(int[][] positions) {
    final double kErr = 1e-6;
    double currX = 50;
    double currY = 50;
    double ans = distSum(positions, currX, currY);
    double step = 1;

    while (step > kErr) {
      boolean shouldDecreaseStep = true;
      for (double[] dirs : new double[][] {{0, step}, {0, -step}, {step, 0}, {-step, 0}}) {
        final double x = currX + dirs[0];
        final double y = currY + dirs[1];
        final double newDistSum = distSum(positions, x, y);
        if (newDistSum < ans) {
          ans = newDistSum;
          currX = x;
          currY = y;
          shouldDecreaseStep = false;
        }
      }
      if (shouldDecreaseStep)
        step /= 10;
    }

    return ans;
  }

  private double distSum(int[][] positions, double a, double b) {
    double sum = 0;
    for (int[] p : positions)
      sum += Math.sqrt(Math.pow(a - p[0], 2) + Math.pow(b - p[1], 2));
    return sum;
  }
}
// code provided by PROGIEZ

1515. Best Position for a Service Centre LeetCode Solution in Python

class Solution:
  def getMinDistSum(self, positions: list[list[int]]) -> float:
    def distSum(a: float, b: float) -> float:
      return sum(math.sqrt((a - x)**2 + (b - y)**2)
                 for x, y in positions)

    kErr = 1e-6
    currX = 50
    currY = 50
    ans = distSum(currX, currY)
    step = 1

    while step > kErr:
      shouldDecreaseStep = True
      for dx, dy in [(0, step), (0, -step), (step, 0), (-step, 0)]:
        x = currX + dx
        y = currY + dy
        newDistSum = distSum(x, y)
        if newDistSum < ans:
          ans = newDistSum
          currX = x
          currY = y
          shouldDecreaseStep = False
      if shouldDecreaseStep:
        step /= 10

    return ans
 # code by PROGIEZ