Product of Array Except Self

Bài toán

Cho một mảng số nguyên nums. Trả về một mảng answer sao cho answer[i] bằng tích của tất cả các phần tử trong nums ngoại trừ nums[i]. Bạn phải viết thuật toán chạy trong thời gian $O(n)$ và không được sử dụng phép chia.

Ví dụ:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Giải thích:
- Tại i=0: 2*3*4 = 24
- Tại i=1: 1*3*4 = 12
- ...

Phân Tích & Tiếp Cận

Cách 1: Dùng phép chia (Bị cấm)

Tính tổng tích toàn bộ mảng (totalProduct), sau đó res[i] = totalProduct / nums[i]. Cách này không hoạt động nếu mảng có số 0 (chia cho 0 -> crash hoặc infinity). Hơn nữa đề bài cấm dùng phép chia.

Cách 2: Prefix & Suffix (Tiền tố & Hậu tố)

Tích tại i thực chất là: (Tích các số bên trái i) * (Tích các số bên phải i).

Ta có thể tính trước hai mảng:

• prefix[i]: Tích từ đầu đến i-1.
• suffix[i]: Tích từ i+1 đến cuối.

Sau đó res[i] = prefix[i] * suffix[i]. prefix và suffix có thể tính trong $O(N)$.

Tối ưu không gian O(1)

Ta không cần lưu mảng prefix và suffix riêng biệt. Ta có thể tính trực tiếp vào mảng kết quả res.

1. Duyệt từ trái sang phải: Tính tích dồn (prefix) và lưu vào res. Lúc này res[i] chứa tích các số bên trái nó.
2. Duyệt từ phải sang trái: Duy trì một biến tích dồn (postfix/suffix) chạy, và nhân nó vào res[i].

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const res: number[] = new Array(n).fill(1);

    // Bước 1: Tính Prefix Product (Tích bên trái)
    let prefix = 1;
    for (let i = 0; i < n; i++) {
        res[i] = prefix; // res[i] giờ là tích các số [0...i-1]
        prefix *= nums[i]; // Cập nhật prefix cho vòng sau
    }

    // Bước 2: Tính Postfix Product (Tích bên phải) và nhân vào
    let postfix = 1;
    for (let i = n - 1; i >= 0; i--) {
        res[i] *= postfix; // Nhân với tích bên phải
        postfix *= nums[i]; // Cập nhật postfix cho vòng sau
    }

    return res;
}

Dry Run: nums = [1, 2, 3, 4]

1. Vòng 1 (Trái -> Phải):

   • i=0, res[0]=1, prefix=1
   • i=1, res[1]=1, prefix=1*1=1
   • i=2, res[2]=2, prefix=1*2=2
   • i=3, res[3]=6, prefix=2*3=6
   • res sau vòng 1: [1, 1, 2, 6] (Đây là tích các số bên trái của mỗi vị trí)

2. Vòng 2 (Phải -> Trái): postfix khởi tạo = 1.

   • i=3, res[3] = 6 * 1 = 6. postfix = 1*4 = 4.
   • i=2, res[2] = 2 * 4 = 8. postfix = 4*3 = 12.
   • i=1, res[1] = 1 * 12 = 12. postfix = 12*2 = 24.
   • i=0, res[0] = 1 * 24 = 24. postfix = 24*1 = 24.
   • Kết quả: [24, 12, 8, 6].

• Time Complexity: $O(N)$ - Hai vòng lặp tách biệt.
• Space Complexity: $O(1)$ - Không tính mảng kết quả res (theo quy ước LeetCode). Ta chỉ dùng vài biến tạm.

Pattern Nhận Diện

Kỹ thuật Prefix Sum / Prefix Product rất hữu ích khi bạn cần tính toán thông tin tích lũy của mảng (tổng, tích, XOR...) để truy xuất đoạn con nhanh chóng. Bài này là biến thể: thay vì đoạn con [i, j], ta cần đoạn [0, i-1] và [i+1, n].