Problem Description

You have an array arr and a matrix mat that together contain all integers from 1 to m×n exactly once (where the matrix has dimensions m×n).

Starting from index 0 in arr, you need to "paint" cells in the matrix. For each element arr[i], you find where that number appears in mat and paint that cell.

Your task is to find the smallest index i in arr such that after painting the cell containing arr[i], you have completely painted either:

• An entire row in the matrix, OR
• An entire column in the matrix

For example, if you have a 2×3 matrix and you're painting cells one by one according to the order in arr, you need to determine at which index in arr you'll first complete painting all cells in any single row or any single column.

The solution tracks this by:

1. Creating a hash table to quickly find where each number is located in the matrix
2. Maintaining counters for how many cells have been painted in each row and column
3. For each element in arr, updating the corresponding row and column counters
4. Returning the index when any row counter reaches n (full row) or any column counter reaches m (full column)

Intuition

The key insight is that we need to efficiently track when a row or column becomes completely painted. Instead of checking the entire row or column each time we paint a cell, we can maintain running counters.

Think of it this way: each time we paint a cell at position (i, j), we're making progress on both row i and column j. A row i is complete when we've painted exactly n cells in it (where n is the number of columns). Similarly, a column j is complete when we've painted exactly m cells in it (where m is the number of rows).

This leads us to the counting approach: maintain two arrays row[m] and col[n] where row[i] counts how many cells we've painted in row i, and col[j] counts how many cells we've painted in column j.

The challenge is that arr contains values (1 to m×n), not positions. We need to quickly find where each value lives in the matrix. This is where the hash table comes in - we preprocess the matrix to create a mapping from each value to its position: idx[value] = (row, column).

Now the algorithm becomes straightforward:

1. For each element in arr, look up its position in the matrix
2. Increment the counters for that row and column
3. Check if either counter has reached its maximum (row reaches n or column reaches m)
4. If yes, we've found our answer - return the current index

This approach is efficient because we only do constant time operations for each element in arr, avoiding the need to repeatedly scan entire rows or columns.

Solution Approach

The solution uses a hash table combined with array counting to efficiently track when a row or column becomes completely painted.

Step 1: Build Position Mapping

First, we create a hash table idx to map each value in the matrix to its position:

idx = {}
for i in range(m):
    for j in range(n):
        idx[mat[i][j]] = (i, j)

This allows us to quickly find where any value from arr is located in the matrix in O(1) time.

Step 2: Initialize Counters

We create two arrays to track painting progress:

row = [0] * m  # counts painted cells in each row
col = [0] * n  # counts painted cells in each column

Step 3: Process Array Elements

For each element arr[k] in the array:

1. Look up its position in the matrix: i, j = idx[arr[k]]
2. Increment the counters for that row and column:

   row[i] += 1
   col[j] += 1

3. Check if either the row or column is now complete:

   if row[i] == n or col[j] == m:
       return k

A row i is complete when row[i] == n (all n columns in that row are painted). A column j is complete when col[j] == m (all m rows in that column are painted).

Time Complexity: O(m * n) - we iterate through the matrix once to build the hash table, then through the array once (which has m * n elements).

Space Complexity: O(m * n) for the hash table, plus O(m + n) for the counting arrays.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• Matrix mat (2×3):

  [[1, 4, 5],
   [2, 3, 6]]

• Array arr: [3, 2, 5, 1, 4, 6]

Goal: Find the smallest index in arr where we complete a full row or column.

Step 1: Build Position Mapping

Create hash table idx mapping each value to its (row, column) position:

idx = {
  1: (0, 0),  # value 1 is at row 0, column 0
  4: (0, 1),  # value 4 is at row 0, column 1
  5: (0, 2),  # value 5 is at row 0, column 2
  2: (1, 0),  # value 2 is at row 1, column 0
  3: (1, 1),  # value 3 is at row 1, column 1
  6: (1, 2)   # value 6 is at row 1, column 2
}

