238. Product of Array Except Self
Tags:
Medium
Skills:
Array
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu: Với mỗi phần từ trong mảng nums, tính tích của tất cả các phần tử còn lại (trừ chính nó), nhưng không được dùng phép chia và phải đạt độ phức tạp TC: O(n)
Approach
Ta chỉ cần dùng một mảng kết quả (không cần mảng phụ cho prefix/suffix), tiết kiệm bộ nhớ.
Solution - Optimize
1function productExceptSelf(nums: number[]): number[] {
2 const n = nums.length;
3 const res: number[] = new Array(n);
4 let prefix = 1;
5
6 for (let i = 0; i < n; i++) {
7 res[i] = prefix;
8 prefix *= nums[i]
9 }
10
11 let suffix = 1;
12 for (let i = n - 1; i >= 0; i--) {
13 res[i] *= suffix;
14 suffix *= nums[i];
15 }
16
17 return res;
18};Solution - 2 Array
1function productExceptSelf(nums: number[]): number[] {
2 const n = nums.length;
3
4 let prefix: number[] = Array(n);
5 prefix[0] = 1
6
7 for (let i = 1; i < n; i++) {
8 prefix[i] = prefix[i - 1] * nums[i - 1];
9 }
10
11 let suffix: number[] = Array(n)
12 suffix[n - 1] = 1
13 for (let i = n - 2; i >= 0; i--) {
14 suffix[i] = suffix[i + 1] * nums[i + 1]
15 }
16
17 let res: number[] = Array(n)
18 for (let i = 0; i < n; i++) {
19 res[i] = prefix[i] * suffix[i]
20 }
21
22 return res;
23};