Manhattan Distances of All Arrangements of Pieces - Solution & Explanation

Problem Overview: You place k identical pieces on an m x n grid. For every possible arrangement, compute the total Manhattan distance between every pair of pieces. The task is to return the sum of these distances across all valid arrangements.

Approach 1: Brute Force Enumeration (Exponential)

The most direct idea is to generate every way to place k pieces among the m * n cells, then compute the pairwise Manhattan distance for each arrangement. For every configuration you iterate over all k choose 2 pairs and accumulate distances. This quickly becomes infeasible because the number of arrangements is C(mn, k). Time complexity is roughly O(C(mn, k) * k^2) with O(k) space for storing positions. This approach only works for extremely small grids and mainly helps you understand what the problem is asking.

Approach 2: Pair Contribution with Combinatorics (O(m + n))

Instead of enumerating arrangements, focus on how much each pair of cells contributes to the final answer. If two cells are chosen for pieces, their Manhattan distance contributes once for every arrangement where those two cells are occupied. The number of such arrangements is C(mn - 2, k - 2) because the remaining k-2 pieces can be placed in any of the other cells.

Now compute the sum of Manhattan distances across all unordered cell pairs. Manhattan distance splits cleanly into row and column components: |r1 - r2| + |c1 - c2|. You can aggregate these independently.

For rows, consider every distance d between two rows. There are (m - d) row pairs with that difference. Each row pair combines with any column pair, giving n * n cell pairs. The total row contribution becomes sum(d * (m - d) * n^2). Do the same for columns: sum(d * (n - d) * m^2). This produces the total Manhattan distance across all cell pairs in O(m + n) time.

Finally multiply that value by C(mn - 2, k - 2). Precompute factorials and modular inverses to evaluate combinations efficiently. This solution relies heavily on combinatorics and mathematical decomposition of Manhattan distance. Time complexity is O(m + n) with O(mn) preprocessing for factorials.

Recommended for interviews: The combinatorics contribution approach is what interviewers expect. Explaining the brute force shows you understand the problem space, but recognizing that each pair of cells contributes independently demonstrates strong mathematical reasoning and familiarity with combinatorial counting.