DDSA Solutions

2661. First Completely Painted Row or Column

MediumView on LeetCode
ArrayHash TableMatrix
Time: O(mn)
Space: O(mn)

Problem Overview

Return time when all cells of grid are filled.

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

  1. 1Create reverse map: value -> position. BFS/simulate additions. Track when each cell is filled.
  2. 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
C#
// 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?

Related Problems