Best Position for a Service Centre - Practice Coding Problems

Best Position for a Service Centre - Problem

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 sum of distances √((xi-xcentre)² + (yi-ycentre)²) for all customers is minimized.

Answers within 10⁻⁵ of the actual value will be accepted.

Input & Output

Example 1 — Square Formation

$ Input: positions = [[0,1],[1,0],[1,2],[2,1]]

› Output: 4.00000

💡 Note: Customers form a square pattern. The optimal service center is at (1,1) which gives equal distances √2 to each corner, total = 4×√2 ≈ 5.66. However, the actual optimal position minimizes this further to approximately 4.0.

Example 2 — Linear Arrangement

$ Input: positions = [[1,1],[3,3]]

› Output: 2.82843

💡 Note: Two customers at (1,1) and (3,3). Optimal center is at midpoint (2,2), giving distances √2 + √2 = 2√2 ≈ 2.828 to both customers.

Example 3 — Single Customer

$ Input: positions = [[1,1]]

› Output: 0.00000

💡 Note: Only one customer at (1,1). The service center should be placed at the same location, giving total distance = 0.

Constraints

1 ≤ positions.length ≤ 50
positions[i].length == 2
0 ≤ positions[i][0], positions[i][1] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Customer positions on 2D map: [[0,1],[1,0],[1,2],[2,1]]

Process

Find center position minimizing sum of Euclidean distances

Output

Minimum possible sum of distances: 4.00000

Key Takeaway

🎯 Key Insight: The optimal service center location is found through mathematical optimization, not simple averaging of coordinates

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that this is a geometric optimization problem where we need to find the point that minimizes the sum of Euclidean distances to all customers. The optimal approach uses gradient descent starting from the centroid to iteratively find the minimum. Time: O(n × k), Space: O(1) where k is the number of iterations.

Common Approaches

Approach	Time	Space	Notes
✓ Grid Search	O(G × n)	O(1)	Try all possible positions on a fine grid
Gradient Descent Optimization	O(n × k)	O(1)	Use iterative optimization to find the minimum point

Grid Search — Algorithm Steps

Find bounding box of all customer positions
Generate grid points within the box
For each grid point, calculate sum of distances to all customers
Return minimum distance found

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup Grid

Create fine grid over customer area

Test Points

Calculate distance sum for each grid point

Find Minimum

Return the grid point with smallest total distance

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

double solution(int positions[][2], int n) {
    if (n == 0) return 0.0;
    
    // Find bounding box
    int minX = positions[0][0], maxX = positions[0][0];
    int minY = positions[0][1], maxY = positions[0][1];
    
    for (int i = 0; i < n; i++) {
        if (positions[i][0] < minX) minX = positions[i][0];
        if (positions[i][0] > maxX) maxX = positions[i][0];
        if (positions[i][1] < minY) minY = positions[i][1];
        if (positions[i][1] > maxY) maxY = positions[i][1];
    }
    
    double minDist = 1e9;
    double step = 0.01;
    
    // Try all grid points
    for (double x = minX; x <= maxX; x += step) {
        for (double y = minY; y <= maxY; y += step) {
            double totalDist = 0;
            for (int i = 0; i < n; i++) {
                double dx = x - positions[i][0];
                double dy = y - positions[i][1];
                totalDist += sqrt(dx*dx + dy*dy);
            }
            if (totalDist < minDist) {
                minDist = totalDist;
            }
        }
    }
    
    return minDist;
}

int main() {
    // Simple parsing for small test cases
    int positions[100][2];
    int n = 0;
    
    // Read and parse positions manually
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Basic parsing - assumes format [[x1,y1],[x2,y2],...]
    char* ptr = line + 1; // Skip first [
    while (*ptr && n < 100) {
        if (*ptr == '[') {
            ptr++;
            positions[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            if (*ptr == ',') ptr++;
            positions[n][1] = atoi(ptr);
            n++;
            while (*ptr && *ptr != ']') ptr++;
        }
        ptr++;
    }
    
    double result = solution(positions, n);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(G × n)

G grid points × n customers for distance calculation

✓ Linear Growth

Space Complexity

O(1)

Only variables for tracking minimum, no extra data structures

✓ Linear Space

18.5K Views

Medium Frequency

~35 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Grid Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler