Get started

First Completely Painted Row or Column — Medium Problem & Solution

arr is a permutation of the integers 1 … m·n, and mat is an m × n matrix holding the same integers, each exactly once.

  • 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.length
  • n == mat[i].length
  • arr.length == m * n
  • 1 <= m, n <= 300
  • arr and mat both hold every integer from 1 to m · n exactly once

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

  1. Build a lookup from value to (row, col) by scanning the matrix once.
  2. Start rowLeft[i] = n and colLeft[j] = m.
  3. For each arr[k], decrement its row's and column's counters.
  4. Return k the 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 -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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue