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 0s or 1s. 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 0s.

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 1s 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 0s, or in the second row, there can be a 1 in the second position but all cells after that should be 0s, 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 1s 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 1s 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:

  1. 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 no 1 in the row, the position is considered -1. We store each of these positions in the array pos.

  2. 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 last 1 of each row is located at or before its index i. We scan the rows from the current row i downward, looking for the first row where the last 1 is well-placed (i.e., pos[j] <= i). When a suitable row k is found, the number of swaps needed is k - i, because each swap will move row k one position upwards.

  3. Perform the Swaps: Once the row k is identified, we simulate the swaps by moving the element at index k in the pos array upwards till it reaches index i. This is done using a while loop and decrementing k until it equals i. During each iteration, we swap the elements at positions k and k - 1. This doesn't actually swap the rows in the grid; instead, it mirrors the desired row movements within the pos array.

  4. Optimality and Halt Condition: If, at any time, there is no row below the current i-th row (j >= i where j goes up to n) that has its last 1 at or before i, it means we cannot make the grid valid, and the function returns -1.

  5. 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 the ans.

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:

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

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 Evaluator

Example Walkthrough

Consider the following 3x3 binary grid as an example:

Grid:
0 1 1
1 0 0
0 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 last 1 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:

  1. The outer loop runs from i = 0 to i = n - 1, resulting in a time complexity of O(n) for this part.
  2. Inside the outer loop, there is an inner loop that begins with j = n - 1 down to j = 0 and looks for the last occurrence of a 1 in each row. This loop also runs n times for each row, contributing O(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 size n, which stores the positions of the last 1 in each row, contributes a space complexity of O(n).
  • Constant space is used for the ans, i, j, k variables, which does not depend on n 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement recursion?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More