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

minSwaps.js

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minSwaps = function(grid) {
    const n = grid.length;

    // Step 1: For each row, compute the index of the rightmost 1.
    // If a row has no 1s, store -1.
    const rightmost = new Array(n).fill(0);

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

    // Step 2: Greedily place rows from top to bottom.
    // For row i, we need rightmost[row] <= i.
    let swaps = 0;

    for (let i = 0; i < n; i++) {
        // Find the first row r >= i whose rightmost 1 is <= i.
        let target = -1;
        for (let r = i; r < n; r++) {
            if (rightmost[r] <= i) {
                target = r;
                break;
            }
        }

        // If no such row exists, it's impossible.
        if (target === -1) return -1;

        // Step 3: Bubble row 'target' up to position i.
        // Each upward move is one adjacent swap.
        while (target > i) {
            // Swap rightmost[target] with rightmost[target - 1]
            [rightmost[target], rightmost[target - 1]] = [rightmost[target - 1], rightmost[target]];
            swaps++;
            target--;
        }
    }

    return swaps;
};