2661. First Completely Painted Row or Column - Detailed Explanation

Problem Statement

You are given a grid with m rows and n columns and an array paints where each element is a pair [r, c] indicating that the cell at row r and column c is painted in that operation (cells are typically 0-indexed). The operations are performed in order. Your task is to determine the earliest operation (by its index in the sequence) after which at least one row or one column is completely painted (i.e. every cell in that row or column has been painted). If no row or column becomes completely painted, return -1.

Example 1

• Input:
  • m = 3, n = 4
  • paints = [[0,1], [1,2], [0,0], [2,3], [0,2], [0,3]]
• Output: 5
• Explanation:
  After processing the operations in order:
  1. Paint cell (0,1) → Row 0 painted: {1}
  2. Paint cell (1,2) → Row 1 painted: {2}
  3. Paint cell (0,0) → Row 0 painted: {0,1}
  4. Paint cell (2,3) → Row 2 painted: {3}
  5. Paint cell (0,2) → Row 0 painted: {0,1,2}
  6. Paint cell (0,3) → Row 0 painted: {0,1,2,3}
  At step 6 (index 5), row 0 is fully painted (all 4 columns). Hence, return 5.

Example 2

• Input:
  • m = 2, n = 3
  • paints = [[1,0], [0,0], [1,1], [1,2]]
• Output: 3
• Explanation:
  The operations eventually fully paint row 1 after the 4th operation (index 3).

Hints to Solve the Problem

• Simulate Painting:
  Instead of simulating the entire grid cell-by-cell, you can maintain counters for each row and each column to track how many cells have been painted.

• Update Counters:
  For each painting operation, update the counter for the row and the counter for the column of the painted cell. Then, check whether the counter equals the number of columns (for a row) or the number of rows (for a column).

• Avoid Duplicates:
  Ensure that you do not count the same cell twice. (In many problem settings, it is assumed each cell is painted only once. If not, you should check if a cell is already painted before updating.)

Approaches to Solve the Problem

Approach 1: Direct Simulation Using Row and Column Counters

Idea:

• Maintain two arrays:

  • rowCount[m]: Number of painted cells in each row.
  • colCount[n]: Number of painted cells in each column.

• Iterate over the list of painting operations (keeping track of the current operation index).

• For each operation, update the corresponding row and column counters.

• Check immediately whether rowCount[r] equals n (all cells in row r are painted) or whether colCount[c] equals m (all cells in column c are painted). If yes, return the current operation index.

• If the entire sequence is processed without any row or column being fully painted, return -1.

Complexity Analysis:

• Time Complexity: O(k), where k is the number of operations (each operation is processed in constant time).

• Space Complexity: O(m + n) for the two counter arrays, plus O(m*n) if you decide to track individual painted cells—but you can avoid that if the problem guarantees no duplicate operations.

Step-by-Step Walkthrough (Using Counters)

1. Initialize Counters:

   • Create an array rowCount of length m initialized with zeros.
   • Create an array colCount of length n initialized with zeros.
   • (Optional) Create a 2D boolean array painted of size m x n to track if a cell is already painted (if duplicate operations are possible).

2. Process Each Operation:
   For each operation (with index i) given by [r, c]:

   • If you are tracking duplicates and cell (r, c) is already painted, skip the update.

   • Otherwise, mark cell (r, c) as painted.

   • Increment rowCount[r] and colCount[c].

   • Check if rowCount[r] == n (i.e. the entire row r is painted) or if colCount[c] == m (i.e. the entire column c is painted).

   • If either condition is met, return the current index i.

3. Finish Processing:
   If no row or column is completely painted after all operations, return -1.

Code Implementations

Python Code