Product of Array Except Self: tại sao ràng buộc cấm chia là một món quà

Cách tiếp cận hiển nhiên ở đây là total_product / nums[i]. Tính tích của tất cả mọi thứ, rồi chia ra phần tử hiện tại. Đề bài cấm tường minh. Ràng buộc đó không phải tùy tiện — nó loại bỏ lối tắt và buộc bạn nghĩ về ý nghĩa thực sự của đáp án tại vị trí i.

Đáp án tại vị trí i là tích của tất cả thứ bên trái i nhân với tích của tất cả thứ bên phải. Không cần phép chia, không cần tổng tích. Hai tích riêng biệt, kết hợp tại mỗi chỉ số.

Trước khi bắt đầu, các constraint đáng đọc kỹ. 2 <= nums.length <= 10^5 nghĩa là luôn có ít nhất hai phần tử, mảng một phần tử không bao giờ xảy ra. Giá trị nằm trong khoảng -30 đến 30, nên các tích trung gian không bị overflow 32-bit integer. Với n lên đến 100,000, bất kỳ approach O(n²) nào cũng sẽ chạy khoảng 10^10 phép tính — TLE chắc chắn. Bạn cần O(n).

Brute force: O(n²)

Với mỗi vị trí i, duyệt qua toàn bộ vị trí j khác và nhân lại. Bỏ qua trường hợp j == i.

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = [0] * n
        for i in range(n):
            product = 1
            for j in range(n):
                if j != i:
                    product *= nums[j]
            result[i] = product
        return result

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = 0; j < n; j++) {
                if (j != i)
                    product *= nums[j];
            }
            result[i] = product;
        }
        return result;
    }
}

O(n²) thời gian, O(1) extra space. Với n = 10^5 đó là 10^10 phép nhân. Approach này cũng mang tinh thần của phép chia — mỗi vị trí tính lại toàn bộ tích từ đầu, lặp lại n - 1 phép nhân chồng chéo với mọi vị trí khác. Phân rã prefix × suffix chính là thứ ngăn chặn công việc lặp đó.

Thử với nums = [1, 2, 3, 4] tại vị trí i = 2: bạn nhân 1 × 2 × 4 = 8. Tại i = 1: bạn nhân 1 × 3 × 4 = 12. Cả hai đều tính 1 × 4 độc lập — đó chính là sự lãng phí. Mỗi chỉ số tính lại tích đầy đủ trừ một phần tử, nên công việc chồng chéo O(n) lần xuyên suốt mảng.

Cách phân tích prefix × suffix

Insight cốt lõi: answer[i] = (tích của tất cả phần tử bên trái i) × (tích của tất cả phần tử bên phải i). Không nửa nào bao gồm nums[i]. Bạn có thể tính cả hai nửa độc lập trong một lượt trái-sang-phải và một lượt phải-sang-trái. Không cần phép chia.

Với nums = [1, 2, 3, 4], đây là những gì mỗi mảng chứa và lý do tại sao:

tích trái (prefix):
  index 0: không có gì bên trái         -> 1   (phần tử đồng nhất, không phần tử nào)
  index 1: nums[0]                      -> 1
  index 2: nums[0] * nums[1]            -> 2
  index 3: nums[0] * nums[1] * nums[2]  -> 6
  prefix = [1, 1, 2, 6]

tích phải (suffix):
  index 3: không có gì bên phải         -> 1   (phần tử đồng nhất, không phần tử nào)
  index 2: nums[3]                      -> 4
  index 1: nums[3] * nums[2]            -> 12
  index 0: nums[3] * nums[2] * nums[1]  -> 24
  suffix = [24, 12, 4, 1]

answer[i] = prefix[i] * suffix[i]:
  [1*24, 1*12, 2*4, 6*1] = [24, 12, 8, 6]

Sơ đồ dưới đây cho thấy cách prefix và suffix chảy vào từng ô kết quả:

Hai lượt duyệt độc lập nhau. Xây prefix từ trái sang phải, suffix từ phải sang trái, nhân chúng lại. Ba lượt tuyến tính tổng cộng — vẫn là O(n).

