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].length1 <= n <= 200grid[i][j] is either 0 or 1This greedy method counts the number of trailing zeros in each row and then tries to move rows upwards to match each row's position with the trailing zero requirement.
The idea is to calculate the minimum number of zeroes required on the right side for each row and then check if a row can be moved up by swapping to meet the requirement.
The function minSwaps is implemented to calculate the number of trailing zeros for each row and tries to position them correctly by swapping rows up when necessary. The inner loop finds the closest row with enough trailing zeros to swap in place.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), as we iterate over the grid twice to find trailing zeros and perform necessary swaps. Space Complexity: O(n) for storing trailing zero counts.
This method involves counting the minimum number of swaps directly by halting if a grid row, while positioned at top positions, meets the required trailing zero count. Start from the bottom row and work upwards, swapping minimally to achieve target zero counts.
The C approach decomposes row trailing zeros and aligns these with minimum bottom-to-top swapping, moving upwards and maintaining swap count or returning -1 for an impossible task.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), iterating primarily for least swaps, incrementally. Space Complexity: O(n) to store zero counts.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Method to Track Trailing Zeros | Time Complexity: O(n^2), as we iterate over the grid twice to find trailing zeros and perform necessary swaps. Space Complexity: O(n) for storing trailing zero counts. |
| Approach 2: Advanced Counting from Bottom to Top | Time Complexity: O(n^2), iterating primarily for least swaps, incrementally. Space Complexity: O(n) to store zero counts. |
Minimum Swaps Required to Sort an Array • DS Algo • 91,592 views views
Watch 9 more video solutions →Practice Minimum Swaps to Arrange a Binary Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor