First Completely Painted Row or Column
MedPrompt
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 * n- All the integers of
arrare unique. - All the integers of
matare unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. For each number in arr, we perform a full scan of the matrix mat to find its location. We use an auxiliary boolean matrix to keep track of which cells have been painted. After painting a cell, we check its entire row and column to see if they have become completely painted.
Algorithm
- Create a boolean matrix
paintedof the same dimensions asmat, initialized tofalse. - Iterate through the input array
arrfrom indexi = 0toarr.length - 1. - For each number
val = arr[i]:- Search the entire
matto find the rowrand columncwheremat[r][c] == val. - Mark the cell as painted by setting
painted[r][c] = true. - Check if the entire row
ris painted by iterating through its columns. - If the row is complete, return
i. - Check if the entire column
cis painted by iterating through its rows. - If the column is complete, return
i.
- Search the entire
Walkthrough
The brute-force method involves iterating through each element of the arr. In each iteration, we take the number and search for it within the mat. This search operation itself takes O(m*n) time. Once found at (r, c), we mark this position in a separate painted grid. Then, we check if row r is complete by scanning all n cells in that row, and similarly, check column c by scanning all m cells. This entire process (search, mark, check) is repeated for each number in arr until a complete row or column is found.
class Solution { public int firstCompleteIndex(int[] arr, int[][] mat) { int m = mat.length; int n = mat[0].length; boolean[][] painted = new boolean[m][n]; for (int i = 0; i < arr.length; i++) { int val = arr[i]; int r = -1, c = -1; // Find val in mat find_val: for (int row = 0; row < m; row++) { for (int col = 0; col < n; col++) { if (mat[row][col] == val) { r = row; c = col; break find_val; } } } painted[r][c] = true; // Check row r boolean rowComplete = true; for (int col = 0; col < n; col++) { if (!painted[r][col]) { rowComplete = false; break; } } if (rowComplete) { return i; } // Check column c boolean colComplete = true; for (int row = 0; row < m; row++) { if (!painted[row][c]) { colComplete = false; break; } } if (colComplete) { return i; } } return -1; // Should not be reached }}Complexity
Time
O((m*n)^2). The outer loop runs up to `k` times (where `k` is the answer index, worst case `m*n`). Inside the loop, searching the matrix takes O(m*n). This results in a total complexity of O(k * m * n), which is O((m*n)^2) in the worst case.
Space
O(m * n) to store the `painted` boolean matrix.
Trade-offs
Pros
Simple to conceptualize and implement.
Uses a straightforward simulation of the problem statement.
Cons
Extremely inefficient due to repeated searching of the matrix.
Will result in a 'Time Limit Exceeded' error for larger inputs.
This approach improves upon the brute-force method by optimizing the search for each number's location. We first pre-process mat to store the coordinates of every number in a hash map or an array. This allows for an O(1) lookup of a number's position. The rest of the simulation, which involves marking cells in a boolean grid and then checking the entire row and column for completion, remains the same.
Algorithm
- Create a map or an array
positionsto store the coordinates of each number inmat. - Populate
positionsby iterating throughmatonce. - Initialize a boolean matrix
paintedof sizem x nto allfalse. - Iterate through
arrwith indexi. - For each number
val = arr[i]:- Get its coordinates
(r, c)frompositionsin O(1) time. - Set
painted[r][c] = true. - Check the entire row
rand columncin thepaintedmatrix for completion. - If either is complete, return
i.
- Get its coordinates
Walkthrough
To avoid the costly O(mn) search in every step, we can pre-compute the locations of all numbers. We create a map where keys are the numbers from mat and values are their (row, col) coordinates. This pre-computation takes O(mn) time. After this, we iterate through arr. For each number, we get its coordinates in O(1) from our map. We then mark it in a painted boolean grid and perform the same O(m+n) check on the corresponding row and column to see if they are full.
import java.util.HashMap;import java.util.Map; class Solution { public int firstCompleteIndex(int[] arr, int[][] mat) { int m = mat.length; int n = mat[0].length; Map<Integer, int[]> posMap = new HashMap<>(); for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { posMap.put(mat[r][c], new int[]{r, c}); } } boolean[][] painted = new boolean[m][n]; for (int i = 0; i < arr.length; i++) { int val = arr[i]; int[] pos = posMap.get(val); int r = pos[0]; int c = pos[1]; painted[r][c] = true; // Check row r boolean rowComplete = true; for (int col = 0; col < n; col++) { if (!painted[r][col]) { rowComplete = false; break; } } if (rowComplete) { return i; } // Check column c boolean colComplete = true; for (int row = 0; row < m; row++) { if (!painted[row][c]) { colComplete = false; break; } } if (colComplete) { return i; } } return -1; // Should not be reached }}Complexity
Time
O(m*n * (m+n)). Pre-computation takes O(m*n). The main loop runs up to `k` times (worst case `m*n`). Inside, checking the row and column takes O(m+n). Total time is O(m*n + k*(m+n)).
Space
O(m * n) for the `positions` map and the `painted` matrix.
Trade-offs
Pros
Faster than the pure brute-force approach.
Eliminates the expensive O(m*n) search from the main loop.
Cons
The check for a completed row or column is still inefficient.
Can still be too slow for constraints where one dimension is very large (e.g., m=10^5, n=1).
This is the most efficient approach. It optimizes both finding the number's location and checking for completion. Like the previous approach, it uses a data structure for O(1) position lookups. The key improvement is using two counter arrays, one for rows and one for columns. When a cell (r, c) is painted, we simply increment the counters for row r and column c. A row r is complete if its counter reaches n (the number of columns), and a column c is complete if its counter reaches m (the number of rows). This makes the check an O(1) operation.
Algorithm
- Create an array
positionsof sizem*n + 1to store the coordinates of each number. - Populate
positionsby iterating throughmat:positions[mat[r][c]] = {r, c}. - Initialize a row counter array
rowCountof sizemand a column counter arraycolCountof sizento all zeros. - Iterate through
arrwith indexi. - For each number
val = arr[i]:- Get coordinates
(r, c)frompositions[val]. - Increment
rowCount[r]andcolCount[c]. - Check if
rowCount[r] == norcolCount[c] == m. - If either condition is true, return
i.
- Get coordinates
Walkthrough
This optimal solution begins by pre-calculating the position of each number in the matrix and storing it in a positions array for O(1) lookup. Since the numbers are guaranteed to be in the range [1, m*n], an array is more efficient than a hash map. We also initialize two arrays, rowCount and colCount, to keep track of the number of painted cells in each row and column, respectively.
Then, we iterate through arr. For each number, we find its row r and column c using our positions array. We increment rowCount[r] and colCount[c]. After each increment, we check if rowCount[r] has reached n (the total number of columns) or if colCount[c] has reached m (the total number of rows). The first time this condition is met, we have found the first completely painted row or column, and we return the current index i.
class Solution { public int firstCompleteIndex(int[] arr, int[][] mat) { int m = mat.length; int n = mat[0].length; // Using an array for positions since values are 1 to m*n int[][] pos = new int[m * n + 1][2]; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { pos[mat[r][c]][0] = r; pos[mat[r][c]][1] = c; } } int[] rowCount = new int[m]; int[] colCount = new int[n]; for (int i = 0; i < arr.length; i++) { int val = arr[i]; int r = pos[val][0]; int c = pos[val][1]; rowCount[r]++; colCount[c]++; if (rowCount[r] == n || colCount[c] == m) { return i; } } return -1; // Should not be reached as a solution always exists }}Complexity
Time
O(m * n). The pre-computation step to build the `positions` map takes O(m*n). The main loop iterates through `arr` once (at most `m*n` times), and each step inside the loop is an O(1) operation. Therefore, the total time complexity is linear with respect to the number of cells in the matrix.
Space
O(m * n). We need O(m*n) space for the `positions` array, O(m) for `rowCount`, and O(n) for `colCount`. The dominant term is O(m*n).
Trade-offs
Pros
Highly efficient with linear time complexity.
All operations inside the main loop are O(1).
Passes all constraints comfortably.
Cons
Requires extra space for the position map and counter arrays, which is proportional to the size of the matrix.
Solutions
Solution
class Solution {public int firstCompleteIndex(int[] arr, int[][] mat) { int m = mat.length, n = mat[0].length; Map<Integer, int[]> idx = new HashMap<>(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { idx.put(mat[i][j], new int[]{i, j}); } } int[] row = new int[m]; int[] col = new int[n]; for (int k = 0;; ++k) { var x = idx.get(arr[k]); int i = x[0], j = x[1]; ++row[i]; ++col[j]; if (row[i] == n || col[j] == m) { return k; } } }}class Solution {public: int firstCompleteIndex(vector<int> &arr, vector<vector<int>> &mat) { int m = mat.size(), n = mat[0].size(); unordered_map<int, pair<int, int>> idx; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { idx[mat[i][j]] = {i, j}; } } vector<int> row(m), col(n); for (int k = 0;; ++k) { auto [i, j] = idx[arr[k]]; ++row[i]; ++col[j]; if (row[i] == n || col[j] == m) { return k; } } }};class Solution: def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int: m, n = len(mat), len(mat[0]) idx = {} for i in range(m): for j in range(n): idx[mat[i][j]] = (i, j) row = [0] * m col = [0] * n for k in range(len(arr)): i, j = idx[arr[k]] row[i] += 1 col[j] += 1 if row[i] == n or col[j] == m: return kVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.