LeetCode 2661: First Completely Painted Row or Column in C#

LeetCode problem 2661: First Completely Painted Row or Column asks us to determine the first operation at which a row or a column of a given matrix is fully painted. This is an interesting grid and mapping problem that requires efficient handling of operations due to the constraints.

In this article, we’ll break down the problem, analyze the approach, and provide a complete solution in C#.

---

Problem Explanation

You are given:

1. An array arr: Represents the order in which the cells in the matrix will be painted.
2. A matrix mat: A grid containing unique integers ranging from 1 to m * n.

The task is to determine the smallest index i in arr at which a row or column in mat becomes fully painted.

---

Constraints

1. Matrix dimensions: m x n, where 1 <= m, n <= 10^5.
2. Number of elements: 1 <= m * n <= 10^5.
3. Both arr and mat contain all integers from 1 to m * n, and all values are unique.

---

Approach

Given the constraints, we need an efficient solution. A direct approach that simulates painting the matrix would be too slow. Instead, we use a mapping and counting approach.

Key Steps:

1. Map Values to Coordinates:

   • Create a dictionary to map each value in mat to its corresponding (row, column).

2. Track Painted Rows and Columns:

   • Maintain two arrays: rowCount and colCount, to track how many cells in each row and column are painted.

3. Iterate Over arr:

   • For each value in arr, determine the corresponding row and column using the dictionary.
   • Increment the counters for the row and column.
   • Check if the row or column is fully painted.

4. Stop at First Complete:

   • Return the index of the first operation where a row or column becomes fully painted.

---

C# Solution

Here’s the full implementation:

using System;
using System.Collections.Generic;

public class Solution
{
    public int FirstCompleteIndex(int[] arr, int[][] mat)
    {
        int m = mat.Length;     // Number of rows
        int n = mat[0].Length;  // Number of columns
        
        // Step 1: Map matrix values to their coordinates
        var valueToCoordinates = new Dictionary<int, (int row, int col)>();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                valueToCoordinates[mat[i][j]] = (i, j);
            }
        }
        
        // Step 2: Initialize row and column counters
        int[] rowCount = new int[m];
        int[] colCount = new int[n];
        
        // Step 3: Iterate through arr to paint cells
        for (int i = 0; i < arr.Length; i++)
        {
            int value = arr[i];
            var (row, col) = valueToCoordinates[value];

            // Increment the row and column counters
            rowCount[row]++;
            colCount[col]++;
            
            // Check if the row or column is fully painted
            if (rowCount[row] == n || colCount[col] == m)
            {
                return i;  // Return the 0-based index
            }
        }
        
        return -1;  // This should never happen given the problem constraints
    }
}

---

How the Solution Works

1. Mapping Values to Coordinates:

   • The dictionary valueToCoordinates allows us to quickly locate the (row, col) position of any value in O(1) time.

2. Counting Painted Cells:

   • The rowCount and colCount arrays are used to efficiently track how many cells in each row and column have been painted.

3. Stopping Early:

   • The solution stops as soon as a row or column is fully painted, ensuring optimal performance.

---

Example Walkthrough

Example 1:

Input:

int[] arr = {1, 3, 4, 2};
int[][] mat = {
    new int[] {1, 4},
    new int[] {2, 3}
};

Execution:

1. Map matrix values to coordinates:
   {1: (0, 0), 4: (0, 1), 2: (1, 0), 3: (1, 1)}.
2. Process arr:
   • Paint 1: rowCount = [1, 0], colCount = [1, 0]
   • Paint 3: rowCount = [1, 1], colCount = [1, 1]
   • Paint 4: rowCount = [2, 1], colCount = [1, 2] → Row 0 is fully painted.
3. Output: 2

---

Comparison Table

Feature	Relational Databases	NoSQL Databases
Input Size Handling	Up to 10^5 rows	Efficient for large datasets
Mapping Complexity	O(1) lookup	Same for key-value stores
Scalability	Limited	Horizontally scalable

---

Summary

This problem showcases how mapping and counting can simplify operations on matrices. By efficiently tracking painted cells, the solution avoids unnecessary computations and scales well with large inputs.

Try this approach to gain deeper insights into solving grid and matrix problems effectively!