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:
- An array
arr: Represents the order in which the cells in the matrix will be painted. - A matrix
mat: A grid containing unique integers ranging from1tom * n.
The task is to determine the smallest index i in arr at which a row or column in mat becomes fully painted.
Constraints
- Matrix dimensions:
m x n, where1 <= m, n <= 10^5. - Number of elements:
1 <= m * n <= 10^5. - Both
arrandmatcontain all integers from1tom * 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:
-
Map Values to Coordinates:
- Create a dictionary to map each value in
matto its corresponding(row, column).
- Create a dictionary to map each value in
-
Track Painted Rows and Columns:
- Maintain two arrays:
rowCountandcolCount, to track how many cells in each row and column are painted.
- Maintain two arrays:
-
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.
- For each value in
-
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
-
Mapping Values to Coordinates:
- The dictionary
valueToCoordinatesallows us to quickly locate the(row, col)position of any value inO(1)time.
- The dictionary
-
Counting Painted Cells:
- The
rowCountandcolCountarrays are used to efficiently track how many cells in each row and column have been painted.
- The
-
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:
- Map matrix values to coordinates:
{1: (0, 0), 4: (0, 1), 2: (1, 0), 3: (1, 1)}. - 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.
- Paint
- 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!
