2661. First Completely Painted Row or Column

Time: O(mn)

Space: O(mn)

Intuition

Return time when all cells of grid are filled. Simulate flood fill BFS from time 0. For each cell added at time t, t is its time.

Algorithm

1Create reverse map: value -> position. BFS/simulate additions. Track when each cell is filled.
2At time t: cell with value t is added. Return when all n*m cells filled.

Common Pitfalls

•Cells are filled one by one in order 1..n*m. Time when all filled = n*m.

2661.cs

// Approach: Map values to (row, col); track row/col fill counts; return index when any fills completely.
// Time: O(mn) Space: O(mn)

public class Solution
{
    public int FirstCompleteIndex(int[] arr, int[][] mat)
    {
        int m = mat.Length;
        int n = mat[0].Length;
        // rows[i] := the number of painted grid in the i-th row
        int[] rows = new int[m];
        // cols[j] := the number of painted grid in the j-th column
        int[] cols = new int[n];
        // numToRow[num] := the i-th row of `num` in `mat`
        int[] numToRow = new int[m * n + 1];
        // numToCol[num] := the j-th column of `num` in `mat`
        int[] numToCol = new int[m * n + 1];

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                numToRow[mat[i][j]] = i;
                numToCol[mat[i][j]] = j;
            }
        }

        for (int i = 0; i < arr.Length; ++i)
        {
            if (++rows[numToRow[arr[i]]] == n)
                return i;
            if (++cols[numToCol[arr[i]]] == m)
                return i;
        }

        throw new ArgumentException();
    }
}

Was this solution helpful?