1536. Minimum Swaps to Arrange a Binary Grid
Problem Description
The problem presents a scenario where we have an n x n
binary grid, meaning a grid filled with either 0
s or 1
s. The main diagonal of the grid is the diagonal that runs from the top-left cell (1,1) to the bottom-right cell (n,n). A key rule is defined for the grid to be considered "valid": all cells above the main diagonal must be 0
s.
The task involves making the grid valid by performing a sequence of steps. In each step, you can swap two adjacent rows completely. The question asks us to find and return the minimum number of swaps required to make the grid valid. If it's not possible to make the grid valid through any number of swaps, we must return -1.
To elaborate, the grid becomes valid when, for each row, the trailing 1
s start at or after their row index if we consider the first row and column as index 1. For instance, in the first row, the cells after the main diagonal (which in this case are all the cells except the first one) should be all 0
s, or in the second row, there can be a 1
in the second position but all cells after that should be 0
s, and so on.
Intuition
The intuition behind the solution is based on a greedy approach. To make the grid valid, we can focus individually on each row, starting from the top. For the i-th row to be in a "valid" position, the last 1
in that row must be at or before the i-th column. If the last 1
is beyond the i-th column, the grid is automatically invalid, since we cannot move 1
s to the right of their current positions by swapping rows.
Thus, we iterate through each row and find the position of the last 1
. If we encounter a row that doesn't meet the requirement (has its last 1
beyond the current index), we look for a row below it that does meet the requirement and then perform a series of swaps to bring that row into the i-th position.
This greedy approach works because swapping rows doesn't affect the order of 1
s within the rows themselves, and it is always beneficial to move a row that meets the current requirement as high as possible. By doing so iteratively and carefully counting the number of swaps, we can determine the minimum number of steps needed—or conclude that it's impossible if no such row can be found when needed.
Following this strategy will enable us to transform the grid into a valid state in an optimal way, assuming it is possible. For each row from the top to the bottom, we ensure the condition for validity is satisfied, ultimately resulting in a valid grid or determining the impossibility if the condition cannot be met at any step.
Learn more about Greedy patterns.
Solution Approach
The solution code follows a greedy strategy which is implemented by the following steps:
-
Find the Position of the Last '1': We traverse each row of the grid from the bottom to the top, looking for the last
1
. Once we find it, we note its position. If there is no1
in the row, the position is considered-1
. We store each of these positions in the arraypos
. -
Determine Required Swaps: Starting from the first row (
i = 0
) to the last row (i = n-1
), we ensure, as per the problem description, that the last1
of each row is located at or before its indexi
. We scan the rows from the current rowi
downward, looking for the first row where the last1
is well-placed (i.e.,pos[j] <= i
). When a suitable rowk
is found, the number of swaps needed isk - i
, because each swap will move rowk
one position upwards. -
Perform the Swaps: Once the row
k
is identified, we simulate the swaps by moving the element at indexk
in thepos
array upwards till it reaches indexi
. This is done using a while loop and decrementingk
until it equalsi
. During each iteration, we swap the elements at positionsk
andk - 1
. This doesn't actually swap the rows in the grid; instead, it mirrors the desired row movements within thepos
array. -
Optimality and Halt Condition: If, at any time, there is no row below the current
i
-th row (j >= i
wherej
goes up ton
) that has its last1
at or beforei
, it means we cannot make the grid valid, and the function returns-1
. -
Count and Return Total Swaps: The total number of swaps accumulated throughout this process is stored in the variable
ans
. This represents the minimum number of row swaps required to make the grid valid. The algorithm ensures that each swap moves us closer to the goal without wasted moves, hence the number of swaps calculated is indeed the minimum. If the function doesn't return-1
, it finally returns theans
.
This approach utilizes a greedy algorithm that intelligently selects the immediate best choice (choosing the row that can be moved up with the least number of swaps) without considering the larger problem. This problem has the property that the greedy local choice leads to an optimal global solution, which is not true for all problems but is verified here. The data structure used (pos
array) helps to keep track of the essential information needed to determine swap steps without modifying the original grid, providing an efficient way of simulating row movements.
Here's the part of the code that reflects the above approach:
1pos = [-1] * n
2for i in range(n):
3 for j in range(n - 1, -1, -1):
4 if grid[i][j] == 1:
5 pos[i] = j
6 break
7ans = 0
8for i in range(n):
9 k = -1
10 for j in range(i, n):
11 if pos[j] <= i:
12 ans += j - i
13 k = j
14 break
15 if k == -1:
16 return -1
17 while k > i:
18 pos[k], pos[k - 1] = pos[k - 1], pos[k]
19 k -= 1
20return ans
This code is a direct implementation of the algorithm explained and finds the minimum number of swaps to make the grid valid.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Consider the following 3x3
binary grid as an example:
1Grid: 20 1 1 31 0 0 40 1 1
- Step 1: Find the Position of the Last '1'
Starting from the bottom of the grid, we find the positions of the last 1
in each row:
- Row 3 (bottom row): the last
1
is at position 3. - Row 2: there is no
1
in this row, so the position is considered-1
. - Row 1 (top row): the last
1
is at position 2.
The array pos
is now: [2, -1, 3]
.
- Step 2: Determine Required Swaps
Starting from the first row (index 0
) to the last (index 2
):
For i = 0
(the first row):
- We need the last
1
to be at or before position 1. - We look for a suitable row from index
0
downward. Unfortunately, neither row matches the condition (as the last1
in Row 1 is in position 2). - Since no suitable row is found, we return
-1
.
Thus, in this example, it's not possible to make the grid valid because there is no row below the first that has the last 1
at or before the first position.
If, however, the grid was slightly different and had a possible solution, we would perform the swaps, iterating over the pos
array and moving suitable rows up one by one, then count the swaps to provide the total number of steps required to make the grid valid. But in this case, with the initial grid given, the result is -1
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def min_swaps(self, grid: List[List[int]]) -> int:
5 n = len(grid) # Get the size of the grid.
6 row_max_one_pos = [-1] * n # Store the rightmost one’s position for each row.
7
8 # Loop through each row to find the rightmost one's position.
9 for row in range(n):
10 for col in range(n - 1, -1, -1):
11 if grid[row][col] == 1:
12 row_max_one_pos[row] = col
13 break
14
15 swaps = 0 # Initialize swap counter to 0.
16
17 # Loop through each row to determine if the rows need to be moved to get the required zero rows.
18 for target_row in range(n):
19 found = False # Flag to mark if we found a row that can be swapped.
20 for current_row in range(target_row, n):
21 # Check if the current row can be placed at target_row without further swaps.
22 if row_max_one_pos[current_row] <= target_row:
23 # Increment the swap counter by the distance the row is from its target.
24 swaps += current_row - target_row
25 found = True
26 row_to_move = current_row
27 break
28 # If no such row is found, it's impossible to sort the grid with required zeros condition.
29 if not found:
30 return -1
31
32 # Move the found row up to its target position by swapping with rows above it.
33 while row_to_move > target_row:
34 # Swap positions in the tracker.
35 row_max_one_pos[row_to_move], row_max_one_pos[row_to_move - 1] = row_max_one_pos[row_to_move - 1], row_max_one_pos[row_to_move]
36 row_to_move -= 1 # Go one level up for the next iteration of swapping.
37
38 return swaps # Return the total number of swaps needed.
39
40# Example usage:
41# solution = Solution()
42# swaps_needed = solution.min_swaps([[0, 0, 1], [1, 1, 0], [1, 0, 0]])
43# print(swaps_needed) # Output would be the number of swaps needed, or -1 if it's not possible.
44
1class Solution {
2 public int minSwaps(int[][] grid) {
3 // n represents the size of the grid (since it's an nxn matrix)
4 int n = grid.length;
5
6 // A pos array to hold the position of the rightmost '1' in each row
7 int[] rightmostOnePosition = new int[n];
8 Arrays.fill(rightmostOnePosition, -1); // Initialize with -1
9
10 // Fill in the pos array with the actual positions of the rightmost '1's
11 for (int row = 0; row < n; ++row) {
12 for (int col = n - 1; col >= 0; --col) {
13 if (grid[row][col] == 1) {
14 rightmostOnePosition[row] = col;
15 break; // Stop once the rightmost '1' is found
16 }
17 }
18 }
19
20 // Initialize answer to count the minimum number of swaps required
21 int swapCount = 0;
22 // Iterate each row to put the row in the correct position
23 for (int targetRow = 0; targetRow < n; ++targetRow) {
24 int swapWithRow = -1; // Initialize with -1, indicating no row found yet to swap with
25
26 // Look for a row to swap with the target row
27 for (int currentRow = targetRow; currentRow < n; ++currentRow) {
28 // Check if the current row can be swapped to the target row's position
29 // This is possible if the rightmost '1' in the current row is at or to the left of the targetRow position
30 if (rightmostOnePosition[currentRow] <= targetRow) {
31 // Swap currentRow to the target position
32 swapCount += currentRow - targetRow;
33 swapWithRow = currentRow;
34 break; // Stop, as we have found a row to swap
35 }
36 }
37
38 // If no row is found that can be swapped to the target position, it's not possible to sort the grid
39 if (swapWithRow == -1) {
40 return -1;
41 }
42
43 // Swap the rows by updating the positions of the rightmost '1's
44 // Shuffle the rows one by one up to the final target position
45 while (swapWithRow > targetRow) {
46 // Perform the row swap operation by swapping rightmost '1' positions
47 int temp = rightmostOnePosition[swapWithRow];
48 rightmostOnePosition[swapWithRow] = rightmostOnePosition[swapWithRow - 1];
49 rightmostOnePosition[swapWithRow - 1] = temp;
50 swapWithRow--; // Move up towards the target position
51 }
52 }
53
54 // Return the total number of swaps performed
55 return swapCount;
56 }
57}
58
1#include<vector>
2#include<algorithm> // To include the swap function
3using namespace std;
4
5class Solution {
6public:
7 // Function to find minimum number of swaps to sort the binary grid.
8 int minSwaps(vector<vector<int>>& grid) {
9 int size = grid.size(); // Store the size of the grid
10 vector<int> rightmostOnes(size, -1); // Vector to store the index of rightmost 1 in each row
11
12 // Loop over each row to fill in the rightmostOnes vector
13 for (int i = 0; i < size; ++i) {
14 for (int j = size - 1; j >= 0; --j) {
15 if (grid[i][j] == 1) {
16 rightmostOnes[i] = j; // Update the position of rightmost 1
17 break; // No need to check further left as we found the rightmost 1
18 }
19 }
20 }
21
22 int swapCount = 0; // Counter for the number of swaps
23
24 // Main loop to determine the minimum number of swaps needed
25 for (int i = 0; i < size; ++i) {
26 int j;
27 // Find a row j such that j >= i and the rightmost one in this row
28 // is at or to the left of position i (i.e., rightmostOnes[j] <= i),
29 // which means no swap is needed for this row.
30 for (j = i; j < size; ++j) {
31 if (rightmostOnes[j] <= i) {
32 swapCount += j - i; // Increment the swap count
33 break; // Found a suitable row, so break the loop
34 }
35 }
36
37 if (j == size) {
38 // If we reached the end without finding a row,
39 // there are no such rows, and sorting isn't possible.
40 return -1;
41 }
42
43 // Move the found row up to its final destination by swapping
44 while (j > i) {
45 swap(rightmostOnes[j], rightmostOnes[j - 1]);
46 --j;
47 }
48 }
49
50 return swapCount; // Return the minimum number of swaps
51 }
52};
53
1function minSwaps(grid: number[][]): number {
2 const n: number = grid.length; // n represents the size of the grid
3 const position: number[] = Array(n).fill(-1); // An array to store the rightmost '1' for each row
4
5 // Loop through each row to determine the rightmost '1'
6 for (let i = 0; i < n; ++i) {
7 for (let j = n - 1; j >= 0; --j) { // Start from the rightmost column
8 if (grid[i][j] === 1) {
9 position[i] = j;
10 break; // Once found, break out of the loop to proceed to the next row
11 }
12 }
13 }
14
15 let swaps = 0; // Initialize the swap count
16
17 // Attempt to bring each row to the correct position
18 for (let i = 0; i < n; ++i) {
19 let rowToSwap = -1; // This variable will hold the index of the row we want to swap with i
20
21 // Find the first row below the ith row which can be swapped with the ith row
22 for (let j = i; j < n; ++j) {
23 if (position[j] <= i) {
24 swaps += j - i; // Increment the swap count by the distance the row needs to be moved
25 rowToSwap = j; // Update the index of the row to be swapped
26 break; // Break as we have found the appropriate row
27 }
28 }
29
30 // If we didn't find a row to swap, the target state cannot be achieved
31 if (rowToSwap === -1) {
32 return -1;
33 }
34
35 // Perform the swaps to bring the row up to the correct position
36 while (rowToSwap > i) {
37 // Swap the values
38 [position[rowToSwap], position[rowToSwap - 1]] = [position[rowToSwap - 1], position[rowToSwap]];
39 rowToSwap--; // Move one position up
40 }
41 }
42
43 return swaps; // Return the total number of swaps
44}
45
Time and Space Complexity
Time Complexity
The time complexity of the given code can be analyzed by examining the two nested loops:
- The outer loop runs from
i = 0
toi = n - 1
, resulting in a time complexity ofO(n)
for this part. - Inside the outer loop, there is an inner loop that begins with
j = n - 1
down toj = 0
and looks for the last occurrence of a1
in each row. This loop also runsn
times for each row, contributingO(n)
complexity for each iteration of the outer loop.
The combination of these loops, therefore, gives us a time complexity of O(n^2)
because for each row (n times), it searches the entire row (another n times) in the worst case.
In addition, there is another nested loop where the outer loop also runs n
times (from i = 0
to i = n - 1
), and the inner loop searches for the index j
such that pos[j] <= i
. In the worst case, this inner loop might go through n
elements to find the necessary index, contributing to another O(n^2)
.
The while
loop inside the innermost if
condition moves the elements of the array pos
and runs at most n - 1
times in the first iteration, then n - 2
times, and so on. The sum of this series from 1
to n - 1
is (n - 1)n / 2
, which simplifies to O(n^2)
.
Therefore, combining all parts, the total time complexity remains O(n^2)
as no single part has a complexity higher than that.
Space Complexity
The space complexity of the given code is analyzed by looking at the additional space used by the program besides the input:
- The
pos
array of sizen
, which stores the positions of the last1
in each row, contributes a space complexity ofO(n)
. - Constant space is used for the
ans
,i
,j
,k
variables, which does not depend onn
and, hence, does not add significant space complexity.
Overall, the space complexity is O(n)
as the space required does not increase quadratically with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first