Manhattan Distances of All Arrangements of Pieces

Manhattan Distances of All Arrangements of Pieces

What is this problem about?

This is a highly advanced combinatorial math problem. You are given an $M \times N$ grid and $K$ identical pieces. You need to place all $K$ pieces on the grid. For a single arrangement of $K$ pieces, the "Manhattan Distance" of that arrangement is the sum of the Manhattan distances between all pairs of pieces. You must return the sum of these distances across all possible valid arrangements of the $K$ pieces on the grid, modulo $10^9 + 7$.

Why is this asked in interviews?

This problem is asked almost exclusively in quantitative finance firms (like Citadel or HRT) or for extremely senior FAANG algorithmic roles. It tests a candidate's ability to decouple combinatorics from geometry. A brute-force generation of arrangements is impossible. It requires you to mathematically calculate the expected contribution of a single distance between two specific cells across all possible combinations of the remaining pieces.

Algorithmic pattern used

This problem relies purely on Combinatorics and Decoupling Dimensions. Instead of looking at whole arrangements, look at a single pair of cells A and B. The distance between them is dist(A, B). If we place pieces on A and B, how many ways can we place the remaining $K - 2$ pieces in the remaining $M \times N - 2$ empty cells? The answer is "N-choose-K": $\binom{M \times N - 2}{K - 2}$. Therefore, the total sum is simply the sum of dist(A, B) for all possible pairs of cells in the grid, multiplied by $\binom{M \times N - 2}{K - 2}$. Furthermore, calculating the sum of distances for all cell pairs can be optimized mathematically in $O(M + N)$ or $O(1)$ time by separating the X and Y axes.

Example explanation

Grid $2 \times 2$, pieces $K = 3$. Total cells $C = 4$. Remaining cells to place $K-2$ pieces: $C - 2 = 2$. Remaining pieces: $3 - 2 = 1$. Combinations = $\binom{2}{1} = 2$. Let's find sum of all pairwise distances in a $2 \times 2$ grid:

• (0,0) to (0,1): dist 1
• (0,0) to (1,0): dist 1
• (0,0) to (1,1): dist 2 ... Doing this for all 6 unique pairs yields a total grid distance of 8. Total answer = $8 \times 2 = 16$.

Common mistakes candidates make

The biggest mistake is attempting to simulate the board states or generate arrangements using backtracking. Since the board can be large and $K$ can be large, $O(\binom{M \times N}{K})$ time complexity will fail instantly. Another error is calculating the combinations using naive factorials which overflow; you must use modular inverse properties to calculate $\binom{N}{K} \pmod{10^9+7}$.

Interview preparation tip

For this specific advanced pattern, remember that Expected Value and Combinatorial Sums can almost always be "flipped". Instead of summing over configurations, sum over the atomic elements (the pairs of cells) and multiply by the number of configurations in which that atomic element is active. Also, learn how to calculate Sum of absolute differences in a 1D array mathematically to optimize the grid distance calculation.