1536. Minimum Swaps to Arrange a Binary Grid

/**
 * Problem: LeetCode 1536 - Minimum Swaps to Arrange a Binary Grid
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] trailingZeros = new int[n];

        // Step 1: Count trailing zeros for each row
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 0) {
                    count++;
                } else {
                    break;
                }
            }
            trailingZeros[i] = count;
        }

        int swaps = 0;

        // Step 2: For each row i, find the first available row with >= (n - 1 - i) trailing zeros
        for (int i = 0; i < n; i++) {
            int requiredZeros = n - 1 - i;
            int foundIdx = -1;

            for (int j = i; j < n; j++) {
                if (trailingZeros[j] >= requiredZeros) {
                    foundIdx = j;
                    break;
                }
            }

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

            // Step 3: Shift the qualifying row up to position i
            swaps += (foundIdx - i);
            int temp = trailingZeros[foundIdx];
            for (int j = foundIdx; j > i; j--) {
                trailingZeros[j] = trailingZeros[j - 1];
            }
            trailingZeros[i] = temp;
        }

        return swaps;
    }
}

"""
Problem: LeetCode 1536 - Minimum Swaps to Arrange a Binary Grid
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        n = len(grid)
        trailing_zeros = []

        # Step 1: Count trailing zeros for each row
        for row in grid:
            count = 0
            for val in reversed(row):
                if val == 0:
                    count += 1
                else:
                    break
            trailing_zeros.append(count)

        swaps = 0

        # Step 2: For each row i, find first row with at least (n - 1 - i) zeros
        for i in range(n):
            required = n - 1 - i
            found_idx = -1
            for j in range(i, n):
                if trailing_zeros[j] >= required:
                    found_idx = j
                    break

            if found_idx == -1:
                return -1

            # Step 3: Shift row to index i
            swaps += found_idx - i
            val = trailing_zeros.pop(found_idx)
            trailing_zeros.insert(i, val)

        return swaps

/**
 * Problem: LeetCode 1536 - Minimum Swaps to Arrange a Binary Grid
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> trailingZeros(n);

        // Step 1: Count trailing zeros for each row
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 0) {
                    count++;
                } else {
                    break;
                }
            }
            trailingZeros[i] = count;
        }

        int swaps = 0;

        // Step 2: Greedy selection of closest row meeting requirement
        for (int i = 0; i < n; i++) {
            int required = n - 1 - i;
            int foundIdx = -1;

            for (int j = i; j < n; j++) {
                if (trailingZeros[j] >= required) {
                    foundIdx = j;
                    break;
                }
            }

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

            // Step 3: Shift qualifying row up to index i
            swaps += (foundIdx - i);
            int temp = trailingZeros[foundIdx];
            for (int j = foundIdx; j > i; j--) {
                trailingZeros[j] = trailingZeros[j - 1];
            }
            trailingZeros[i] = temp;
        }

        return swaps;
    }
};

/**
 * Problem: LeetCode 1536 - Minimum Swaps to Arrange a Binary Grid
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minSwaps = function(grid) {
    const n = grid.length;
    const trailingZeros = new Array(n);

    // Step 1: Count trailing zeros for each row
    for (let i = 0; i < n; i++) {
        let count = 0;
        for (let j = n - 1; j >= 0; j--) {
            if (grid[i][j] === 0) {
                count++;
            } else {
                break;
            }
        }
        trailingZeros[i] = count;
    }

    let swaps = 0;

    // Step 2: Greedy search for first qualifying row
    for (let i = 0; i < n; i++) {
        const required = n - 1 - i;
        let foundIdx = -1;

        for (let j = i; j < n; j++) {
            if (trailingZeros[j] >= required) {
                foundIdx = j;
                break;
            }
        }

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

        // Step 3: Bubble up qualifying row to index i
        swaps += (foundIdx - i);
        const temp = trailingZeros[foundIdx];
        for (let j = foundIdx; j > i; j--) {
            trailingZeros[j] = trailingZeros[j - 1];
        }
        trailingZeros[i] = temp;
    }

    return swaps;
};