Minimum Swaps to Arrange a Binary Grid

MEDIUM

Description

Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.

A grid is said to be valid if all the cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

Example 1:

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3

Example 2:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0

Constraints:

n == grid.length == grid[i].length
1 <= n <= 200
grid[i][j] is either 0 or 1

Approaches

Checkout 2 different approaches to solve Minimum Swaps to Arrange a Binary Grid. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Permutations

This approach exhaustively checks every possible arrangement of rows to find a valid one that requires the minimum number of swaps. It's conceptually simple but computationally very expensive.

Algorithm

1. Pre-calculate and store the number of trailing zeros for each of the original n rows.
1. Initialize a variable min_swaps to a very large value.
1. Generate every permutation of row indices [0, 1, ..., n-1].
1. For each permutation p:
- a. Check Validity: Verify if the arrangement is valid. For each position i, the row p[i] must have at least n - 1 - i trailing zeros.
- b. Calculate Swaps: If the permutation is valid, calculate the number of inversions in p. This gives the number of adjacent swaps.
- c. Update Minimum: Update min_swaps = min(min_swaps, number_of_inversions).
1. If min_swaps remains at its initial large value, no solution exists; return -1. Otherwise, return min_swaps.

The fundamental idea is to generate all n! permutations of the grid's rows. For each permutation, we first check if it meets the criteria for a 'valid' grid (all cells above the main diagonal are zero). If it is valid, we then calculate the number of adjacent swaps needed to transform the original row order into this new, valid order. This number of swaps is equivalent to the number of inversions in the permutation. We keep track of the minimum swap count found across all valid permutations.

This method is guaranteed to find the optimal solution because it explores the entire solution space. However, due to the factorial growth (n!), it is not feasible for the constraints given in the problem (n <= 200) and will time out.

Complexity Analysis

Time Complexity: O(n! * n^2) - Generating `n!` permutations, and for each, performing a check and inversion count which takes at least `O(n)` time.Space Complexity: O(n^2) - To store the grid itself. Additional `O(n)` space is needed for storing permutations and helper arrays.

Pros and Cons

Pros:

Guarantees finding the absolute minimum number of swaps if a solution exists.

Cons:

Extremely inefficient with a time complexity of O(n! * n^2), making it impractical for n > 10-12.

Code Solutions

Checking out 3 solutions in different languages for Minimum Swaps to Arrange a Binary Grid. Click on different languages to view the code.

class Solution {
public
  int minSwaps(int[][] grid) {
    int n = grid.length;
    int[] pos = new int[n];
    Arrays.fill(pos, -1);
    for (int i = 0; i < n; ++i) {
      for (int j = n - 1; j >= 0; --j) {
        if (grid[i][j] == 1) {
          pos[i] = j;
          break;
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int k = -1;
      for (int j = i; j < n; ++j) {
        if (pos[j] <= i) {
          ans += j - i;
          k = j;
          break;
        }
      }
      if (k == -1) {
        return -1;
      }
      for (; k > i; --k) {
        int t = pos[k];
        pos[k] = pos[k - 1];
        pos[k - 1] = t;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Minimum Swaps to Arrange a Binary Grid

Patterns:

Greedy

Data Structures:

ArrayMatrix