Allocate mailboxes

Array Math Dynamic Programming Sorting

56.5% acceptance

Feb 25, 2026

1171

Given the array houses where houses[i] is the location of the ith house along a street and an integer k, allocate k mailboxes in the street. Return the minimum total distance between each house and its nearest mailbox. The test cases are generated so that the answer fits in a 32-bit integer.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_distance(mut houses: Vec<i32>, k: i32) -> i32 {
    houses.sort_unstable();
    let n = houses.len();
    let k = k as usize;
    // cost[i][j] = min cost with one mailbox for houses[i..=j]
    let mut cost = vec![vec![0i32; n]; n];
    for i in 0..n {
      for j in i..n {
        let m = (i + j) / 2;
        let mut c = 0;
        for l in i..=j {
          c += (houses[l] - houses[m]).abs();
        }
        cost[i][j] = c;
      }
    }
    const INF: i32 = i32::MAX / 2;
    // dp[i][j] = min cost for i mailboxes covering houses[0..=j]
    let mut dp = vec![vec![INF; n]; k + 1];
    for j in 0..n { dp[1][j] = cost[0][j]; }
    for i in 2..=k {
      for j in (i - 1)..n {
        for p in (i - 2)..j {
          if dp[i - 1][p] < INF {
            let val = dp[i - 1][p] + cost[p + 1][j];
            if val < dp[i][j] { dp[i][j] = val; }
          }
        }
      }
    }
    dp[k][n - 1]
  }
}