1478. Allocate Mailboxes LeetCode Solution

Last updated: February 23, 2025

In this guide, you will get 1478. Allocate Mailboxes LeetCode Solution with the best time and space complexity. The solution to Allocate Mailboxes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Allocate Mailboxes solution in C++
Allocate Mailboxes solution in Java
Allocate Mailboxes solution in Python
Additional Resources

1478. Allocate Mailboxes LeetCode Solution image

Problem Statement of Allocate Mailboxes

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.

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.

Constraints:

1 <= k <= houses.length <= 100
1 <= houses[i] <= 104
All the integers of houses are unique.

Complexity Analysis

Time Complexity: O(n^3 + kn^2) = O(n^3);
Space Complexity: O(n^2)

1478. Allocate Mailboxes LeetCode Solution in C++

class Solution {
 public:
  int minDistance(vector<int>& houses, int k) {
    const int n = houses.size();
    vector<vector<int>> mem(n, vector<int>(k + 1, INT_MAX));
    // cost[i][j] := the minimum cost to allocate mailboxes between houses[i]
    // and houses[j]
    vector<vector<int>> cost(n, vector<int>(n));

    ranges::sort(houses);

    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) {
        const int median = houses[(i + j) / 2];
        for (int x = i; x <= j; ++x)
          cost[i][j] += abs(houses[x] - median);
      }

    return minDistance(houses, 0, k, cost, mem);
  }

 private:
  static constexpr int kMax = 1'000'000;

  // Returns the minimum distance to allocate k mailboxes for houses[i..n).
  int minDistance(const vector<int>& houses, int i, int k,
                  const vector<vector<int>>& cost, vector<vector<int>>& mem) {
    if (i == houses.size() && k == 0)
      return 0;
    if (i == houses.size() || k == 0)
      return kMax;
    if (mem[i][k] != INT_MAX)
      return mem[i][k];

    for (int j = i; j < houses.size(); ++j)
      mem[i][k] = min(
          mem[i][k], cost[i][j] + minDistance(houses, j + 1, k - 1, cost, mem));

    return mem[i][k];
  }
};
/* code provided by PROGIEZ */

1478. Allocate Mailboxes LeetCode Solution in Java

class Solution {
  public int minDistance(int[] houses, int k) {
    final int n = houses.length;
    int[][] mem = new int[n][k + 1];
    // cost[i][j] := the minimum cost to allocate mailboxes between houses[i]
    // and houses[j]
    int[][] cost = new int[n][n];

    Arrays.stream(mem).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    Arrays.sort(houses);

    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) {
        int median = houses[(i + j) / 2];
        for (int x = i; x <= j; ++x)
          cost[i][j] += Math.abs(houses[x] - median);
      }

    return minDistance(houses, 0, k, cost, mem);
  }

  private static final int kMax = 1_000_000;

  // Returns the minimum distance to allocate k mailboxes for houses[i..n).
  private int minDistance(int[] houses, int i, int k, int[][] cost, int[][] mem) {
    if (i == houses.length && k == 0)
      return 0;
    if (i == houses.length || k == 0)
      return kMax;
    if (mem[i][k] != Integer.MAX_VALUE)
      return mem[i][k];

    for (int j = i; j < houses.length; ++j)
      mem[i][k] = Math.min(mem[i][k], cost[i][j] + minDistance(houses, j + 1, k - 1, cost, mem));

    return mem[i][k];
  }
}
// code provided by PROGIEZ

1478. Allocate Mailboxes LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents