Skip to content

2661. First Completely Painted Row or Column 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 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
class Solution {
 public:
  int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
    const int m = mat.size();
    const int n = mat[0].size();
    // rows[i] := the number of painted grid in the i-th row
    vector<int> rows(m);
    // cols[j] := the number of painted grid in the j-th column
    vector<int> cols(n);
    // numToRow[num] := the i-th row of `num` in `mat`
    vector<int> numToRow(m * n + 1);
    // numToCol[num] := the j-th column of `num` in `mat`
    vector<int> numToCol(m * n + 1);

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        numToRow[mat[i][j]] = i;
        numToCol[mat[i][j]] = j;
      }

    for (int i = 0; i < arr.size(); ++i) {
      if (++rows[numToRow[arr[i]]] == n)
        return i;
      if (++cols[numToCol[arr[i]]] == m)
        return i;
    }

    throw;
  }
};

 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
class Solution {
  public int firstCompleteIndex(int[] arr, int[][] mat) {
    final int m = mat.length;
    final int n = mat[0].length;
    // rows[i] := the number of painted grid in the i-th row
    int[] rows = new int[m];
    // cols[j] := the number of painted grid in the j-th column
    int[] cols = new int[n];
    // numToRow[num] := the i-th row of `num` in `mat`
    int[] numToRow = new int[m * n + 1];
    // numToCol[num] := the j-th column of `num` in `mat`
    int[] numToCol = new int[m * n + 1];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        numToRow[mat[i][j]] = i;
        numToCol[mat[i][j]] = j;
      }

    for (int i = 0; i < arr.length; ++i) {
      if (++rows[numToRow[arr[i]]] == n)
        return i;
      if (++cols[numToCol[arr[i]]] == m)
        return i;
    }

    throw new IllegalArgumentException();
  }
}

 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
class Solution:
  def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
    m = len(mat)
    n = len(mat[0])
    # rows[i] := the number of painted grid in the i-th row
    rows = [0] * m
    # cols[j] := the number of painted grid in the j-th column
    cols = [0] * n
    # numToRow[num] := the i-th row of `num` in `mat`
    numToRow = [0] * (m * n + 1)
    # numToCol[num] := the j-th column of `num` in `mat`
    numToCol = [0] * (m * n + 1)

    for i, row in enumerate(mat):
      for j, num in enumerate(row):
        numToRow[num] = i
        numToCol[num] = j

    for i, a in enumerate(arr):
      rows[numToRow[a]] += 1
      if rows[numToRow[a]] == n:
        return i
      cols[numToCol[a]] += 1
      if cols[numToCol[a]] == m:
        return i