Leetcode 1536: Minimum Swaps to Arrange a Binary Grid
You are given an n x n binary grid, and in one move, you can swap any two adjacent rows. The grid is valid if all the cells above the main diagonal are zeros. Your task is to return the minimum number of swaps needed to make the grid valid, or -1 if it’s not possible.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer grid of size n x n, where each element is either 0 or 1.
Example: grid = [[0, 1, 1], [1, 0, 1], [1, 0, 0]]
Constraints:
• n == grid.length == grid[i].length
• 1 <= n <= 200
• grid[i][j] is either 0 or 1
Output: Return the minimum number of swaps required to make the grid valid, or -1 if it's not possible.
Example: For grid = [[0, 1, 1], [1, 0, 1], [1, 0, 0]], the output is 2.
Constraints:
• The output is an integer indicating the number of swaps required or -1 if the grid cannot be made valid.
Goal: The goal is to transform the grid such that all the cells above the main diagonal are zeros by performing a minimum number of adjacent row swaps.
Steps:
• For each row, count the number of trailing zeros.
• For each row, try to find a valid position that can be swapped to fulfill the condition of zeros above the main diagonal.
• Simulate the row swaps and track how many steps it takes to achieve a valid grid.
Goal: Ensure that the solution can handle the constraints efficiently.
Steps:
• The grid will always have n x n elements with 0 or 1 values.
• n can be as large as 200, so an efficient solution is necessary.
Assumptions:
• The grid contains distinct rows in terms of binary values.
• It's guaranteed that a valid grid is achievable for some test cases, and for others, it's not possible.
• Input: grid = [[0, 1, 1], [1, 0, 1], [1, 0, 0]]
• Explanation: By swapping rows 0 and 2, followed by swapping rows 1 and 2, we can make the grid valid with 2 moves.
• Input: grid = [[0, 1, 1, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 1, 1, 0]]
• Explanation: Since all the rows are the same, no valid transformation is possible, and the output is -1.
Approach: The approach is to simulate the process of row swaps and track the number of steps required to transform the grid into a valid one.
Observations:
• The problem boils down to counting the trailing zeros of each row and determining whether we can swap rows to make the grid valid.
• We need to focus on minimizing the number of swaps and checking if it's possible to reach a valid state.
Steps:
• For each row, calculate how many trailing zeros it has.
• Try to find an arrangement where rows can be swapped to bring the zeros above the diagonal.
• Perform the minimum number of swaps and return the result.
Empty Inputs:
• The grid will always have at least one row, as n >= 1.
Large Inputs:
• For large grids (up to 200x200), ensure the solution is optimized for time and space efficiency.
Special Values:
• Handle cases where all rows are the same and swaps won't help.
Constraints:
• Ensure that the solution handles grids with n up to 200.
int minSwaps(vector<vector<int>>& grid) {
int n = grid.size();
set<int> found;
vector<int> arr(n, 0);
for(int i = 0; i < n; i++) {
int j = n - 1, cnt = 0;
while(j > -1 && grid[i][j] == 0) {
j--;
cnt++;
}
for(int k = n - 1; k >= 0; k--) {
if(cnt >= k && !found.count(k)) {
found.insert(k);
arr[i] = n - 1 - k;
break;
}
}
}
if(found.size() != n) return -1;
return bubble(arr);
}
int bubble(vector<int> &arr) {
int cnt = 0;
for(int i = 0; i < arr.size(); i++)
for(int j = 1; j < arr.size(); j++)
if(arr[j - 1] > arr[j]) {
swap(arr[j - 1], arr[j]);
cnt++;
}
return cnt;
}
1 : Function Declaration
int minSwaps(vector<vector<int>>& grid) {
This is the function declaration for `minSwaps`, which takes a 2D vector `grid` representing the grid of integers as input.
2 : Variable Initialization
int n = grid.size();
The variable `n` is initialized to the size of the grid. This represents the number of rows in the grid.
3 : Set Declaration
set<int> found;
The set `found` is used to store the indices of rows that have already been processed, ensuring no duplicate indices are used.
4 : Vector Initialization
vector<int> arr(n, 0);
A vector `arr` is initialized with `n` elements, all set to zero. It will store the number of swaps for each row.
5 : For Loop
for(int i = 0; i < n; i++) {
A for loop starts to iterate through each row of the grid.
6 : Variable Initialization
int j = n - 1, cnt = 0;
Two variables are initialized: `j` is set to the last column index, and `cnt` is set to zero. `cnt` tracks the number of trailing zeros in the row.
7 : While Loop
while(j > -1 && grid[i][j] == 0) {
A while loop starts, moving `j` backward until a non-zero element is found or all elements are checked.
8 : Decrement Operation
j--;
Decrements `j` to check the previous column.
9 : Increment Operation
cnt++;
Increments `cnt` as a trailing zero is encountered.
10 : For Loop
for(int k = n - 1; k >= 0; k--) {
A nested for loop iterates backward through the rows to find the appropriate position for the number of trailing zeros in `arr[i]`.
11 : Conditional Check
if(cnt >= k && !found.count(k)) {
Checks if the current `cnt` is greater than or equal to `k` and if `k` has not already been used.
12 : Insert Operation
found.insert(k);
Inserts `k` into the set `found`, marking this row as processed.
13 : Array Update
arr[i] = n - 1 - k;
Updates the `arr[i]` with the number of swaps needed for this row based on the value of `k`.
14 : Break Statement
break;
Breaks out of the inner for loop after the swap has been made.
15 : Conditional Check
if(found.size() != n) return -1;
Checks if the size of the set `found` is not equal to `n`. If true, it returns -1 indicating that it is impossible to rearrange the grid.
16 : Return Statement
return bubble(arr);
Returns the result of the `bubble` function, which calculates the number of swaps required to sort the array `arr`.
17 : Function Declaration
int bubble(vector<int> &arr) {
This function performs a bubble sort on the `arr` and returns the number of swaps made.
18 : Variable Initialization
int cnt = 0;
Initializes `cnt` to count the number of swaps performed during the bubble sort.
19 : For Loop
for(int i = 0; i < arr.size(); i++)
A loop that iterates through the elements of `arr`.
20 : Nested For Loop
for(int j = 1; j < arr.size(); j++)
A nested loop that compares adjacent elements in `arr`.
21 : Conditional Check
if(arr[j - 1] > arr[j]) {
Checks if the current element is greater than the next element.
22 : Swap Operation
swap(arr[j - 1], arr[j]);
Swaps the two elements if the current element is greater than the next.
23 : Increment Operation
cnt++;
Increments the swap counter.
24 : Return Statement
return cnt;
Returns the number of swaps made during the bubble sort.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The time complexity is O(n^2) because we perform row comparisons and potential swaps.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) due to the auxiliary arrays used to track row positions.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus