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:

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.

Example 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 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

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.