Allocate Mailboxes - Practice Coding Problems

Allocate Mailboxes - Problem

Given an 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.

Input & Output

Example 1 — Basic Case

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

› Output: 5

💡 Note: Allocate mailboxes at positions 1, 8, and 20. Houses [1,4] use mailbox at 1 (distance 0+3=3), house [8] uses mailbox at 8 (distance 0), houses [10,20] use mailbox at 20 (distance 10+0=10). But optimal is mailboxes at 3, 8, 15 giving total distance 5.

Example 2 — Two Mailboxes

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

› Output: 9

💡 Note: Place first mailbox at position 3 for houses [2,3,5] (distances 1+0+2=3) and second mailbox at position 15 for houses [12,18] (distances 3+3=6). Total: 3+6=9.

Example 3 — One Mailbox

$ Input: houses = [7,4,6,1], k = 1

› Output: 8

💡 Note: With only one mailbox, place it at median position. Sorted houses: [1,4,6,7]. Median between positions 1 and 2 is around 5. Place mailbox at 4 or 6. At position 5: distances are 4+1+1+2=8.

Constraints

1 ≤ k ≤ houses.length ≤ 100
1 ≤ houses[i] ≤ 10⁴
All the positions of houses are unique.

Visualization

Tap to expand

Understanding the Visualization

Input

Houses at positions [1,4,8,10,20] and k=3 mailboxes

Process

Find optimal mailbox positions using DP

Output

Minimum total distance is 5

Key Takeaway

🎯 Key Insight: For any group of houses, place the mailbox at the median position to minimize total distance

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is that for any group of consecutive houses, the optimal mailbox position is at the median to minimize total distance. Best approach uses 2D Dynamic Programming with precomputed cost matrix. Time: O(n²×k), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(n² × k)	O(n × k)	Cache recursive results to avoid recomputation
Brute Force Recursion	O(k^n)	O(n)	Try all possible ways to partition houses into k groups
2D Dynamic Programming	O(n² × k)	O(n²)	Bottom-up DP with precomputed costs

Memoized Recursion — Algorithm Steps

Step 1: Sort houses by position
Step 2: Use recursion with memoization
Step 3: Cache results for each (index, mailboxes_left) state

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Calculate solve(2, 2) = ?

Cache Result

Store result in memo table

Reuse

Next time solve(2, 2) returns cached value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_HOUSES 100
#define MAX_MEMO 10000

struct MemoEntry {
    int idx;
    int mailboxes;
    int cost;
    int used;
};

struct MemoEntry memo[MAX_MEMO];
int memoSize = 0;
int houses[MAX_HOUSES];
int n;

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int getMemo(int idx, int mailboxes) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].used && memo[i].idx == idx && memo[i].mailboxes == mailboxes) {
            return memo[i].cost;
        }
    }
    return -1;
}

void setMemo(int idx, int mailboxes, int cost) {
    if (memoSize < MAX_MEMO) {
        memo[memoSize].idx = idx;
        memo[memoSize].mailboxes = mailboxes;
        memo[memoSize].cost = cost;
        memo[memoSize].used = 1;
        memoSize++;
    }
}

int cost(int i, int j) {
    int mid = (i + j) / 2;
    int total = 0;
    for (int idx = i; idx <= j; idx++) {
        total += abs(houses[idx] - houses[mid]);
    }
    return total;
}

int solve(int idx, int mailboxesLeft) {
    int cached = getMemo(idx, mailboxesLeft);
    if (cached != -1) {
        return cached;
    }
    
    if (mailboxesLeft == 1) {
        int result = cost(idx, n - 1);
        setMemo(idx, mailboxesLeft, result);
        return result;
    }
    
    if (idx >= n) {
        return INT_MAX;
    }
    
    int minCost = INT_MAX;
    for (int end = idx; end <= n - mailboxesLeft; end++) {
        int currentCost = cost(idx, end);
        int remaining = solve(end + 1, mailboxesLeft - 1);
        if (remaining != INT_MAX) {
            if (currentCost + remaining < minCost) {
                minCost = currentCost + remaining;
            }
        }
    }
    
    setMemo(idx, mailboxesLeft, minCost);
    return minCost;
}

int solution(int* housesArr, int housesSize, int k) {
    for (int i = 0; i < housesSize; i++) {
        houses[i] = housesArr[i];
    }
    n = housesSize;
    qsort(houses, n, sizeof(int), compare);
    memoSize = 0;
    return solve(0, k);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int housesArr[MAX_HOUSES];
    int housesSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            housesArr[housesSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(housesArr, housesSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × k)

At most n×k unique states, each taking O(n) time to compute

⚠ Quadratic Growth

Space Complexity

O(n × k)

Memoization table stores n×k states plus recursion stack

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~45 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler