Manhattan Distances of All Arrangements of Pieces

Manhattan Distances of All Arrangements of Pieces - Problem

Math Combinatorics Hard

You are given three integers m, n, and k. There is a rectangular grid of size m × n containing k identical pieces.

Return the sum of Manhattan distances between every pair of pieces over all valid arrangements of pieces.

A valid arrangement is a placement of all k pieces on the grid with at most one piece per cell.

Since the answer may be very large, return it modulo 10^9 + 7.

The Manhattan Distance between two cells (x_i, y_i) and (x_j, y_j) is |x_i - x_j| + |y_i - y_j|.

Input & Output

Example 1 — Small Grid

$ Input: m = 1, n = 2, k = 2

› Output: 1

💡 Note: Only one arrangement possible: both pieces at positions (0,0) and (0,1). Distance = |0-0| + |0-1| = 1.

Example 2 — Square Grid

$ Input: m = 2, n = 2, k = 2

› Output: 8

💡 Note: Grid has 4 cells, C(4,2) = 6 arrangements. Sum of all pairwise distances across arrangements equals 8.

Example 3 — Single Piece

$ Input: m = 3, n = 3, k = 1

› Output: 0

💡 Note: With only one piece, there are no pairs to calculate distance between, so sum is 0.

Constraints

1 ≤ m, n ≤ 100
1 ≤ k ≤ m × n
Answer fits in 32-bit integer after modulo

Visualization

Tap to expand

Understanding the Visualization

Input

Grid dimensions m×n and k pieces to place

Process

Calculate Manhattan distances for all arrangements

Output

Sum of all pairwise distances modulo 10^9+7

Key Takeaway

🎯 Key Insight: Use combinatorial mathematics to count distance contributions without generating all arrangements

Asked in

G Google 25 f Meta 18 M Microsoft 15 a Amazon 12

The key insight is to avoid generating all arrangements by using combinatorial mathematics. Split Manhattan distance into x and y components, then for each pair of cells, calculate how many arrangements include both cells using C(total-2, k-2). Best approach is mathematical combinatorics. Time: O(m²×n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(C(mn, k) k²)	O(k)	Generate all possible arrangements and calculate sum of distances
Mathematical Combinatorics	O(m² × n²)	O(1)	Use combinatorial mathematics to calculate sum without generating arrangements

Brute Force Enumeration — Algorithm Steps

Generate all ways to choose k positions from m*n grid cells
For each arrangement, calculate distances between all pairs
Sum all distances across all arrangements

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Positions

Create all m×n grid positions

All Combinations

Generate C(m×n, k) arrangements

Calculate Distances

Sum Manhattan distances for each arrangement

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MOD 1000000007

int abs_val(int x) {
    return x < 0 ? -x : x;
}

void generate_combinations(int positions[][2], int total_pos, int k, int start, int depth, int current[][2], long long *total) {
    if (depth == k) {
        for (int i = 0; i < k; i++) {
            for (int j = i + 1; j < k; j++) {
                int dist = abs_val(current[i][0] - current[j][0]) + abs_val(current[i][1] - current[j][1]);
                *total = (*total + dist) % MOD;
            }
        }
        return;
    }
    
    for (int i = start; i < total_pos; i++) {
        current[depth][0] = positions[i][0];
        current[depth][1] = positions[i][1];
        generate_combinations(positions, total_pos, k, i + 1, depth + 1, current, total);
    }
}

int solution(int m, int n, int k) {
    long long total = 0;
    int positions[m * n][2];
    int current[k][2];
    
    int idx = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            positions[idx][0] = i;
            positions[idx][1] = j;
            idx++;
        }
    }
    
    generate_combinations(positions, m * n, k, 0, 0, current, &total);
    return (int)total;
}

int main() {
    int m, n, k;
    scanf("%d", &m);
    scanf("%d", &n);
    scanf("%d", &k);
    
    printf("%d\n", solution(m, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(C(m*n, k) * k²)

C(m*n, k) arrangements times k² pairs per arrangement

✓ Linear Growth

Space Complexity

O(k)

Store current arrangement of k pieces

✓ Linear Space

12.4K Views

Medium Frequency

~35 min Avg. Time

285 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

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler