#1478

Allocate Mailboxes

expert · 1255 · lc hard +32 · verified · 56.5% accepted · 1,171 likes · top 51%

Description

Houses are located at positions given by the array houses along a street. You must place exactly k mailboxes anywhere on the street. Return the minimum possible sum of distances, where each house's contribution is its distance to the nearest mailbox. The answer is guaranteed to fit in a 32-bit integer.

Example 1:

Input: houses = [1,4,8,10,20], k = 3

Output: 5

Explanation: Allocate mailboxes in position 3, 9 and 20.

Minimum total distance from each houses to nearest mailboxes is |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5

Example 2:

Input: houses = [2,3,5,12,18], k = 2

Output: 9

Explanation: Allocate mailboxes in position 3 and 14.

Minimum total distance from each houses to nearest mailboxes is |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9.

Code

1

2

3

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int: