We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Swaps to Arrange a Binary Grid

Difficulty: Medium

Problem Description

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.

Key Insights

  • A valid grid requires all cells (i, j) where i < j to be zeros.
  • The number of zeros needed in each row increases as you move down the grid.
  • Each row can only be swapped with its adjacent rows, which means the rows must be arranged in a specific order for validity.
  • If a row has insufficient trailing zeros compared to its required position, the grid cannot be made valid.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

To solve the problem, we can use a greedy approach with the following steps:

  1. Count Trailing Zeros: For each row, count the number of trailing zeros. This count determines how far down the row can be moved in order to make the grid valid.
  2. Determine Required Zeros: As we iterate through the rows, we keep track of how many zeros are required for each row based on its position in the grid.
  3. Swapping Logic: For each row, if it does not have enough zeros, we need to find a row below it that can be swapped into its place. We count how many swaps are needed to achieve this.
  4. Return the Result: If at any point we cannot find a suitable row to swap into position, we return -1. Otherwise, we return the total number of swaps made.

Code Solutions

def minSwaps(grid):
    n = len(grid)
    # Step 1: Calculate the number of trailing zeros for each row
    trailing_zeros = [0] * n
    for i in range(n):
        count = 0
        for j in range(n - 1, -1, -1):
            if grid[i][j] == 0:
                count += 1
            else:
                break
        trailing_zeros[i] = count
    
    swaps = 0
    for i in range(n):
        # Step 2: Determine required zeros for the current row
        required_zeros = n - 1 - i
        # If current row has less trailing zeros than required
        if trailing_zeros[i] < required_zeros:
            # Try to find a row to swap with
            found = False
            for j in range(i + 1, n):
                if trailing_zeros[j] >= required_zeros:
                    # Perform the swaps
                    for k in range(j, i, -1):
                        trailing_zeros[k], trailing_zeros[k - 1] = trailing_zeros[k - 1], trailing_zeros[k]
                        swaps += 1
                    found = True
                    break
            if not found:
                return -1
    return swaps
← Back to All Questions