Minimum Swaps to Arrange a Binary Grid
MedPrompt
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: 3Example 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].length1 <= n <= 200grid[i][j]is either0or1
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
-
- Pre-calculate and store the number of trailing zeros for each of the original
nrows.
- Pre-calculate and store the number of trailing zeros for each of the original
-
- Initialize a variable
min_swapsto a very large value.
- Initialize a variable
-
- Generate every permutation of row indices
[0, 1, ..., n-1].
- Generate every permutation of row indices
-
- For each permutation
p:
- a. Check Validity: Verify if the arrangement is valid. For each position
i, the rowp[i]must have at leastn - 1 - itrailing 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).
- For each permutation
-
- If
min_swapsremains at its initial large value, no solution exists; return -1. Otherwise, returnmin_swaps.
- If
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 forn > 10-12.
Solutions
Solution
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 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.