FastPrepGet Minimum Sum of Distances

Get Minimum Sum of Distances

Amazon logoAmazon● MediumNEW GRADOA

Updated

Problem statement

Amazon has recently established n distribution centers in a new location. They want to set up 2 warehouses to serve these distribution centers. Note that the centers and warehouses are all built along a straight line. A warehouse may be placed at any point on the line, including at a distribution center, and the two warehouses may share a position. A distribution center has its demands met by the warehouse that is closest to it. A logistics team wants to choose the location of the warehouses such that the sum of the distances of the distribution centers to their closest warehouses is minimized.

Given an array dist_centers that represents the positions of the distribution centers, return the minimum sum of distances to their closest warehouses if the warehouses are positioned optimally.

Function

getMinimumSumOfDistances(dist_centers: int[]) → int

Complete the function getMinimumSumOfDistances in the editor.

getMinimumSumOfDistances has the following parameter:

  1. int[] dist_centers: the positions of the distribution centers

Returns int: the minimum possible sum of distances from each center to its closest warehouse

Examples

Example 1

dist_centers = [1, 6]return = 0

Place one warehouse at position 1 and the other at position 6. Each distribution center has a warehouse at its own position, so the sum of distances is 0 + 0 = 0. The answer is 0.

Example 2

dist_centers = [1, 2, 5, 6]return = 2

Place one warehouse at position 1 and the other at position 6. The distances from the centers at 1, 2, 5 and 6 to their nearest warehouse are [0, 1, 1, 0], for a sum of 2. No placement does better: each warehouse serves a group of centers, and a group whose two farthest-apart centers are d apart costs at least d. If both groups have two centers, each costs at least 1, because any two centers are at least 1 apart, so the sum is at least 1 + 1 = 2. Any other split puts three or four centers in one group, whose farthest-apart centers are at least 4 apart. The answer is 2.

Constraints

  • 1 <= n <= 10^5, where n is the length of dist_centers
  • 1 <= dist_centers[i] <= 10^4

More Amazon interview questions

Similar questions at other companies

Interview reports that mention this question

Amazon interview experiences

See Amazon hiring insights
Saved
class Solution {
    public int getMinimumSumOfDistances(int[] dist_centers) {
      // write your code here
    }

}
Checking account…