# Minimum Swaps to Arrange a Binary Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-swaps-to-arrange-a-binary-grid)
Canonical: https://scaleengineer.com/dsa/problems/minimum-swaps-to-arrange-a-binary-grid
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-swaps-to-arrange-a-binary-grid/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/minimum-swaps-to-arrange-a-binary-grid/image1.jpg) 

**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:**

![](https://assets.glich.co/dsa/minimum-swaps-to-arrange-a-binary-grid/image2.jpg) 

**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
## 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.
**Time:** O(n! * n^2) - Generating `n!` permutations, and for each, performing a check and inversion count which takes at least `O(n)` time. · **Space:** O(n^2) - To store the grid itself. Additional `O(n)` space is needed for storing permutations and helper arrays.
**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`.
### Explanation
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.
### Algorithm
*   1. Pre-calculate and store the number of trailing zeros for each of the original `n` rows.
*   2. Initialize a variable `min_swaps` to a very large value.
*   3. Generate every permutation of row indices `[0, 1, ..., n-1]`.
*   4. 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)`.
*   5. If `min_swaps` remains at its initial large value, no solution exists; return -1. Otherwise, return `min_swaps`.

## Greedy Row Selection
A much more efficient approach is to solve the problem greedily. We first simplify the problem by representing each row by its count of trailing zeros. Then, we iterate from the top row downwards, and for each position, we find the closest available row that satisfies the requirement and move it into place, summing the swaps.
**Time:** O(n^2) - The initial calculation of trailing zeros is `O(n^2)`. The main loop runs `n` times, and inside it, the search and list manipulation each take up to `O(n)` time, leading to `O(n^2)` for the swapping part. · **Space:** O(n) - To store the list of trailing zero counts.
**Pros:** Efficient with `O(n^2)` time complexity, which is well within limits.; The greedy logic is intuitive and relatively simple to implement.
**Cons:** The use of a list with removals and insertions can be slightly less performant than pure array manipulations in some languages, but the overall complexity remains the same.
### Explanation
The condition for a valid grid implies that for each row `i` (from 0 to `n-1`), the row placed at this position must have at least `n - 1 - i` trailing zeros. This insight allows us to build the valid grid row by row.

The algorithm proceeds as follows:
1.  **Preprocessing:** First, we iterate through the input `grid` and calculate the number of trailing zeros for each row. We store these counts in a list, say `trailing_zeros`, which maintains the current order of rows.
2.  **Greedy Swapping:** We then iterate from `i = 0` to `n-1`. In each iteration `i`, we are trying to fill the `i`-th row of the grid. We need a row with at least `n - 1 - i` trailing zeros.
    *   We search for the *first* available row from the current position `i` onwards (i.e., in `trailing_zeros[i:]`) that meets this requirement.
    *   If no such row is found, it's impossible to form a valid grid, and we return -1.
    *   If we find a suitable row at index `j` (`j >= i`), we know it takes `j - i` adjacent swaps to move this row to position `i`. We add this to our total swap count.
    *   We then update our `trailing_zeros` list to reflect this swap: we move the element from index `j` to index `i`. This ensures that in the next iteration for `i+1`, we are working with the correctly updated arrangement of rows.

This greedy choice is optimal because by picking the closest suitable row, we satisfy the current requirement with the minimum possible number of swaps, without negatively affecting our ability to solve the subproblem for the remaining rows.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minSwaps(int[][] grid) {
        int n = grid.length;
        List<Integer> trailingZeros = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 0) {
                    count++;
                } else {
                    break;
                }
            }
            trailingZeros.add(count);
        }

        int swaps = 0;
        for (int i = 0; i < n; i++) {
            int required = n - 1 - i;
            int foundIdx = -1;
            
            // Find the first suitable row from current position i
            for (int j = i; j < n; j++) {
                if (trailingZeros.get(j) >= required) {
                    foundIdx = j;
                    break;
                }
            }

            if (foundIdx == -1) {
                return -1; // No suitable row found
            }

            // Move the found row to position i
            int val = trailingZeros.remove(foundIdx);
            trailingZeros.add(i, val);
            swaps += foundIdx - i;
        }
        return swaps;
    }
}
```
### Algorithm
*   1. Create a list `trailing_zeros` of size `n`.
*   2. For each row `i` from `0` to `n-1`, count its trailing zeros and store it in `trailing_zeros[i]`.
*   3. Initialize `swaps = 0`.
*   4. Iterate `i` from `0` to `n-1` (the target row position):
    *   a. Calculate `required_zeros = n - 1 - i`.
    *   b. Search for the first index `j >= i` where `trailing_zeros[j] >= required_zeros`.
    *   c. If no such `j` exists, return -1.
    *   d. Add `j - i` to `swaps`.
    *   e. Simulate the swap by moving the element at `j` to position `i` in the `trailing_zeros` list.
*   5. Return `swaps`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int: n = len(grid) pos = [- 1] * n for i in range(n): for j in range(n - 1, - 1, - 1): if grid[i][j] == 1: pos[i] = j break ans = 0 for i in range(n): k = - 1 for j in range(i, n): if pos[j] <= i: ans += j - i k = j break if k == - 1: return - 1 while k > i: pos[k], pos[k - 1] = pos[k - 1], pos[k] k -= 1 return ans

```

### CPP

```cpp
class Solution {
public:
  int minSwaps(vector<vector<int>> &grid) {
    int n = grid.size();
    vector<int> pos(n, -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) {
        swap(pos[k], pos[k - 1]);
      }
    }
    return ans;
  }
};

```