LeetCode Problem 3426

Difficulty: 🔴 Hard
Topics: Math, Combinatorics

Solution

LeetCode 3426 - Manhattan Distances of All Arrangements of Pieces

Problem Understanding

We are given an m × n grid and must place exactly k identical pieces onto distinct cells. Every possible placement of these k pieces is considered a valid arrangement.

For a single arrangement, we compute the sum of Manhattan distances between every pair of placed pieces. The Manhattan distance between cells (x1, y1) and (x2, y2) is:

$$|x_1-x_2| + |y_1-y_2|$$

The problem asks for the sum of these pairwise distances across all valid arrangements.

The most important detail is that we are not interested in a single arrangement. We must aggregate the contribution of every pair of occupied cells over every possible selection of k cells from the grid.

The constraints are large:

• m, n ≤ 10^5
• m * n ≤ 10^5
• k ≤ m * n

The product m * n is at most 100000, which means iterating over all cells is possible, but enumerating all arrangements is completely infeasible because the number of arrangements is:

$$\binom{m n}{k}$$

which can be astronomically large.

Therefore, the solution must rely on combinatorial counting rather than explicit enumeration.

Some important edge cases are immediately apparent:

• k = 2, where every arrangement contains exactly one pair.
• k = m*n, where every cell is occupied and there is only one arrangement.
• Single-row grids (m = 1) and single-column grids (n = 1).
• Large grids where m*n = 100000, requiring efficient combinatorial preprocessing.
• Situations where many arrangements share the same pair of cells, suggesting a contribution-counting approach.

Approaches

Brute Force

A brute-force solution would generate every possible choice of k cells from the m*n grid.

For each arrangement:

1. Enumerate all occupied-cell pairs.
2. Compute their Manhattan distances.
3. Add the result to the global answer.

This is correct because it directly follows the problem definition.

However, the number of arrangements is:

$$\binom{m n}{k}$$

which is already enormous for even moderate inputs. Furthermore, each arrangement requires examining up to:

$$\binom{k}{2}$$

pairs.

Therefore, this approach is completely impractical.

Key Insight

Instead of iterating through arrangements, reverse the counting process.

Consider a fixed pair of cells:

$$A,; B$$

with Manhattan distance:

$$d(A,B)$$

How many arrangements contain both cells?

Once these two cells are fixed as occupied, we must choose the remaining:

$$k-2$$

occupied cells from the remaining:

$$m n - 2$$

cells.

Thus the number of arrangements containing both cells is:

$$\binom{m n - 2}{k - 2}$$

This value is identical for every pair of cells.

Therefore:

$$\text{Answer} = \left( \sum_{\text{all cell pairs}} d(A,B) \right) \times \binom{m n - 2}{k - 2}$$

So the entire problem reduces to computing the sum of Manhattan distances between all unordered pairs of cells in the grid.

The Manhattan distance separates nicely:

$$|r_1-r_2| + |c_1-c_2|$$

allowing row and column contributions to be computed independently.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	$O\left(\binom{mn}{k} \cdot k^2\right)$	$O(k)$	Enumerates all arrangements
Optimal	$O(m+n+mn)$	$O(mn)$	Uses combinatorial counting and distance decomposition

Algorithm Walkthrough

Step 1: Count how many arrangements contain a fixed pair of cells

Let:

$$N = m \times n$$

Choose any two distinct cells.

Once those two cells are occupied, we need to select:

$$k-2$$

additional occupied cells from the remaining:

$$N-2$$

cells.

The number of such arrangements is:

$$\binom{N-2}{k-2}$$

Step 2: Compute the total distance over all cell pairs

Let:

$$S=\sum_{\text{all unordered cell pairs}} \text{ManhattanDistance}$$

Then:

$$\text{Answer} = S \times \binom{N-2}{k-2}$$

modulo $10^9+7$.

Step 3: Separate row and column contributions

For two cells:

$$(r_1,c_1), (r_2,c_2)$$

the Manhattan distance is:

$$|r_1-r_2| + |c_1-c_2|$$

Therefore:

$$S = S_{\text{row}} + S_{\text{col}}$$

where row and column effects can be computed independently.

Step 4: Compute row contribution

Consider two row indices whose difference equals d.

There are:

$$m-d$$

ways to choose such row pairs.

For each row pair, any column in the first row can be paired with any column in the second row:

$$n^2$$

cell pairs.

Therefore row contribution is:

