Skip to content

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
32
class Solution {
 public:
  int minSwaps(vector<vector<int>>& grid) {
    const int n = grid.size();
    int ans = 0;
    // suffixZeros[i] := the number of suffix zeros in the i-th row
    vector<int> suffixZeros;

    for (const vector<int> 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 - 1 - i;
      // Get the first row with suffix zeros >= `neededZeros` in
      // suffixZeros[i:..n).
      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 the rows[j] to the 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] := the number of suffix zeros in the 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 - 1 - i;
      // Get the first row with suffix zeros >= `neededZeros` in suffixZeros[i:..n).
      final int j = getFirstRowWithEnoughZeros(suffixZeros, i, neededZeros);
      if (j == -1)
        return -1;
      // Move the rows[j] to the 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:..n).
  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] := the number of suffix zeros in the 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 - 1 - i
      # Get the first row with suffix zeros >= `neededZeros` in suffixZeros[i:..n).
      j = next((j for j in range(i, n) if suffixZeros[j] >= neededZeros), -1)
      if j == -1:
        return -1
      # Move the rows[j] to the rows[i].
      for k in range(j, i, -1):
        suffixZeros[k] = suffixZeros[k - 1]
      ans += j - i

    return ans