Get Minimum Sum of Distances
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:
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 = 0Place 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 = 2Place 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, wherenis the length ofdist_centers1 <= dist_centers[i] <= 10^4
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Maximum Taxi EarningsWells Fargo · OAWells Fargo interview questions
- Maximize Power Values Sum 🪴Google · OAGoogle interview questions
- Alternating Jumps to the Last IndexExpedia · OAExpedia interview questions
- Longest Chain of Nested BoxesBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Maximum Length Pair ChainInMobi · ONSITE INTERVIEWInMobi interview questions
- Cheapest Order to Cut a RodAdobe · PHONE SCREENAdobe interview questions
- Russian Doll EnvelopesAirbnb · ONSITE INTERVIEWAirbnb interview questions
- Maximum Game Score with Fixed Forward JumpsStripe · OAStripe interview questions
- 0/1 KnapsackConfluent · OAConfluent interview questions