Step 2: Initialize Counters

row = [0, 0]    # for 2 rows
col = [0, 0, 0] # for 3 columns

Step 3: Process Array Elements

Index 0: arr[0] = 3

• Look up position: idx[3] = (1, 1) → paint cell at row 1, column 1
• Update counters: row[1] = 1, col[1] = 1
• Check completion: row 1 needs 3 cells (has 1), column 1 needs 2 cells (has 1)
• Continue

Index 1: arr[1] = 2

• Look up position: idx[2] = (1, 0) → paint cell at row 1, column 0
• Update counters: row[1] = 2, col[0] = 1
• Check completion: row 1 needs 3 cells (has 2), column 0 needs 2 cells (has 1)
• Continue

Index 2: arr[2] = 5

• Look up position: idx[5] = (0, 2) → paint cell at row 0, column 2
• Update counters: row[0] = 1, col[2] = 1
• Check completion: row 0 needs 3 cells (has 1), column 2 needs 2 cells (has 1)
• Continue

Index 3: arr[3] = 1

• Look up position: idx[1] = (0, 0) → paint cell at row 0, column 0
• Update counters: row[0] = 2, col[0] = 2
• Check completion:
  • Row 0 needs 3 cells (has 2) - not complete
  • Column 0 needs 2 cells (has 2) - COMPLETE!
• Return index 3

Visual Progress: After each step, the painted cells (marked with X):

Step 0: [[ ,  ,  ],    Step 1: [[ ,  ,  ],    Step 2: [[ ,  , X],    Step 3: [[X,  , X],
         [ , X,  ]]             [X, X,  ]]             [X, X,  ]]             [X, X,  ]]

At index 3, column 0 becomes fully painted (both cells in that column are painted), so we return 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm consists of two main parts:

1. Building the index dictionary by iterating through the entire matrix: O(m × n)
2. Processing the array arr which has length m × n and performing constant-time operations for each element: O(m × n)

Since both operations are O(m × n) and executed sequentially, the overall time complexity is O(m × n).

Space Complexity: O(m × n)

The space usage includes:

1. The idx dictionary storing positions for all m × n elements: O(m × n)
2. The row array of size m: O(m)
3. The col array of size n: O(n)

Since O(m × n) dominates O(m) + O(n), the overall space complexity is O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Row/Column Complete Conditions

A frequent mistake is mixing up when a row versus a column is complete:

• Wrong: Checking if row[i] == m or col[j] == n
• Correct: A row is complete when row[i] == n (number of columns), and a column is complete when col[j] == m (number of rows)

Why this happens: It's counterintuitive that a row's completion depends on the column count and vice versa. Think of it this way: to complete row i, you need to paint all n cells in that row (one from each column).

Solution:

# Remember: rows have n cells (one per column), columns have m cells (one per row)
if row_paint_count[row_idx] == num_cols or col_paint_count[col_idx] == num_rows:
    return index

2. Off-by-One Error with Return Value

Another mistake is returning the wrong index type:

• Wrong: Returning index + 1 (1-indexed) or the value arr[index]
• Correct: Return index directly (0-indexed position in array)

Solution: The problem asks for the index in arr, not the value at that index or a 1-indexed position.

3. Assuming Matrix Values Start at 0

The problem states values range from 1 to m×n, not 0 to m×n-1. If you accidentally use the matrix values as direct array indices without the hash table, you'll get index errors or incorrect results.

Wrong approach:

# This assumes values are 0-indexed and consecutive
row_idx = arr[index] // num_cols
col_idx = arr[index] % num_cols

Correct approach: Always use the position mapping hash table to find where each value is located.

4. Not Handling Edge Cases

While not explicitly a bug, failing to consider edge cases can cause issues:

• Single row matrix (m=1): Any element completes the row
• Single column matrix (n=1): Any element completes the column
• Single cell matrix (m=n=1): First element completes both

The solution handles these naturally, but it's worth verifying your logic works for these cases during implementation.