First Completely Painted Row or Column

First Completely Painted Row or Column

1. What is this problem about?

The First Completely Painted Row or Column interview question is a grid simulation task. You are given an $m imes n$ matrix and an array arr that specifies an order in which cells are "painted." You need to find the earliest index in arr such that either a full row or a full column in the matrix has been painted.

2. Why is this asked in interviews?

Companies like Google and Bloomberg ask this to test your ability to use Hash Tables for fast coordinate lookups. It evaluations if you can avoid redundant matrix scans ($O(M \cdot N)$) by maintaining counters for each row and column. It tests efficiency in Matrix interview patterns.

3. Algorithmic pattern used

This problem follows the Coordinate Mapping and Frequency Counting pattern.

1. Mapping: Use a hash map (or array) to store the (row, col) coordinates for every value in the matrix. This allows $O(1)$ lookup of a value's position.
2. Counters: Maintain two arrays: rowCount of size $m$ and colCount of size $n$.
3. Iteration: For each value in arr:
   • Retrieve its (r, c) from the map.
   • Increment rowCount[r] and colCount[c].
   • If rowCount[r] == n OR colCount[c] == m, the row/column is complete.
4. Result: Return the current index in arr.

4. Example explanation

Matrix $2 imes 2$: [[1, 2], [3, 4]]. arr = [1, 4, 2, 3].

1. Paint 1: (0,0). row0=1, col0=1.
2. Paint 4: (1,1). row1=1, col1=1.
3. Paint 2: (0,1). row0=2. Row 0 has 2 columns, it is now full! Result: Index 2.

5. Common mistakes candidates make

• Matrix Scans: Trying to check the whole row/column for every painted cell ($O(N \cdot M)$ or $O(N+M)$ inside the loop), which is too slow.
• Inefficient Lookup: Searching for the value in the matrix instead of using a coordinate map.
• Off-by-one: Mistakes in checking the target counts ($m$ for columns, $n$ for rows).

6. Interview preparation tip

Always look for ways to store "aggregate" information like row/column sums or counts. This transforms a 2D grid check into a 1D array lookup, which is a common optimization in Hash Table interview patterns.