First Completely Painted Row or Column

MEDIUM

Description

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.length
n = mat[i].length
arr.length == m * n
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
1 <= arr[i], mat[r][c] <= m * n
All the integers of arr are unique.
All the integers of mat are unique.

Approaches

Checkout 3 different approaches to solve First Completely Painted Row or Column. Click on different approaches to view the approach and algorithm in detail.

Brute Force Simulation

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.

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 Analysis

Time Complexity: 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 Complexity: O(m * n) to store the `painted` boolean matrix.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for First Completely Painted Row or Column. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for First Completely Painted Row or Column

Data Structures:

ArrayHash TableMatrix

Companies:

Citadel |