# 1536. Minimum Swaps to Arrange a Binary Grid

• Time: $O(n^2)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public: int minSwaps(vector>& grid) { const int n = grid.size(); int ans = 0; // suffixZeros[i] := # of suffix zeros in i-th row vector suffixZeros; for (const vector row : grid) { const auto itLastOne = find(row.rbegin(), row.rend(), 1); const int suffixZeroCount = distance(row.rbegin(), itLastOne); suffixZeros.push_back(suffixZeroCount); } for (int i = 0; i < n; ++i) { const int neededZeros = n - i - 1; // Get the first row w/ suffix zeros >= neededZeros in suffixZeros[i:]. const auto it = find_if(suffixZeros.begin() + i, suffixZeros.end(), [&](int count) { return count >= neededZeros; }); if (it == suffixZeros.end()) return -1; const int j = distance(suffixZeros.begin(), it); // Move rows[j] to rows[i]. for (int k = j; k > i; --k) suffixZeros[k] = suffixZeros[k - 1]; ans += j - i; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public int minSwaps(int[][] grid) { final int n = grid.length; int ans = 0; // suffixZeros[i] := # of suffix zeros in i-th row int[] suffixZeros = new int[n]; for (int i = 0; i < grid.length; ++i) suffixZeros[i] = getSuffixZeroCount(grid[i]); for (int i = 0; i < n; ++i) { final int neededZeros = n - i - 1; // Get the first row w/ suffix zeros >= neededZeros in suffixZeros[i:]. final int j = getFirstRowWithEnoughZeros(suffixZeros, i, neededZeros); if (j == -1) return -1; // Move rows[j] to rows[i]. for (int k = j; k > i; --k) suffixZeros[k] = suffixZeros[k - 1]; ans += j - i; } return ans; } private int getSuffixZeroCount(int[] row) { for (int i = row.length - 1; i >= 0; --i) if (row[i] == 1) return row.length - i - 1; return row.length; } // Returns first row that has suffix zeros > neededZeros in suffixZeros[i:]. private int getFirstRowWithEnoughZeros(int[] suffixZeros, int i, int neededZeros) { for (int j = i; j < suffixZeros.length; ++j) if (suffixZeros[j] >= neededZeros) return j; return -1; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def minSwaps(self, grid: List[List[int]]) -> int: n = len(grid) ans = 0 # suffixZeros[i] := # of suffix zeros in i-th row suffixZeros = [n if 1 not in row else row[::-1].index(1) for row in grid] for i in range(n): neededZeros = n - i - 1 # Get the first row w/ suffix zeros >= neededZeros in suffixZeros[i:]. j = next((j for j in range(i, n) if suffixZeros[j] >= neededZeros), -1) if j == -1: return -1 # Move rows[j] to rows[i]. for k in range(j, i, -1): suffixZeros[k] = suffixZeros[k - 1] ans += j - i return ans