LC1536: Minimum Swaps to Arrange a Binary Grid

Date: 2026-03-02
Difficulty: MEDIUM
Attempts: 7
Solution link: https://leetcode.com/submissions/detail/1935888178/
Question link: https://leetcode.com/problems/minimum-swaps-to-arrange-a-binary-grid

Intuition

To be updated

Approach

To be updated

Complexity

Time complexity: $O(n^2)$

Space complexity: $O(n)$

Code

class Solution {
    public int minSwaps(int[][] grid) {
        int gridSize = grid.length;
        if (gridSize == 1) {
            return 0;
        }
        int[] rowMostRight1 = new int[gridSize];
        for (int i = 0; i < gridSize; i++) {
            int j;
            for (j = gridSize - 1; j >= 0; j--) {
                if (grid[i][j] == 1) {
                    j += 1;
                    break;
                }
            }
            rowMostRight1[i] = j - 1;
        }

        // Let's try bubble sort
        boolean isSwapped;
        int swapCount = 0;
        for (int i = 0; i < gridSize; i++) {
            if (rowMostRight1[i] > i) {
                int j;
                for (j = i + 1; j < gridSize; j++) {
                    if (rowMostRight1[j] <= i) {
                        swapCount+=j-i;
                        for (int k = j; k > i; k--) {
                            int temp = rowMostRight1[k];
                            rowMostRight1[k] = rowMostRight1[k - 1];
                            rowMostRight1[k - 1] = temp;
                        }
                        break;
                    }
                }
                if (j == gridSize) {
                    return -1;
                }
            }
        }
        return swapCount;
    }
}