Minimum Swaps to Arrange a Binary Grid

Med

#1415Time: 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.

Patterns

Greedy

Data structures

Array Matrix

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

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.

Algorithm

1. Create a list trailing_zeros of size n.
1. For each row i from 0 to n-1, count its trailing zeros and store it in trailing_zeros[i].
1. Initialize swaps = 0.
1. 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.
1. Return swaps.

Walkthrough

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:

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.
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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int minSwaps(int[][] grid) {6        int n = grid.length;7        List<Integer> trailingZeros = new ArrayList<>();8        for (int i = 0; i < n; i++) {9            int count = 0;10            for (int j = n - 1; j >= 0; j--) {11                if (grid[i][j] == 0) {12                    count++;13                } else {14                    break;15                }16            }17            trailingZeros.add(count);18        }19 20        int swaps = 0;21        for (int i = 0; i < n; i++) {22            int required = n - 1 - i;23            int foundIdx = -1;24            25            // Find the first suitable row from current position i26            for (int j = i; j < n; j++) {27                if (trailingZeros.get(j) >= required) {28                    foundIdx = j;29                    break;30                }31            }32 33            if (foundIdx == -1) {34                return -1; // No suitable row found35            }36 37            // Move the found row to position i38            int val = trailingZeros.remove(foundIdx);39            trailingZeros.add(i, val);40            swaps += foundIdx - i;41        }42        return swaps;43    }44}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int minSwaps(int[][] grid) {4    int n = grid.length;5    int[] pos = new int[n];6    Arrays.fill(pos, -1);7    for (int i = 0; i < n; ++i) {8      for (int j = n - 1; j >= 0; --j) {9        if (grid[i][j] == 1) {10          pos[i] = j;11          break;12        }13      }14    }15    int ans = 0;16    for (int i = 0; i < n; ++i) {17      int k = -1;18      for (int j = i; j < n; ++j) {19        if (pos[j] <= i) {20          ans += j - i;21          k = j;22          break;23        }24      }25      if (k == -1) {26        return -1;27      }28      for (; k > i; --k) {29        int t = pos[k];30        pos[k] = pos[k - 1];31        pos[k - 1] = t;32      }33    }34    return ans;35  }36}

1class Solution:2    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

1class Solution {2public:3  int minSwaps(vector<vector<int>> &grid) {4    int n = grid.size();5    vector<int> pos(n, -1);6    for (int i = 0; i < n; ++i) {7      for (int j = n - 1; j >= 0; --j) {8        if (grid[i][j] == 1) {9          pos[i] = j;10          break;11        }12      }13    }14    int ans = 0;15    for (int i = 0; i < n; ++i) {16      int k = -1;17      for (int j = i; j < n; ++j) {18        if (pos[j] <= i) {19          ans += j - i;20          k = j;21          break;22        }23      }24      if (k == -1) {25        return -1;26      }27      for (; k > i; --k) {28        swap(pos[k], pos[k - 1]);29      }30    }31    return ans;32  }33};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem