2661. First Completely Painted Row or Column

Description

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.

 

Solutions

Solution: Hash Map

• Time complexity: O(mn)
• Space complexity: O(mn)

 

JavaScript

/**
 * @param {number[]} arr
 * @param {number[][]} mat
 * @return {number}
 */
const firstCompleteIndex = function (arr, mat) {
  const m = mat.length;
  const n = mat[0].length;
  const rows = Array.from({ length: m }, () => 0);
  const cols = Array.from({ length: n }, () => 0);
  const matMap = new Map();

  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      const value = mat[row][col];

      matMap.set(value, { row, col });
    }
  }

  for (let index = 0; index < m * n; index++) {
    const value = arr[index];
    const { row, col } = matMap.get(value);

    rows[row] += 1;
    cols[col] += 1;

    if (rows[row] === n || cols[col] === m) return index;
  }
  return -1;
};