Dare2Solve
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.
Initialization:
prefix_products
and suffix_products
.prefix_products[i]
will store the product of all elements to the left of nums[i]
.suffix_products[i]
will store the product of all elements to the right of nums[i]
.Prefix Product Calculation:
prefix_products[0]
to 1 since there are no elements to the left of the first element.prefix_products
such that prefix_products[i]
is the product of all elements before nums[i]
.Suffix Product Calculation:
suffix_products[n-1]
to 1 since there are no elements to the right of the last element.suffix_products
such that suffix_products[i]
is the product of all elements after nums[i]
.Result Construction:
answer
array where answer[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.
Time Complexity:
Space Complexity:
By using this approach, we avoid the division operation and achieve the desired time complexity.
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
unordered_map<int, int> 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<int> answer(n);
for (int i = 0; i < n; i++) {
answer[i] = pre[i] * suf[i];
}
return answer;
}
};
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)
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;
}
}
/**
* @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;
};