Cài đặt với hai mảng: O(n) thời gian, O(n) space

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        prefix = [1] * n
        suffix = [1] * n
 
        for i in range(1, n):
            prefix[i] = prefix[i - 1] * nums[i - 1]
        for i in range(n - 2, -1, -1):
            suffix[i] = suffix[i + 1] * nums[i + 1]
 
        return [prefix[i] * suffix[i] for i in range(n)]

prefix[i] chứa tích tích lũy của mọi thứ trước chỉ số i. prefix[0] bằng 1 theo định nghĩa — không có gì bên trái phần tử đầu tiên. Logic tương tự cho suffix[n-1] = 1.

Trong C#:

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int n = nums.Length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
 
        prefix[0] = 1;
        for (int i = 1; i < n; i++)
            prefix[i] = prefix[i - 1] * nums[i - 1];
 
        suffix[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--)
            suffix[i] = suffix[i + 1] * nums[i + 1];
 
        int[] result = new int[n];
        for (int i = 0; i < n; i++)
            result[i] = prefix[i] * suffix[i];
 
        return result;
    }
}

Đây là version tôi sẽ giải thích đầu tiên trong phỏng vấn — logic minh bạch. Mỗi mảng có vai trò rõ ràng. Bước nhân cuối cùng là một dòng. O(n) thời gian, O(n) extra space (hai mảng phụ). Đây đáp ứng phần chính của bài. Follow-up yêu cầu giảm extra space xuống O(1).

Follow-up: O(1) extra space

Mảng output không tính vào space complexity theo đề bài. Vậy thì tái sử dụng nó.

Lượt đầu (trái sang phải): điền result với prefix products y hệt như trước.

Lượt hai (phải sang trái): thay vì mảng suffix riêng, dùng một biến right tích lũy tích đang chạy từ phải. Tại mỗi chỉ số, nhân result[i] — đang chứa prefix product — với right, rồi cập nhật right.

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = [1] * n
 
        # lượt đầu: result[i] = tích của mọi thứ bên trái i
        for i in range(1, n):
            result[i] = result[i - 1] * nums[i - 1]
 
        # lượt hai: nhân với tích của mọi thứ bên phải i
        right = 1
        for i in range(n - 1, -1, -1):
            result[i] *= right
            right *= nums[i]
 
        return result

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
 
        result[0] = 1;
        for (int i = 1; i < n; i++)
            result[i] = result[i - 1] * nums[i - 1];
 
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= right;
            right *= nums[i];
        }
 
        return result;
    }
}

Thứ tự trong vòng lặp thứ hai quan trọng: nhân trước (result[i] *= right), sau đó cập nhật (right *= nums[i]). Đảo hai dòng đó sẽ đưa nums[i] vào suffix product cho vị trí i, chính xác là thứ ta đang cố loại trừ.

Trace từng bước cho nums = [1, 2, 3, 4]:

Sau lượt đầu (prefix vào result):
  i=1: result[1] = result[0] * nums[0] = 1 * 1 = 1
  i=2: result[2] = result[1] * nums[1] = 1 * 2 = 2
  i=3: result[3] = result[2] * nums[2] = 2 * 3 = 6
  result = [1, 1, 2, 6]   <- đây là tích trái của mỗi vị trí

Lượt hai, right bắt đầu từ 1:
  i=3: result[3] = 6  * 1  = 6;   right = 1  * 4 = 4
  i=2: result[2] = 2  * 4  = 8;   right = 4  * 3 = 12
  i=1: result[1] = 1  * 12 = 12;  right = 12 * 2 = 24
  i=0: result[0] = 1  * 24 = 24;  right = 24 * 1 = 24

  result = [24, 12, 8, 6]  ✓

Tại mỗi bước, result[i] chứa (tích trái) × (tích phải) — tức là mọi thứ trừ nums[i]. Đây là version tôi sẽ ship lên production. Hai lượt duyệt, O(1) extra space, logic vẫn rõ ràng khi bạn hiểu mẹo một biến tích lũy.

Edge cases — những gì thực sự cần chú ý

Một số không trong mảng. nums = [1, 0, 3, 4]:

prefix = [1, 1, 0, 0]
suffix = [0, 12, 4, 1]
result = [0, 12, 0, 0]

