Minimum Swaps to Arrange a Binary Grid

Medium
1559.

Minimum Swaps to Arrange a Binary Grid

Minimum Swaps to Arrange a Binary Grid is a medium coding problem on arrays, greedy and matrix, asked in Amazon and Microsoft interviews.

grid is an n x n binary matrix. In one step you may swap two adjacent rows.

The grid is valid when every cell strictly above the main diagonal is 0 — that is, grid[i][j] == 0 whenever j > i.

Return the minimum number of steps needed to make the grid valid, or -1 if no sequence of swaps can do it.

Example 1

Input
grid = [[1,1,0],[1,0,0],[0,1,1]]
Output
1
Explanation
Swapping the first two rows gives `[[1,0,0],[1,1,0],[0,1,1]]`.

Example 2

Input
grid = [[0,0,1],[0,1,0],[1,0,0]]
Output
3
Explanation
The last row must climb to the top (two swaps), then the old first row must move below the old second row (one more).

Example 3

Input
grid = [[0,1,0],[1,0,1],[0,0,1]]
Output
-1
Explanation
The top row needs two trailing zeros and no row has them.

Constraints

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • grid[i][j] is 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minSwaps = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Swaps to Arrange a Binary Grid — Problem & Solution

Minimum Swaps to Arrange a Binary Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Swaps to Arrange a Binary Grid is a medium coding problem on arrays, greedy and matrix, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Greedy, Matrix
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

grid is an n x n binary matrix. In one step you may swap two adjacent rows.

The grid is valid when every cell strictly above the main diagonal is 0 — that is, grid[i][j] == 0 whenever j > i.

Return the minimum number of steps needed to make the grid valid, or -1 if no sequence of swaps can do it.

Example 1

Input: grid = [[1,1,0],[1,0,0],[0,1,1]]
Output: 1
Explanation: Swapping the first two rows gives `[[1,0,0],[1,1,0],[0,1,1]]`.

Example 2

Input: grid = [[0,0,1],[0,1,0],[1,0,0]]
Output: 3
Explanation: The last row must climb to the top (two swaps), then the old first row must move below the old second row (one more).

Example 3

Input: grid = [[0,1,0],[1,0,1],[0,0,1]]
Output: -1
Explanation: The top row needs two trailing zeros and no row has them.

Constraints

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • grid[i][j] is 0 or 1

Hints for Minimum Swaps to Arrange a Binary Grid

  1. Hint 1

    Only one number per row matters: how many zeros it ends with.

  2. Hint 2

    Row i (0-indexed) of a valid grid must end with at least n - 1 - i zeros, so the top row has the strictest requirement.

  3. Hint 3

    Fill positions from the top: bring up the nearest row below that meets the requirement, paying one swap per row it passes. If no such row exists, return -1.

How to solve Minimum Swaps to Arrange a Binary Grid

Reduce each row to its count of trailing zeros, then fill the positions top-down, each time bubbling up the closest row that is good enough.

Approach

  1. Compute tz[r], the number of trailing zeros of row r.
  2. For i = 0 .. n-1, find the first j >= i with tz[j] >= n - 1 - i. If none, return -1.
  3. Move it to position i by adjacent swaps (j - i of them), shifting the rows in between down by one, and add j - i to the answer.
  4. Return the total.

Why it works

Requirements only get weaker going down. Any row that satisfies position i also satisfies every later position, so taking the nearest qualifying row is never worse: rows passed over keep their relative order and only move down, where their requirement is weaker, and moving a farther row instead would cost at least as many swaps. A standard exchange argument turns any optimal sequence into the greedy one without increasing its length.

Complexity

  • Time — O(n²)
  • Space — O(n)

Pitfalls

  • Choose the nearest qualifying row, not the one with the most trailing zeros — that would waste a strong row on an easy position and can cost extra swaps.
  • Rows move by adjacent swaps, so moving row j to i costs j - i and shifts the others; simulate the shift.
  • Count trailing zeros, not total zeros.

Reference solution

Python

from typing import List

def minSwaps(grid: List[List[int]]) -> int:
    n = len(grid)
    tz = []
    for row in grid:
        z = 0
        j = n - 1
        while j >= 0 and row[j] == 0:
            z += 1
            j -= 1
        tz.append(z)
    swaps = 0
    for i in range(n):
        j = i
        while j < n and tz[j] < n - 1 - i:
            j += 1
        if j == n:
            return -1
        swaps += j - i
        tz.insert(i, tz.pop(j))
    return swaps

Java

public static int minSwaps(int[][] grid) {
    int n = grid.length;
    int[] tz = new int[n];
    for (int r = 0; r < n; r++) {
        int z = 0;
        for (int c = n - 1; c >= 0 && grid[r][c] == 0; c--) z++;
        tz[r] = z;
    }
    int swaps = 0;
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && tz[j] < n - 1 - i) j++;
        if (j == n) return -1;
        for (; j > i; j--) {
            int t = tz[j]; tz[j] = tz[j - 1]; tz[j - 1] = t;
            swaps++;
        }
    }
    return swaps;
}

C++

int minSwaps(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<int> tz(n, 0);
    for (int r = 0; r < n; r++) {
        int z = 0;
        for (int c = n - 1; c >= 0 && grid[r][c] == 0; c--) z++;
        tz[r] = z;
    }
    int swaps = 0;
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && tz[j] < n - 1 - i) j++;
        if (j == n) return -1;
        for (; j > i; j--) {
            swap(tz[j], tz[j - 1]);
            swaps++;
        }
    }
    return swaps;
}

JavaScript

var minSwaps = function(grid) {
    var n = grid.length, tz = [];
    for (var r = 0; r < n; r++) {
        var z = 0;
        for (var c = n - 1; c >= 0 && grid[r][c] === 0; c--) z++;
        tz.push(z);
    }
    var swaps = 0;
    for (var i = 0; i < n; i++) {
        var j = i;
        while (j < n && tz[j] < n - 1 - i) j++;
        if (j === n) return -1;
        for (; j > i; j--) {
            var t = tz[j]; tz[j] = tz[j - 1]; tz[j - 1] = t;
            swaps++;
        }
    }
    return swaps;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms