Medium January 20, 2025 by Loser1

Table Of Contents

2661. First Completely Painted Row or Column
Problem Statement
First Thoughts & Intuition
Approach
Code Implementation
Complexity Analysis
Key Insights
Tips & Tricks

Xin chào mọi người! Mình là Loser1 từ Learning AI with Loser. Hôm nay chúng ta sẽ tạm nghỉ ngơi sau 2 bài Hard liên tiếp với một bài Medium nhẹ nhàng hơn nhé! Let’s paint it! 🖌️

Chào anh em, các ae có thể xem Đề bài và Solution của mình trên LeetCode nhé:

Đề bài: Xem tại đây
Solution: Xem tại đây

View Problem View Solution

James TW · When You Love Someone

2661. First Completely Painted Row or Column

Medium

Solved

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.

View Problem View Solution

Problem Statement

Cho một mảng arr và một ma trận mat. Mỗi phần tử trong arr sẽ "tô màu" một ô trong ma trận mat. Nhiệm vụ của chúng ta là tìm chỉ số đầu tiên trong arr mà tại đó, một hàng hoặc một cột trong ma trận được tô đầy đủ.

First Thoughts & Intuition

Khi mới nhìn vào bài này, mình cảm giác như đang chơi một game tô màu vậy! 🎮

Tưởng tượng bạn có:

Ma trận:      Mảng arr để tô:
1 4           [1, 3, 4, 2]
2 3

Quá trình tô màu sẽ diễn ra như sau:

Step 1: Tô số 1    Step 2: Tô số 3    Step 3: Tô số 4
🟦 ⬜️            🟦 ⬜️            🟦 🟦
⬜️ ⬜️            ⬜️ 🟦             ⬜️ 🟦
                                      (Hàng 1 đã tô xong!)

Điều quan trọng ta nhận ra là:

Mỗi số trong arr sẽ map tới một vị trí duy nhất trong ma trận
Ta cần theo dõi số ô đã tô trong mỗi hàng và mỗi cột
Khi một hàng hoặc cột được tô đủ → Game Over! 🎯

Approach

Bước tiền xử lý:

Tạo một map để lưu tọa độ (row, col) của mỗi số trong ma trận
Giống như việc có một "bản đồ" chỉ dẫn vị trí cần tô

Quá trình tô màu:

Duyệt qua từng số trong arr
Dùng map để biết vị trí cần tô
Cập nhật số ô đã tô trong hàng và cột tương ứng

Kiểm tra điều kiện:

Nếu một hàng đã tô đủ n ô → Return index hiện tại
Nếu một cột đã tô đủ m ô → Return index hiện tại

Code Implementation

C++

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();

        // Bước 1: Tạo map lưu tọa độ
        unordered_map<int, pair<int, int>> cordi;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                cordi[mat[i][j]] = {i, j};
            }
        }

        // Bước 2: Khởi tạo counters cho rows và cols
        unordered_map<int, int> row, col;

        // Bước 3: Bắt đầu tô màu!
        for (int i = 0; i < arr.size(); ++i) {
            auto [x, y] = cordi[arr[i]];

            // Cập nhật số ô đã tô
            row[x]++;
            col[y]++;

            // Kiểm tra điều kiện thắng
            if (row[x] == n || col[y] == m) {
                return i;
            }
        }

        return -1;  // Trường hợp không tìm thấy
    }
};