First Completely Painted Row or Column

MediumArrayHash TableMatrix

Solution

export function firstCompleteIndex(arr: number[], mat: number[][]): number {
  const [m, n] = [mat.length, mat[0].length];
  const positions = new Map<number, [number, number]>();
  mat.forEach((nums, row) => {
    nums.forEach((value, col) => {
      positions.set(value, [row, col]);
    });
  });
 
  const rowCounts = new Array<number>(m).fill(0);
  const colCounts = new Array<number>(n).fill(0);
  for (let i = 0; i < arr.length; i++) {
    const [row, col] = positions.get(arr[i])!;
    rowCounts[row] += 1;
    colCounts[col] += 1;
 
    if (rowCounts[row] === n || colCounts[col] === m) {
      return i;
    }
  }
  return -1;
}

Complexity

  • Time: O(mn)O(m \cdot n)
  • Space: O(mn)O(m \cdot n)