$$S_{\text{row}} = n^2 \sum_{d=1}^{m-1} d(m-d)$$

Step 5: Compute column contribution

By symmetry:

$$S_{\text{col}} = m^2 \sum_{d=1}^{n-1} d(n-d)$$

Step 6: Add both contributions

$$S = n^2 \sum_{d=1}^{m-1} d(m-d) + m^2 \sum_{d=1}^{n-1} d(n-d)$$

Step 7: Multiply by arrangement count

Finally compute:

$$S \times \binom{N-2}{k-2}$$

under modulo $10^9+7$.

Step 8: Precompute factorials and inverse factorials

Since:

$$N \le 100000$$

we can precompute factorials and inverse factorials up to N and evaluate combinations in constant time.

Why it works

Every unordered pair of cells contributes its Manhattan distance to every arrangement that contains both cells. The number of such arrangements depends only on how many remaining cells must be chosen, namely $\binom{N-2}{k-2}$. Therefore each cell pair contributes:

$$d(A,B)\times \binom{N-2}{k-2}$$

to the final answer. Summing over all cell pairs yields exactly the total Manhattan distance across all arrangements. The row-column decomposition computes the complete pairwise distance sum without enumerating cells or arrangements.

Python Solution

from typing import List

class Solution:
    def distanceSum(self, m: int, n: int, k: int) -> int:
        MOD = 10**9 + 7

        total_cells = m * n

        fact = [1] * (total_cells + 1)
        for i in range(1, total_cells + 1):
            fact[i] = fact[i - 1] * i % MOD

        inv_fact = [1] * (total_cells + 1)
        inv_fact[total_cells] = pow(fact[total_cells], MOD - 2, MOD)

        for i in range(total_cells, 0, -1):
            inv_fact[i - 1] = inv_fact[i] * i % MOD

        def comb(a: int, b: int) -> int:
            if b < 0 or b > a:
                return 0
            return fact[a] * inv_fact[b] % MOD * inv_fact[a - b] % MOD

        pair_count = comb(total_cells - 2, k - 2)

        distance_sum = 0

        for d in range(1, m):
            distance_sum = (
                distance_sum
                + d * (m - d) * n * n
            ) % MOD

        for d in range(1, n):
            distance_sum = (
                distance_sum
                + d * (n - d) * m * m
            ) % MOD

        return distance_sum * pair_count % MOD

The implementation begins by precomputing factorials and inverse factorials up to m*n. This enables constant-time evaluation of combinations modulo 10^9 + 7.

The value pair_count equals $\binom{mn-2}{k-2}$, which represents the number of arrangements containing any fixed pair of cells.

Next, the code computes the total Manhattan distance among all unordered cell pairs. The first loop accumulates row contributions. For a row difference d, there are m-d row pairs and n² cell pairs generated by choosing arbitrary columns. The second loop performs the symmetric computation for columns.

Finally, the total pairwise distance sum is multiplied by the number of arrangements containing each pair, producing the required answer.

Go Solution

func distanceSum(m int, n int, k int) int {
	const MOD int64 = 1000000007

	totalCells := m * n

	fact := make([]int64, totalCells+1)
	fact[0] = 1
	for i := 1; i <= totalCells; i++ {
		fact[i] = fact[i-1] * int64(i) % MOD
	}

	powMod := func(a, e int64) int64 {
		res := int64(1)
		for e > 0 {
			if e&1 == 1 {
				res = res * a % MOD
			}
			a = a * a % MOD
			e >>= 1
		}
		return res
	}

	invFact := make([]int64, totalCells+1)
	invFact[totalCells] = powMod(fact[totalCells], MOD-2)

	for i := totalCells; i >= 1; i-- {
		invFact[i-1] = invFact[i] * int64(i) % MOD
	}

	comb := func(a, b int) int64 {
		if b < 0 || b > a {
			return 0
		}
		return fact[a] * invFact[b] % MOD * invFact[a-b] % MOD
	}

	pairCount := comb(totalCells-2, k-2)

	var distanceSum int64 = 0

	for d := 1; d < m; d++ {
		add := int64(d) * int64(m-d) % MOD
		add = add * int64(n) % MOD
		add = add * int64(n) % MOD
		distanceSum = (distanceSum + add) % MOD
	}

	for d := 1; d < n; d++ {
		add := int64(d) * int64(n-d) % MOD
		add = add * int64(m) % MOD
		add = add * int64(m) % MOD
		distanceSum = (distanceSum + add) % MOD
	}

	return int(distanceSum * pairCount % MOD)
}

