2661. First Completely Painted Row or Column

You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n].

Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i].

Return the smallest index i at which either a row or a column will be completely painted in mat.

 Example 1:

Input: arr = [1,3,4,2], mat = [[1,4],[2,3]]
Output: 2
Explanation: The moves are shown in order, and both the first row and second column of the matrix become fully painted at arr[2].

Example 2:

Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
Output: 3
Explanation: The second column becomes fully painted at arr[3].

 Constraints:

• m == mat.length
• n = mat[i].length
• arr.length == m * n
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 1 <= arr[i], mat[r][c] <= m * n
• All the integers of arr are unique.
• All the integers of mat are unique.

Solution 1: Hash Table + Array Counting

JAVA

• class Solution {
      public int firstCompleteIndex(int[] arr, int[][] mat) {
          int m = mat.length, n = mat[0].length;
          Map<Integer, int[]> idx = new HashMap<>();
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  idx.put(mat[i][j], new int[] {i, j});
              }
          }
          int[] row = new int[m];
          int[] col = new int[n];
          for (int k = 0;; ++k) {
              var x = idx.get(arr[k]);
              int i = x[0], j = x[1];
              ++row[i];
              ++col[j];
              if (row[i] == n || col[j] == m) {
                  return k;
              }
          }
      }
  }

C++

• class Solution {
  public:
      int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
          int m = mat.size(), n = mat[0].size();
          unordered_map<int, pair<int, int>> idx;
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  idx[mat[i][j]] = {i, j};
              }
          }
          vector<int> row(m), col(n);
          for (int k = 0;; ++k) {
              auto [i, j] = idx[arr[k]];
              ++row[i];
              ++col[j];
              if (row[i] == n || col[j] == m) {
                  return k;
              }
          }
      }
  };

PYTHON

• class Solution:
      def firstCompleteIndex(self, arr, mat):
          m, n = len(mat), len(mat[0])
          idx = {mat[i][j]: (i, j) for i in range(m) for j in range(n)}
          row = [0] * m
          col = [0] * n
          
          for k, num in enumerate(arr):
              i, j = idx[num]
              row[i] += 1
              col[j] += 1
              if row[i] == n or col[j] == m:
                  return k