1536. Minimum Swaps to Arrange a Binary Grid

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

Solution: Bubble Sort

• Time complexity: O(n²)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
const minSwaps = function (grid) {
  const n = grid.length;
  const zeroSuffixCounts = grid.map(row => n - row.lastIndexOf(1) - 1);
  let result = 0;

  for (let row = 0; row < n; row++) {
    const targetZeroSuffixCounts = n - row - 1;
    let swapRow = row;

    while (swapRow < n && zeroSuffixCounts[swapRow] < targetZeroSuffixCounts) swapRow += 1;
    if (swapRow === n) return -1;
    for (let currentRow = swapRow; currentRow > row; currentRow--) {
      [zeroSuffixCounts[currentRow], zeroSuffixCounts[currentRow - 1]] = [
        zeroSuffixCounts[currentRow - 1],
        zeroSuffixCounts[currentRow],
      ];
      result += 1;
    }
  }
  return result;
};