The Go implementation follows the same mathematical derivation. The main difference is careful use of int64 for all arithmetic because intermediate values can exceed 32-bit integer limits. Modular exponentiation is implemented explicitly to compute inverse factorials via Fermat's Little Theorem.

Worked Examples

Example 1

Input:

m = 2
n = 2
k = 2

Total cells:

$$N=4$$

Arrangement multiplier:

$$\binom{2}{0}=1$$

Row contribution

d	m-d	n²	Contribution
1	1	4	4

Row sum = 4

Column contribution

d	n-d	m²	Contribution
1	1	4	4

Column sum = 4

Total pairwise cell distance:

$$S=4+4=8$$

Final answer:

$$8 \times 1 = 8$$

Output:

8

Example 2

Input:

m = 1
n = 4
k = 3

Total cells:

$$N=4$$

Arrangement multiplier:

$$\binom{2}{1}=2$$

Row contribution

No row differences exist because m = 1.

$$0$$

Column contribution

d	n-d	m²	Contribution
1	3	1	3
2	2	1	4
3	1	1	3

Column sum:

$$3+4+3=10$$

Thus:

$$S=10$$

Final answer:

$$10 \times 2 = 20$$

Output:

20

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m + n + mn)	Factorial preprocessing costs O(mn), distance computation costs O(m+n)
Space	O(mn)	Factorial and inverse-factorial arrays

The dominant cost comes from precomputing factorials up to m*n, which is at most 100000. This comfortably fits within the problem constraints. After preprocessing, combination evaluation is constant time and the distance summation requires only linear scans over rows and columns.

Test Cases

sol = Solution()

assert sol.distanceSum(2, 2, 2) == 8          # example 1
assert sol.distanceSum(1, 4, 3) == 20         # example 2

assert sol.distanceSum(1, 2, 2) == 1          # smallest nontrivial grid
assert sol.distanceSum(2, 1, 2) == 1          # single column

assert sol.distanceSum(1, 3, 2) == 4          # distances: 1+2+1
assert sol.distanceSum(3, 1, 2) == 4          # symmetric case

assert sol.distanceSum(2, 2, 4) == 8          # all cells occupied

assert sol.distanceSum(1, 5, 5) == 20         # only one arrangement

assert sol.distanceSum(3, 3, 2) == 72         # pairwise cell distance sum

assert sol.distanceSum(10, 10, 2) > 0         # larger grid

assert sol.distanceSum(1, 100000, 2) > 0      # maximum cell count boundary

Test Summary

Test	Why
(2,2,2)	Official example 1
(1,4,3)	Official example 2
(1,2,2)	Smallest valid grid
(2,1,2)	Single-column variant
(1,3,2)	One-dimensional distance counting
(3,1,2)	Symmetric one-dimensional case
(2,2,4)	Every cell occupied
(1,5,5)	Exactly one arrangement
(3,3,2)	Pure pairwise-distance computation
(10,10,2)	Medium-sized grid
(1,100000,2)	Maximum constraint boundary

Edge Cases

When k = 2

This is the simplest nontrivial case. Every arrangement contains exactly one pair of pieces, so the answer becomes the sum of Manhattan distances over all unordered cell pairs. A common mistake is to continue thinking in terms of arrangements rather than recognizing that:

$$\binom{N-2}{0}=1$$

The implementation handles this naturally through the combination formula.

When k = m*n

In this situation every cell is occupied, and there is exactly one valid arrangement. The combination factor becomes:

$$\binom{N-2}{N-2}=1$$

Therefore the answer is simply the total Manhattan distance among all cell pairs. The formula remains valid without any special handling.

Single Row or Single Column Grids

For grids such as 1 × n or m × 1, one dimension contributes nothing. A bug-prone implementation might assume both dimensions have positive differences and accidentally access invalid ranges. Here, the loops:

for d in range(1, m):

and

for d in range(1, n):

naturally perform zero iterations when a dimension equals one, correctly producing only the contribution from the remaining dimension.

Maximum Grid Size

The largest possible value is m*n = 100000. Enumerating cell pairs directly would require roughly $10^{10}$ operations, which is impossible. The contribution formula compresses all pair counting into two linear summations and a single combinatorial multiplier, keeping the solution efficient within the limits.