Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Leetcode Logo

LeetCode Daily Challenge – Day 5: Find the Prefix Common Array!

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

2657. Find the Prefix Common Array of Two Arrays

Medium
Solved Topics Companies

You are given two 0-indexed integer permutations A and B of length n.

A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.

Return the prefix common array of A and B.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

Example 1:

Input: A = [1,3,2,4], B = [3,1,2,4]
Output: [0,2,3,4]
Explanation: 
At i = 0: no number is common, so C[0] = 0.
At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2:

Input: A = [2,3,1], B = [3,1,2]
Output: [0,1,3]
Explanation: 
At i = 0: no number is common, so C[0] = 0.
At i = 1: only 3 is common in A and B, so C[1] = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints:

  • 1 <= A.length == B.length == n <= 50
  • 1 <= A[i], B[i] <= n
  • It is guaranteed that A and B are both a permutation of n integers.

Intuition

Xin chào anh em dev thân mến! Hôm nay chúng ta sẽ "phá đảo" một bài toán cực kỳ thú vị về xử lý mảng - Finding the Prefix Common Array. Khi nhìn vào bài này, mình nghĩ ngay đến việc sử dụng frequency array để track các phần tử chung giữa hai mảng. Đây là một approach khá elegant và hiệu quả! 🤓

Approach

Mình xin chia sẻ cách tiếp cận chi tiết:

1. Phân Tích Bài Toán

C++
Ví dụ minh họa:
A = [1, 3, 2, 4]
B = [3, 1, 2, 4]

Cần tìm số phần tử chung tại mỗi index:
- Index 0: A[0]=1, B[0]=3 -> 0 phần tử chung
- Index 1: thêm A[1]=3, B[1]=1 -> 2 phần tử chung (13)
- Index 2: thêm A[2]=B[2]=2 -> 3 phần tử chung
- Index 3: thêm A[3]=B[3]=4 -> 4 phần tử chung

2. Chiến Lược Giải Quyết

  1. Khởi tạo cấu trúc dữ liệu:
  • Mảng freq để đếm tần suất xuất hiện
  • Mảng prefix để lưu kết quả
  • Biến cnt đếm số phần tử chung
  1. Xử lý từng cặp phần tử:
  • Với mỗi index i, xét A[i] và B[i]
  • Nếu freq[x] = 2, nghĩa là x xuất hiện ở cả 2 mảng
  • Cập nhật cnt và prefix[i]
  1. Tối ưu hóa:
  • Chỉ cần duyệt một lần qua mảng
  • Không cần sort hay xử lý phức tạp

Complexity

Time complexity: $O(n)$- một lần duyệt qua mảng

Space complexity: $O(k)$ - k là range của các giá trị trong mảng

Code

C++
class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();
        // Khởi tạo mảng đếm tần suất
        vector<int> freq(n + 1, 0);
        vector<int> prefix(n, 0);
        int cnt = 0;

        // Duyệt qua từng index
        for (int i = 0; i < n; i++) {
            // Xử lý phần tử từ mảng A
            if (++freq[A[i]] == 2) cnt++;

            // Xử lý phần tử từ mảng B
            if (++freq[B[i]] == 2) cnt++;

            // Cập nhật kết quả
            prefix[i] = cnt;
        }

        return prefix;
    }
};

Test Cases Chi Tiết

C++
// Hàm in mảng helper
void printArray(const vector<int>& arr) {
    cout << "[";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i];
        if (i < arr.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {
    Solution sol;

    // Test Case 1
    cout << "\n🔍 Test Case 1:" << endl;
    vector<int> A1 = {1, 3, 2, 4};
    vector<int> B1 = {3, 1, 2, 4};
    cout << "Input:" << endl;
    cout << "A = "; printArray(A1);
    cout << "B = "; printArray(B1);
    cout << "Output: "; 
    printArray(sol.findThePrefixCommonArray(A1, B1));
    cout << "Expected: [0, 2, 3, 4]" << endl;

    // Test Case 2
    cout << "\n🔍 Test Case 2:" << endl;
    vector<int> A2 = {1, 2, 3};
    vector<int> B2 = {3, 2, 1};
    cout << "Input:" << endl;
    cout << "A = "; printArray(A2);
    cout << "B = "; printArray(B2);
    cout << "Output: ";
    printArray(sol.findThePrefixCommonArray(A2, B2));
    cout << "Expected: [0, 1, 3]" << endl;

    // Test Case 3: Edge case - một phần tử
    cout << "\n🔍 Test Case 3:" << endl;
    vector<int> A3 = {1};
    vector<int> B3 = {1};
    cout << "Input:" << endl;
    cout << "A = "; printArray(A3);
    cout << "B = "; printArray(B3);
    cout << "Output: ";
    printArray(sol.findThePrefixCommonArray(A3, B3));
    cout << "Expected: [1]" << endl;

    // Test Case 4: Các số trùng nhau hoàn toàn
    cout << "\n🔍 Test Case 4:" << endl;
    vector<int> A4 = {1, 1, 1};
    vector<int> B4 = {1, 1, 1};
    cout << "Input:" << endl;
    cout << "A = "; printArray(A4);
    cout << "B = "; printArray(B4);
    cout << "Output: ";
    printArray(sol.findThePrefixCommonArray(A4, B4));
    cout << "Expected: [1, 2, 3]" << endl;

    return 0;
}

Tips & Tricks

  1. Với bài toán về prefix và đếm tần suất, frequency array thường là approach tốt
  2. Không cần dùng hashmap khi range của giá trị nhỏ
  3. Tracking realtime tốt hơn là xử lý sau

P/S: Đây là một bài trong series LeetCode Daily Challenge của mình. Anh em có thể check profile để xem các bài trước. Happy coding! 💻✨

Lại code Editor vô chi cho ae đây ......

quyminhhuy0@gmail.com
quyminhhuy0@gmail.com
Articles: 39

Newsletter Updates

Enter your email address below and subscribe to our newsletter

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments
AI Assistant
Hi! How can I help you today?
Choose logi transports for your heavy equipment transport needs in new york, ny.