First Completely Painted Row or Column
Problem
You are given a 0-indexed array arr and an m × n matrix mat. Both contain every integer in the range [1, m·n] exactly once. Going through arr from index 0, paint the cell of mat that holds arr[i]. Return the smallest index i at which some row or some column of mat becomes completely painted.
arr = [1,3,4,2], mat = [[1,4],[2,3]]2def firstCompleteIndex(arr, mat):
m, n = len(mat), len(mat[0])
pos = {} # value -> (row, col)
for r in range(m):
for c in range(n):
pos[mat[r][c]] = (r, c)
rows = [0] * m # painted count per row
cols = [0] * n # painted count per column
for i, v in enumerate(arr): # paint in arr order
r, c = pos[v]
rows[r] += 1
cols[c] += 1
if rows[r] == n or cols[c] == m: # row or column full
return i
return -1function firstCompleteIndex(arr, mat) {
const m = mat.length, n = mat[0].length;
const pos = new Map(); // value -> [row, col]
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
pos.set(mat[r][c], [r, c]);
const rows = new Array(m).fill(0); // painted per row
const cols = new Array(n).fill(0); // painted per column
for (let i = 0; i < arr.length; i++) { // paint in arr order
const [r, c] = pos.get(arr[i]);
rows[r]++;
cols[c]++;
if (rows[r] === n || cols[c] === m) // row or column full
return i;
}
return -1;
}int firstCompleteIndex(int[] arr, int[][] mat) {
int m = mat.length, n = mat[0].length;
Map<Integer, int[]> pos = new HashMap<>(); // value -> {row, col}
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
pos.put(mat[r][c], new int[]{r, c});
int[] rows = new int[m]; // painted per row
int[] cols = new int[n]; // painted per column
for (int i = 0; i < arr.length; i++) { // paint in arr order
int[] rc = pos.get(arr[i]);
rows[rc[0]]++;
cols[rc[1]]++;
if (rows[rc[0]] == n || cols[rc[1]] == m) // row or column full
return i;
}
return -1;
}int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
unordered_map<int, pair<int,int>> pos; // value -> (row, col)
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
pos[mat[r][c]] = {r, c};
vector<int> rows(m, 0); // painted per row
vector<int> cols(n, 0); // painted per column
for (int i = 0; i < (int)arr.size(); i++) { // paint in arr order
auto [r, c] = pos[arr[i]];
rows[r]++;
cols[c]++;
if (rows[r] == n || cols[c] == m) // row or column full
return i;
}
return -1;
}Explanation
The key observation is that we never have to scan the whole matrix after each paint. Instead we keep two small tally arrays: how many cells are painted so far in each row, and how many in each column.
First we build a hash map pos from every value to its (row, col) location in the matrix. This is a one-time pre-process that lets us jump straight to a value's cell in O(1) when we paint it, instead of searching for it.
Then we walk arr in order. For each value we look up its cell, increment rows[r] and cols[c], and check the two counters that just changed. A row is full exactly when its count reaches n (the number of columns); a column is full when its count reaches m (the number of rows).
The first time either counter hits its target we return the current index i — that is the earliest moment a full row or column appears. Because the values are a permutation of [1, m·n], every lookup succeeds and some line or column is guaranteed to fill eventually.
Example: arr = [1,3,4,2], mat = [[1,4],[2,3]]. Painting 1 then 3 leaves one cell missing in both the first row and the second column; painting 4 at index 2 completes both at once, so the answer is 2.