Find the First Paint Step Completing a Row or Column
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Find the First Paint Step Completing a Row or Column
You are given a zero-indexed integer array `arr` and an `m` by `n` integer matrix `mat`. Each contains every integer from `1` through `m * n` exactly once.
Starting with no painted cells, process `arr` from left to right. At index `i`, paint the one cell of `mat` whose value is `arr[i]`.
Return the smallest zero-indexed `i` after which every cell in at least one row or at least one column is painted.
### Examples
**Example 1**
```text
Input: arr = [5,1,6,2,4,3], mat = [[4,1,6],[2,5,3]]
Output: 1
```
The first paint colors the cell containing `5`. The next colors `1`, completing the middle column. No row or column was complete after the first paint.
**Example 2**
```text
Input: arr = [1,3,5,2,4,6], mat = [[6,2],[1,4],[5,3]]
Output: 2
```
After painting `1` and `3`, neither direction is complete. Painting `5` completes the bottom row, which contains `5` and `3`.
### Constraints
- `m == mat.size()` and every row of `mat` has `n` elements.
- `arr.size() == m * n`.
- `1 <= m, n <= 100000`.
- `1 <= m * n <= 100000`.
- `1 <= arr[i], mat[r][c] <= m * n`.
- All entries in `arr` are distinct, and all entries in `mat` are distinct. Thus each input contains the entire stated range.
### Clarifying Questions
- Is the answer a paint count or an array index? Return the index: the first paint has index `0`.
- Does a complete column also qualify? Yes; either direction is sufficient, including a step that completes both.
- What happens with one row or one column? The first paint already completes a column or a row, respectively.
- Is a painted matrix part of the returned result? No; return only the earliest index.
### C++ Interface
```cpp
class Solution {
public:
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
}
};
```
### Reasoning Checkpoints
- Account for both possible completion directions.
- Use the guarantee that each value occurs once in each input.
- Check the one-cell, one-row, and one-column boundaries.
```hint Locate a paint event
Consider how to locate a value's matrix cell without searching the entire matrix again for every paint.
```
Overview: Process a permutation of matrix values as successive paint events. Return the earliest zero-based event index that completes an entire row or column, accounting for rectangular matrices and single-row or single-column boundaries.
