Scale Engineer

First Completely Painted Row or Column

Med
#2418Time: 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.1 company
Data structures
ArrayHash TableMatrix
Companies
Citadel

Prompt

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:

image explanation for 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:

image explanation for 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.length
  • n = mat[i].length
  • arr.length == m * n
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • 1 <= arr[i], mat[r][c] <= m * n
  • All the integers of arr are unique.
  • All the integers of mat are 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 painted of the same dimensions as mat, initialized to false.
  • Iterate through the input array arr from index i = 0 to arr.length - 1.
  • For each number val = arr[i]:
    • Search the entire mat to find the row r and column c where mat[r][c] == val.
    • Mark the cell as painted by setting painted[r][c] = true.
    • Check if the entire row r is painted by iterating through its columns.
    • If the row is complete, return i.
    • Check if the entire column c is painted by iterating through its rows.
    • If the column is complete, return i.

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.

Solutions

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;      }    }  }}

Video 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.

← Previous

Previous problem

Next →

Next problem