Show problems as
Classic problem #1478HardArrayMathDynamic ProgrammingSorting

Allocate Mailboxes

Real-world version: Water Taps Along the Lane
Tracked in this browser only
Read Allocate Mailboxes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A lane runs dead straight, and houses[i] is the position of one house along it, measured in metres from the lane's start. No two houses stand at the same position, and the positions arrive in no particular order.

The council will install exactly taps water taps, each at a whole-metre position on the lane. A tap may stand at the same position as a house, and two taps may stand at the same position. Every household then draws water from whichever tap is closest to its own house, walking the distance between the two positions.

Return the smallest total walking distance over all households that any placement of the taps can achieve.

Examples

Example 1

Input
houses = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10000], taps = 2
Output
20

Put one tap at position 5 and the other at position 10000. The nine close households walk 4, 3, 2, 1, 0, 1, 2, 3 and 4 metres, and the far household walks nothing.

Example 2

Input
houses = [7, 2, 9, 1, 4], taps = 2
Output
5

Put one tap at position 2 and the other at position 9. The households at 1, 2 and 4 walk 1, 0 and 2 metres to the first tap, and the households at 7 and 9 walk 2 and 0 metres to the second.

Example 3

Input
houses = [5, 11, 30, 31, 32, 33], taps = 6
Output
0

There are as many taps as houses, so a tap can stand at every house and nobody has to walk.

Constraints

  • 1 <= taps <= houses.length <= 100
  • 1 <= houses[i] <= 10^4
  • The positions in houses are all different.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def least_total_walk(houses: list[int], taps: int) -> int:
Java
public int leastTotalWalk(int[] houses, int taps)

More on the same topics