Daily LeetCode - by Vítor Belim

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.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

Example 1:

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3

Example 2:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0

Constraints:

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

Solutions

This function computes the minimum number of adjacent row swaps required to transform a binary grid into a valid arrangement where each row i has its rightmost 1 at position i or earlier. It starts by recording the column position of each row's rightmost 1 in a pos array, then iterates through each row index from left to right. For each position, it searches for an unvisited row with a rightmost 1 at or before the target column, increments the swap count by the distance needed, and rearranges the pos array using adjacent swaps. If no suitable row exists for any position, it returns -1 (indicating an impossible configuration).

Language: javascript(2026-03-02 09:42)DONE

CPU Performance75.00%

Memory Performance100.00%

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minSwaps = function (grid) {
    const n = grid.length;
    const pos = new Array(n).fill(-1);

    for (let i = 0; i < n; i++) {
        for (let j = n - 1; j >= 0; j--) {
            if (grid[i][j] === 1) {
                pos[i] = j;
                break;
            }
        }
    }

    let ans = 0;

    for (let i = 0; i < n; i++) {
        let k = -1;

        for (let j = i; j < n; j++) {
            if (pos[j] <= i) {
                ans += j - i;
                k = j;
                break;
            }
        }

        if (k === -1) {
            return -1;
        }

        for (let j = k; j > i; j--) {
            const temp = pos[j];
            pos[j] = pos[j - 1];
            pos[j - 1] = temp;
        }
    }

    return ans;
};

Description

Solutions

AI Explanation