LeetCode 2661 - First Completely Painted Row or Column

The problem is asking us to simulate a painting process on a 2D matrix. We are given a 1D array arr of integers and an m x n matrix mat, both containing all integers from 1 to m n exactly once.

leetcodemediumarrayhash-tablematrix

LeetCode Problem 2661

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Matrix

Solution

Problem Understanding

The problem is asking us to simulate a painting process on a 2D matrix. We are given a 1D array arr of integers and an m x n matrix mat, both containing all integers from 1 to m * n exactly once. For each integer in arr (in order), we "paint" the cell in mat containing that integer. We are tasked with finding the smallest index i in arr such that, after painting arr[i], at least one entire row or column in mat is fully painted.

The input arr represents the painting sequence. Each integer tells us exactly which cell to paint next, and the matrix mat tells us the position of each number. The output is a single integer - the index of the move where the first row or column is fully painted.

Constraints tell us the matrix can be large: up to 105 rows and columns, but the total number of elements is at most 105. Each number is unique and appears exactly once in both arr and mat. This uniqueness guarantees we never paint the same cell twice, simplifying our bookkeeping.

Important edge cases include:

  • A 1x1 matrix (the answer is always 0 because the only cell is painted first).
  • A single row or single column matrix.
  • The last element in arr completing the row or column.

Approaches

Brute-Force Approach

The naive approach iterates through each element in arr. For each number, we search for its position in mat (O(mn) search), mark it as painted, then check every row and column to see if it is completely painted. This approach works correctly but is extremely slow: searching for each number takes O(mn), and checking all rows and columns is O(m + n) each step, leading to a total time complexity of O((mn)^2). For large inputs, this is unacceptable.

Optimal Approach

The key observation is that we do not need to check the entire matrix each time. Instead, we can precompute the position of each number in mat using a hash map from number → (row, column). We then maintain two arrays: rowCount and colCount, representing how many cells remain to be painted in each row and column. Each time we paint a cell, we decrement the counts for that row and column. If any count reaches zero, we have fully painted a row or column. This reduces the operation per move to O(1), and overall time complexity to O(m * n).

Approach Time Complexity Space Complexity Notes
Brute Force O((m * n)^2) O(m * n) Checks all cells repeatedly for each move
Optimal O(m * n) O(m * n) Uses hash map for positions and counters for rows and columns

Algorithm Walkthrough

  1. Initialize a hash map pos mapping each number in mat to its coordinates (row, col).
  2. Initialize two arrays rowCount of length m and colCount of length n to store how many unpainted cells remain in each row and column. Initially, rowCount[r] = n and colCount[c] = m.
  3. Iterate over each index i in arr.
  4. Retrieve the coordinates (r, c) of arr[i] from pos.
  5. Decrement rowCount[r] and colCount[c] by 1 because this cell is now painted.
  6. Check if rowCount[r] or colCount[c] has reached 0. If yes, return i immediately as this move completes a row or column.
  7. Continue until the first fully painted row or column is found.

Why it works: Each cell is painted exactly once. By maintaining counters for each row and column, we efficiently track progress. When any counter reaches zero, all cells in that row or column have been painted, guaranteeing correctness.

Python Solution

from typing import List

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        pos = {}  # maps number to (row, col)
        for r in range(m):
            for c in range(n):
                pos[mat[r][c]] = (r, c)

        rowCount = [n] * m
        colCount = [m] * n

        for i, num in enumerate(arr):
            r, c = pos[num]
            rowCount[r] -= 1
            colCount[c] -= 1
            if rowCount[r] == 0 or colCount[c] == 0:
                return i
        return -1

In this implementation, we first build the pos mapping to instantly locate each number in mat. We maintain rowCount and colCount to track how many cells remain unpainted. Each iteration processes a move in constant time, decrementing counters and checking if the row or column is complete.

Go Solution

func firstCompleteIndex(arr []int, mat [][]int) int {
    m, n := len(mat), len(mat[0])
    pos := make(map[int][2]int)
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            pos[mat[r][c]] = [2]int{r, c}
        }
    }

    rowCount := make([]int, m)
    colCount := make([]int, n)
    for i := range rowCount {
        rowCount[i] = n
    }
    for i := range colCount {
        colCount[i] = m
    }

    for i, num := range arr {
        r, c := pos[num][0], pos[num][1]
        rowCount[r]--
        colCount[c]--
        if rowCount[r] == 0 || colCount[c] == 0 {
            return i
        }
    }
    return -1
}

The Go solution mirrors the Python logic. The main difference is the use of arrays and slices instead of lists, and tuples are replaced by fixed-length arrays [2]int. Map access and slice operations remain efficient and straightforward.

Worked Examples

Example 1:

arr = [1,3,4,2]
mat = [[1,4],[2,3]]

State after each iteration:

i num Painted Cell (r,c) rowCount colCount Complete?
0 1 (0,0) [1,2] [1,2] No
1 3 (1,1) [1,1] [1,1] No
2 4 (0,1) [0,1] [0,0] Yes (col 1)

Answer: 2

Example 2:

arr = [2,8,7,4,1,3,5,6,9]
mat = [[3,2,5],[1,4,6],[8,7,9]]
i num Painted Cell (r,c) rowCount colCount Complete?
0 2 (0,1) [2,3,3] [3,2,3] No
1 8 (2,0) [2,3,2] [2,2,3] No
2 7 (2,1) [2,3,1] [2,1,3] No
3 4 (1,1) [2,2,1] [2,0,3] Yes (col 1)

Answer: 3

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) We iterate over mat once to build the position map, then over arr once to paint, each in constant time per operation.
Space O(m * n) Storing the position map for each cell and the row/column counters.

Since the maximum number of elements is m * n ≤ 10^5, this solution is efficient.

Test Cases

# Provided examples
assert Solution().firstCompleteIndex([1,3,4,2], [[1,4],[2,3]]) == 2  # Example 1
assert Solution().firstCompleteIndex([2,8,7,4,1,3,5,6,9], [[3,2,5],[1,4,6],[8,7,9]]) == 3  # Example 2

# Edge cases
assert Solution().firstCompleteIndex([1], [[1]]) == 0  # 1x1 matrix
assert Solution().firstCompleteIndex([1,2,3], [[1,2,3