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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Swaps to Arrange a Binary Grid

Number: 1658

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an n x n binary grid, a grid is defined as valid if all cells above the main diagonal (from top-left to bottom-right) are zeros. In one step, you can swap any two adjacent rows. The goal is to determine the minimum number of swaps required to transform the grid into a valid grid, or return -1 if it is impossible.

Key Insights

  • For each row, the position of the rightmost 1 determines the row's constraint. Row i is valid if the rightmost 1 is at or before column i.
  • Precompute, for each row, the index of the rightmost 1.
  • Use a greedy strategy: for each row position i, find a row below that can be swapped up (using adjacent row swaps) whose rightmost 1 is at an index ≤ i.
  • Count the number of swaps involved in moving the valid row upward. If no such row exists for any index, return -1.

Space and Time Complexity

Time Complexity: O(n²) – In the worst case, for each row, a scan (or series of swaps) through the remaining rows is done. Space Complexity: O(n) – For storing the rightmost 1 position for each row.

Solution

We first compute an array that captures, for each row, the index of the rightmost 1. Then, iterate through each row i. For each i, look for a row j below (or at) i such that its rightmost one is found at an index ≤ i. If found, simulate the swaps needed by moving row j upward, counting each adjacent swap. If no such row exists for a particular i, the grid cannot be rearranged to be valid, so return -1. Key data structures include an array for storing rightmost ones. The greedy technique ensures minimal swaps are used by always selecting the closest valid candidate.

Code Solutions

def minSwaps(grid):
    n = len(grid)
    # Compute the rightmost one for each row
    rightmost = []
    for row in grid:
        pos = -1
        for j, cell in enumerate(row):
            if cell == 1:
                pos = j
        rightmost.append(pos)
    
    swaps = 0
    # For each row position, pick a row that fits and simulate swaps
    for i in range(n):
        # Find a candidate row with a rightmost one <= i
        pos = i
        while pos < n and rightmost[pos] > i:
            pos += 1
        if pos == n:
            return -1  # Not possible to find a valid row
        # Bring the row to the current position using adjacent swaps
        while pos > i:
            rightmost[pos], rightmost[pos-1] = rightmost[pos-1], rightmost[pos]
            swaps += 1
            pos -= 1
    return swaps

# Example usage:
print(minSwaps([[0,0,1],[1,1,0],[1,0,0]]))  # Expected output: 3
← Back to All Questions