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! 🖌️

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

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à:

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

Approach

1. 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ô

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

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

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

Complexity Analysis

• Time: O(m * n) - duyệt qua ma trận để tạo map
• Space: O(m * n) - cho map lưu tọa độ và counters

Key Insights

1. Preprocessing is Key: Việc tạo map giúp ta truy cập vị trí nhanh chóng
2. Counter Magic: Dùng counters giúp ta không phải check toàn bộ hàng/cột
3. Early Return: Return ngay khi tìm thấy kết quả, không cần duyệt hết

Tips & Tricks

1. Vẽ hình để hình dung quá trình tô màu
2. Test với các edge cases như ma trận 1x1, ma trận dài/rộng không đều
3. Nhớ check empty matrix!

Chúc mọi người code vui! Hẹn gặp lại trong các bài Leetcode tiếp theo! 🚀

P/S: Follow mình tại Learning AI with Loser để cập nhật các bài giải Leetcode hàng ngày nhé! 💻✨

CODE EDITOR

#leetcode #leetcodedaily #algorithms #programming #learningwithlosers