You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n].
Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i].
Return the smallest index i at which either a row or a column will be completely painted in mat.
Example 1:
Input: arr = [1,3,4,2], mat = [[1,4],[2,3]] Output: 2 Explanation: The moves are shown in order, and both the first row and second column of the matrix become fully painted at arr[2].
Example 2:
Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]] Output: 3 Explanation: The second column becomes fully painted at arr[3].
Constraints:
m == mat.lengthn = mat[i].lengtharr.length == m * n1 <= m, n <= 1051 <= m * n <= 1051 <= arr[i], mat[r][c] <= m * narr are unique.mat are unique.This approach leverages a dictionary to map each integer to its corresponding position in the matrix. As we iterate over the array `arr`, we update the count of painted cells in the respective row and column. We keep track of the count of painted cells for each row and column, and as soon as any row or column reaches the total count of columns `n` or rows `m`, respectively, we know it is completely painted.
This code initializes a mapping of each integer to its matrix position. It has arrays to track the number of painted cells in each row and column. As it iterates through `arr`, it updates the paint counters. As soon as a counter equals the respective length of a row or column, the function returns the current index.
Java
Time Complexity: O(m * n), as we traverse each element of the matrix to create the position map and then process each element of `arr`.
Space Complexity: O(m * n), storing position information for every element in the matrix.
This approach leverages sets to efficiently track and update the counts of painted cells in rows and columns. For each element processed from `arr`, we check and update the positions in the matrix. If any row or column set attains the size equal to the number of columns or rows, respectively, we determine that deletion criteria are satisfied.
In this JavaScript solution, a Map is used to store positions of matrix elements. Arrays keep track of painted cell counts for rows and columns. As elements of `arr` are processed, these counts are incremented, and checks are performed for full completion.
C++
Time Complexity: O(m * n), accounting for all map operations and checks.
Space Complexity: O(m * n), for storage in the map structure.
| Approach | Complexity |
|---|---|
| Using Direct Mapping of Integers | Time Complexity: O(m * n), as we traverse each element of the matrix to create the position map and then process each element of `arr`. Space Complexity: O(m * n), storing position information for every element in the matrix. |
| Tracking Painted Cells with Set Operations | Time Complexity: O(m * n), accounting for all map operations and checks. Space Complexity: O(m * n), for storage in the map structure. |
First Completely Painted Row or Column - Leetcode 2661 - Python • NeetCodeIO • 6,978 views views
Watch 9 more video solutions →Practice First Completely Painted Row or Column with our built-in code editor and test cases.
Practice on FleetCode