3426. Manhattan Distances of All Arrangements of Pieces LeetCode Solution

In this guide, you will get 3426. Manhattan Distances of All Arrangements of Pieces LeetCode Solution with the best time and space complexity. The solution to Manhattan Distances of All Arrangements of Pieces problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Manhattan Distances of All Arrangements of Pieces solution in C++
Manhattan Distances of All Arrangements of Pieces solution in Java
Manhattan Distances of All Arrangements of Pieces solution in Python
Additional Resources

3426. Manhattan Distances of All Arrangements of Pieces LeetCode Solution image

Problem Statement of Manhattan Distances of All Arrangements of Pieces

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 109 + 7.
The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi – xj| + |yi – yj|.

Example 1:

Input: m = 2, n = 2, k = 2
Output: 8
Explanation:
The valid arrangements of pieces on the board are:

In the first 4 arrangements, the Manhattan distance between the two pieces is 1.
In the last 2 arrangements, the Manhattan distance between the two pieces is 2.

Thus, the total Manhattan distance across all valid arrangements is 1 + 1 + 1 + 1 + 2 + 2 = 8.

Example 2:

Input: m = 1, n = 4, k = 3
Output: 20
Explanation:
The valid arrangements of pieces on the board are:

The first and last arrangements have a total Manhattan distance of 1 + 1 + 2 = 4.
The middle two arrangements have a total Manhattan distance of 1 + 2 + 3 = 6.

The total Manhattan distance between all pairs of pieces across all arrangements is 4 + 6 + 6 + 4 = 20.

Constraints:

1 <= m, n <= 105
2 <= m * n <= 105
2 <= k <= m * n

Complexity Analysis

Time Complexity: O(k \cdot \log\texttt{kMod})
Space Complexity: O(1)

3426. Manhattan Distances of All Arrangements of Pieces LeetCode Solution in C++

class Solution {
 public:
  int distanceSum(int m, int n, int k) {
    // For each distance d, where 1 < d < m, there are `m - d` ways to choose
    // the two columns that the two pieces are on. For each of the two pieces,
    // there are `n` ways to choose the row that the piece is on.
    // Therefore, the contribution of row differences is
    //   sum(d * (m - d) * n^2), where 1 < d <= m - 1
    // = n^2 * sum(d * m - d^2)
    // = n^2 * (d * m * (m - 1) / 2 - m * (m - 1) * (2m - 1) / 6)
    // = n^2 * (m^3 - m) / 6
    // Similarly, the contribution of column differences is
    //   m^2 * (n^3 - n) / 6
    const int rowContrib = 1L * n * n * (1L * m * m * m - m) / 6 % kMod;
    const int colContrib = 1L * m * m * (1L * n * n * n - n) / 6 % kMod;
    return (rowContrib + colContrib) * nCk(m * n - 2, k - 2) % kMod;
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  long nCk(int n, int k) {
    long res = 1;
    for (int i = 1; i <= k; ++i)
      // By Fermat's little theorem.
      res = res * (n - i + 1) % kMod * modPow(i, kMod - 2) % kMod;
    return res;
  }

  long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x % kMod, (n - 1)) % kMod;
    return modPow(x * x % kMod, (n / 2)) % kMod;
  }
};
/* code provided by PROGIEZ */

3426. Manhattan Distances of All Arrangements of Pieces LeetCode Solution in Java

class Solution {
  public int distanceSum(int m, int n, int k) {
    final long rowContrib = 1L * n * n * (1L * m * m * m - m) / 6 % kMod;
    final long colContrib = 1L * m * m * (1L * n * n * n - n) / 6 % kMod;
    return (int) ((rowContrib + colContrib) % kMod * nCk(m * n - 2, k - 2) % kMod);
  }

  private static final int kMod = 1_000_000_007;

  private long nCk(int n, int k) {
    long res = 1;
    for (int i = 1; i <= k; ++i)
      // By Fermat's little theorem.
      res = res * (n - i + 1) % kMod * modPow(i, kMod - 2) % kMod;
    return res;
  }

  private long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x, n - 1) % kMod;
    return modPow(x * x % kMod, n / 2);
  }
}
// code provided by PROGIEZ

3426. Manhattan Distances of All Arrangements of Pieces LeetCode Solution in Python

class Solution:
  def distanceSum(self, m: int, n: int, k: int) -> int:
    # For each distance d, where 1 < d < m, there are `m - d` ways to choose
    # the two columns that the two pieces are on. For each of the two pieces,
    # there are `n` ways to choose the row that the piece is on.
    # Therefore, the contribution of row differences is
    #   sum(d * (m - d) * n^2), where 1 < d <= m - 1
    # = n^2 * sum(d * m - d^2)
    # = n^2 * (d * m * (m - 1) / 2 - m * (m - 1) * (2m - 1) / 6)
    # = n^2 * (m^3 - m) / 6
    # Similarly, the contribution of column differences is
    #   m^2 * (n^3 - n) / 6
    kMod = 1_000_000_007
    return (n**2 * (m**3 - m) // 6 +
            m**2 * (n**3 - n) // 6) * math.comb(m * n - 2, k - 2) % kMod
 # code by PROGIEZ