2685. First Completely Painted Row Or Column¶

LeetCode Problem View on GitHub

2685. First Completely Painted Row or Column

Medium

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.

Solution¶

class Solution {
    static class Pair {
        int row, col;
        public Pair(int row, int col) {
            this.row = row;
            this.col = col;
        }
        @Override
        public String toString() {
            return "(" + row + " " + col + ")";
        }
    }
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int n = arr.length;
        int row[] = new int[mat.length];
        int col[]= new int[mat[0].length];
        HashMap<Integer, Pair> map = new HashMap<>();
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) map.put(mat[i][j], new Pair(i, j));
        }
        for (int i = 0; i < n; i++) {
            if (map.containsKey(arr[i])) {
                row[map.get(arr[i]).row]++;
                col[map.get(arr[i]).col]++;
                if (row[map.get(arr[i]).row] == mat[0].length) return i;
                if (col[map.get(arr[i]).col] == mat.length) return i;
            }
        }
        return -1;
    }
}

Complexity Analysis¶

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

Approach¶

Detailed explanation of the approach will be added here