🎨Now live: Try our Free AI Image Generation Feature

Intuition
To solve the problem of finding the product of all elements except the current one without using division, we can leverage the concept of prefix and suffix products. By calculating the prefix product (product of all elements before the current one) and suffix product (product of all elements after the current one) for each element, we can derive the result efficiently.
Approach
- Initialization:
- Create two arrays:
prefix_products
andsuffix_products
. -prefix_products[i]
will store the product of all elements to the left ofnums[i]
. -suffix_products[i]
will store the product of all elements to the right ofnums[i]
. - Prefix Product Calculation:
- Initialize
prefix_products[0]
to 1 since there are no elements to the left of the first element. - Iterate through the array to fillprefix_products
such thatprefix_products[i]
is the product of all elements beforenums[i]
. - Suffix Product Calculation:
- Initialize
suffix_products[n-1]
to 1 since there are no elements to the right of the last element. - Iterate through the array in reverse to fillsuffix_products
such thatsuffix_products[i]
is the product of all elements afternums[i]
. - Result Construction:
- Create the
answer
array whereanswer[i] = prefix_products[i] * suffix_products[i]
.
This approach ensures that we traverse the array a constant number of times, resulting in an O(n) time complexity.
Complexity
- Time Complexity: - O(n) for calculating prefix products. - O(n) for calculating suffix products. - O(n) for constructing the result. - The overall time complexity is O(n).
- Space Complexity: - O(n) for storing prefix products. - O(n) for storing suffix products. - O(n) for the result array. - The overall space complexity is O(n).
By using this approach, we avoid the division operation and achieve the desired time complexity.
Code
C++
#include
#include
#include
using namespace std;
class Solution {
public:
vector productExceptSelf(vector& nums) {
unordered_map pre, suf;
int preSum = 1, sufSum = 1;
int n = nums.size();
pre[0] = 1;
suf[n - 1] = 1;
for (int i = 0; i < n; i++) {
preSum *= nums[i];
pre[i + 1] = preSum;
sufSum *= nums[n - 1 - i];
suf[n - 2 - i] = sufSum;
}
// Debug output (similar to console.log in JavaScript)
cout << "Pre: ";
for (auto p : pre) {
cout << "[" << p.first << ": " << p.second << "] ";}
cout << endl;
cout << "Suf: ";
for (auto s : suf) {
cout << "[" << s.first << ": " << s.second << "] ";
}
cout << endl;
vector answer(n);
for (int i = 0; i < n; i++) {
answer[i] = pre[i] * suf[i];
}
return answer;
}
};
Python
f = open("user.out", "w")
for i in stdin:
nums = list(map(int, i.rstrip()[1:-1].split(r",")))
l = nums[0]
r = nums[-1]
ans = [1] * len(nums)
for i in range(1, len(nums)):
ans[i] = l
l *= nums[i]
for i in range(len(nums) - 2, -1, -1):
ans[i] *= r
r *= nums[i]
print(str(ans).replace(" ", ""), file=f)
exit(0)
Java
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] pre = new int[n + 1];
int[] suf = new int[n + 1];
int[] answer = new int[n];
pre[0] = 1;
suf[n] = 1;
int preSum = 1;
int sufSum = 1;
for (int i = 0; i < n; i++) {
preSum *= nums[i];
pre[i + 1] = preSum;
sufSum *= nums[n - 1 - i];
suf[n - 1 - i] = sufSum;
}
for (int i = 0; i < n; i++) {
answer[i] = pre[i] * suf[i + 1];
}
return answer;
}
}
JavaScript
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function (nums) {
let pre = {};
let suf = {};
let preSum = 1;
let sufSum = 1;
pre[0] = 1;
suf[nums.length - 1] = 1;
for (let i = 0; i < nums.length; i++) {
preSum *= nums[i];
pre[i + 1] = preSum;
sufSum *= nums[nums.length - 1 - i];
suf[nums.length - 2 - i] = sufSum;
}
console.log(pre);
console.log(suf);
answer = []
for (let i = 0; i < nums.length; i++) {
answer[i] = pre[i] * suf[i];
}
return answer;
};