Vị trí 1 (chính số không) nhận prefix[1] * suffix[1] = 1 * 12 = 12. Mọi vị trí khác thu được số không từ một trong hai mảng. Không cần rẽ nhánh — số không lan truyền qua tích tích lũy một cách tự nhiên. Không cần đếm số không hay thêm logic đặc biệt nào.

Hai hoặc nhiều số không. nums = [0, 0, 2, 3]:

prefix = [1, 0, 0, 0]
suffix = [0, 0, 6, 2]
result = [0, 0, 0, 0]

Toàn số không — đúng như kỳ vọng. Khi có hai phần tử bằng không thì với mọi vị trí, ít nhất một trong hai phía chứa số không và tích sụp đổ. Thuật toán cho ra đáp án đúng mà không cần logic đếm số không.

Số âm. nums = [-1, 1, 0, -3, 3], kết quả mong đợi [0, 0, 9, 0, 0]. Số không tại index 2 làm về không mọi vị trí trừ chính index 2, nơi nhận (-1) * 1 * (-3) * 3 = 9. Số âm không cần xử lý đặc biệt — prefix và suffix tích lũy chúng đúng, cả dấu lẫn giá trị. Đảm bảo overflow 32-bit trong constraint có nghĩa là bạn cũng không cần lo về độ lớn.

Mảng tối thiểu, hai phần tử. nums = [2, 3]: prefix = [1, 2], suffix = [3, 1], result = [3, 2]. Hoạt động đúng. Constraint n >= 2 nghĩa là đây là input nhỏ nhất có thể, không bao giờ có mảng một phần tử.

Không cái nào trong số này là trường hợp đặc biệt trong code. Thuật toán xử lý tất cả chỉ với hai lượt duyệt giống nhau.

So sánh các approach

Hai version O(n) chỉ khác nhau về space. Tôi sẽ dùng version hai mảng trong code review nơi readability quan trọng và trong phỏng vấn để giải thích ý tưởng rõ ràng, sau đó chuyển sang version tối ưu space như câu trả lời "follow-up". Chúng nhanh như nhau.

Nhận diện pattern và vị trí trong series

Đây là pattern two-pass prefix/suffix: tính toán trước một giá trị tích lũy từ trái, tính toán trước từ phải, kết hợp tại mỗi chỉ số. Đây là dạng tổng quát hóa của prefix sum — cùng cấu trúc, phép nhân thay vì phép cộng.

Bài này nằm sau two-sum và group-anagrams trong series arrays-hashing. Những bài đó xây dựng intuition xung quanh hash map và frequency bucketing. Bài này khác: nó không cần map chút nào. Ý tưởng two-pass prefix chính là thứ bài series này đóng góp.

Một vài từ khóa trong đề bài nên gợi ra cách phân tích này: "tích của tất cả phần tử trừ phần tử hiện tại," "ngoại trừ index i," "không được dùng phép chia." Bất kỳ khi nào bạn cần kết hợp thông tin từ cả hai phía của mỗi vị trí trong một mảng, two-pass prefix/suffix là lựa chọn đúng.

Các bài liên quan

• LeetCode 303 — Range Sum Query: prefix sum cho range query, anh em phép cộng của bài này.
• LeetCode 560 — Subarray Sum Equals K: prefix sum kết hợp hash map để tìm subarray — thêm một lớp frequency lên trên ý tưởng prefix.
• LeetCode 724 — Find Pivot Index: tính left sum và right sum tại mọi vị trí — cùng ý tưởng two-pass, bước kết hợp đơn giản hơn.
• LeetCode 1480 — Running Sum of 1d Array: bài khởi động prefix sum đơn giản nhất; chỉ làm một nửa của bài này (lượt trái mà thôi).

Quy tắc cấm chia là thứ buộc cách đặt vấn đề prefix × suffix. Không có nó, hầu hết mọi người dừng lại ở tổng tích / hiện tại. Với nó, bạn phải hỏi đáp án tại một chỉ số nhất định thực sự phụ thuộc vào gì. Nó phụ thuộc vào hai tích độc lập, một từ mỗi phía. Cách phân tích đó là toàn bộ bài toán — và khi bạn thấy nó ở đây, bạn sẽ nhận ra cùng hình dạng đó trong nhiều bài array khác.