First Completely Painted Row or Column — Problem & Solution
First Completely Painted Row or Column solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
First Completely Painted Row or Column is a medium coding problem on arrays, hash table and matrix, asked in Amazon, Google and Flipkart interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Matrix
- Asked at: Amazon, Google, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
arr is a permutation of the integers 1 … m·n, and mat is an m × n matrix holding the same integers, each exactly once.
Go through arr in order and paint the matching cell of mat. Return the smallest index i at which some row or some column of mat has become completely painted.
Example 1
Input: arr = [1,3,4,2], mat = [[1,4],[2,3]]
Output: 2
Explanation: After painting 1, 3 and 4 the top row `[1,4]` is full.
Example 2
Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
Output: 3
Explanation: By index 3 the values 2, 4 and 7 — the whole middle column — have been painted.
Example 3
Input: arr = [3,1,4,2], mat = [[1,2],[3,4]]
Output: 1
Explanation: Painting 3 then 1 completes the left column.
Constraints
m == mat.lengthn == mat[i].lengtharr.length == m * n1 <= m, n <= 300arr and mat both hold every integer from 1 to m · n exactly once
Hints for First Completely Painted Row or Column
Hint 1
Searching the matrix for each painted value is
O((m·n)²).Hint 2
Map every value to its cell once, up front.
Hint 3
Keep a counter of unpainted cells per row and per column and watch for one hitting zero.
How to solve First Completely Painted Row or Column
Precompute where each value lives, then paint in one pass while keeping, for each row and each column, how many cells are still unpainted. The first counter to reach zero answers the question.
Approach
- Build a lookup from value to
(row, col)by scanning the matrix once. - Start
rowLeft[i] = nandcolLeft[j] = m. - For each
arr[k], decrement its row's and column's counters. - Return
kthe moment either counter is zero.
Why it works
Counting down is equivalent to checking the whole row after each paint, but costs O(1) instead of O(n). Because the values are a permutation, every paint hits a distinct cell, so a counter can never go below zero and hits zero exactly when its line is complete. An answer always exists — the last paint fills the final row.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Re-scanning a row or column after each paint is quadratic and times out at 300 × 300.
- Both counters must be decremented for the same paint; one cell belongs to a row and a column.
- The answer is the index in
arr, not the painted value.
Reference solution
Python
from typing import List
def firstCompleteIndex(arr: List[int], mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
where = {}
for i in range(m):
for j in range(n):
where[mat[i][j]] = (i, j)
row_left = [n] * m
col_left = [m] * n
for k, v in enumerate(arr):
if v not in where:
continue
i, j = where[v]
row_left[i] -= 1
col_left[j] -= 1
if row_left[i] == 0 or col_left[j] == 0:
return k
return -1Java
public static int firstCompleteIndex(int[] arr, int[][] mat) {
int m = mat.length, n = mat[0].length;
Map<Integer, Integer> where = new HashMap<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) where.put(mat[i][j], i * n + j);
}
int[] rowLeft = new int[m];
int[] colLeft = new int[n];
Arrays.fill(rowLeft, n);
Arrays.fill(colLeft, m);
for (int k = 0; k < arr.length; k++) {
Integer at = where.get(arr[k]);
if (at == null) continue;
int r = at / n, c = at % n;
rowLeft[r]--;
colLeft[c]--;
if (rowLeft[r] == 0 || colLeft[c] == 0) return k;
}
return -1;
}C++
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int m = (int) mat.size(), n = (int) mat[0].size();
unordered_map<int, int> where;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) where[mat[i][j]] = i * n + j;
}
vector<int> rowLeft(m, n), colLeft(n, m);
for (int k = 0; k < (int) arr.size(); k++) {
auto it = where.find(arr[k]);
if (it == where.end()) continue;
int r = it->second / n, c = it->second % n;
rowLeft[r]--;
colLeft[c]--;
if (rowLeft[r] == 0 || colLeft[c] == 0) return k;
}
return -1;
}JavaScript
var firstCompleteIndex = function(arr, mat) {
var m = mat.length, n = mat[0].length, i, j;
var where = new Map();
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) where.set(mat[i][j], i * n + j);
}
var rowLeft = [], colLeft = [];
for (i = 0; i < m; i++) rowLeft.push(n);
for (j = 0; j < n; j++) colLeft.push(m);
for (var k = 0; k < arr.length; k++) {
if (!where.has(arr[k])) continue;
var at = where.get(arr[k]);
var r = Math.floor(at / n), c = at % n;
rowLeft[r]--;
colLeft[c]--;
if (rowLeft[r] === 0 || colLeft[c] === 0) return k;
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets