2661. First Completely Painted Row or Column LeetCode Solution

In this guide, you will get 2661. First Completely Painted Row or Column LeetCode Solution with the best time and space complexity. The solution to First Completely Painted Row or Column problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. First Completely Painted Row or Column solution in C++
  4. First Completely Painted Row or Column solution in Java
  5. First Completely Painted Row or Column solution in Python
  6. Additional Resources
2661. First Completely Painted Row or Column LeetCode Solution image

Problem Statement of First Completely Painted Row or Column

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

See also  2375. Construct Smallest Number From DI String LeetCode Solution

Complexity Analysis

  • Time Complexity: O(mn)
  • Space Complexity: O(mn)

2661. First Completely Painted Row or Column LeetCode Solution in C++

class Solution {
 public:
  int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
    const int m = mat.size();
    const int n = mat[0].size();
    // rows[i] := the number of painted grid in the i-th row
    vector<int> rows(m);
    // cols[j] := the number of painted grid in the j-th column
    vector<int> cols(n);
    // numToRow[num] := the i-th row of `num` in `mat`
    vector<int> numToRow(m * n + 1);
    // numToCol[num] := the j-th column of `num` in `mat`
    vector<int> numToCol(m * n + 1);

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        numToRow[mat[i][j]] = i;
        numToCol[mat[i][j]] = j;
      }

    for (int i = 0; i < arr.size(); ++i) {
      if (++rows[numToRow[arr[i]]] == n)
        return i;
      if (++cols[numToCol[arr[i]]] == m)
        return i;
    }

    throw;
  }
};
/* code provided by PROGIEZ */

2661. First Completely Painted Row or Column LeetCode Solution in Java

class Solution {
  public int firstCompleteIndex(int[] arr, int[][] mat) {
    final int m = mat.length;
    final int n = mat[0].length;
    // rows[i] := the number of painted grid in the i-th row
    int[] rows = new int[m];
    // cols[j] := the number of painted grid in the j-th column
    int[] cols = new int[n];
    // numToRow[num] := the i-th row of `num` in `mat`
    int[] numToRow = new int[m * n + 1];
    // numToCol[num] := the j-th column of `num` in `mat`
    int[] numToCol = new int[m * n + 1];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        numToRow[mat[i][j]] = i;
        numToCol[mat[i][j]] = j;
      }

    for (int i = 0; i < arr.length; ++i) {
      if (++rows[numToRow[arr[i]]] == n)
        return i;
      if (++cols[numToCol[arr[i]]] == m)
        return i;
    }

    throw new IllegalArgumentException();
  }
}
// code provided by PROGIEZ

2661. First Completely Painted Row or Column LeetCode Solution in Python

class Solution:
  def firstCompleteIndex(self, arr: list[int], mat: list[list[int]]) -> int:
    m = len(mat)
    n = len(mat[0])
    # rows[i] := the number of painted grid in the i-th row
    rows = [0] * m
    # cols[j] := the number of painted grid in the j-th column
    cols = [0] * n
    # numToRow[num] := the i-th row of `num` in `mat`
    numToRow = [0] * (m * n + 1)
    # numToCol[num] := the j-th column of `num` in `mat`
    numToCol = [0] * (m * n + 1)

    for i, row in enumerate(mat):
      for j, num in enumerate(row):
        numToRow[num] = i
        numToCol[num] = j

    for i, a in enumerate(arr):
      rows[numToRow[a]] += 1
      if rows[numToRow[a]] == n:
        return i
      cols[numToCol[a]] += 1
      if cols[numToCol[a]] == m:
        return i
# code by PROGIEZ

Additional Resources

See also  371. Sum of Two Integers LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.