# [238. Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/description/)

# 1. Tóm tắt đề bài

Cho một mảng $n$ số nguyên. Với mỗi phần tử trong mảng, ta cần tính tích của tất cả các phần tử trong mảng ngoại trừ phần tử đó.

##### Giới hạn

$1 \le n \le 20000$
$-10 \le nums[i] \le 10$

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(n)$**

Thông thường, để dễ nhất, ta sẽ muốn lấy tích tất cả các số trong mảng rồi chia cho từng phần tử.

Tuy nhiên, đề bài đã nêu rất rõ rằng ta không được sử dụng phép chia.


Vì vậy, với mỗi tích, ta sẽ cần phân tích ra để sao cho dễ tính toán nhất.

Một trong những kỹ thuật ta có thể áp dụng đó là mảng tiền tố-hậu tố, hay còn gọi cách khác là mảng cộng dồn. Ý tưởng cụ thể các bạn có thể xem trong hình.

# 3. Lời giải chi tiết

Ta khai báo 1 mảng tiền tố và tính toán tích của $n + 1$ tiền tố.

Ta khai báo 1 mảng hậu tố và tính toán tích của $n + 1$ hậu tố.

Với mỗi phần tử trong kết quả, ta lấy tích giữa hai phần tử cần tính ở cả mảng tiền tố và mảng hậu tố.

Cuối cùng trả về kết quả.

### Độ phức tạp thuật toán

Thời gian: $O(n)$

Bộ nhớ mở rộng: $O(n)$

Code mẫu: https://leetcode.com/problems/product-of-array-except-self/submissions/1203941161/

# 4. Gợi ý mở rộng

[152. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/description/)

[1473. Paint House III](https://leetcode.com/problems/paint-house-iii/description/)