Product of Array Except Self

82.1k
0

Given an integer array nums, return an array answer where answer[index] equals the product of every element in nums except nums[index].

The product must be calculated without using the value at the current index.

Return an empty array when nums is empty.

Example 1

Input: nums = [1, 2, 3, 4]

Output: [24, 12, 8, 6]

Explanation: For each index, we multiply all elements except the current element. For index 0, product is 2 × 3 × 4 = 24.

Example 2

Input: nums = [-1, 1, 0, -3, 3]

Output: [0, 0, 9, 0, 0]

Explanation: Only the index containing 0 gets the product of all non-zero elements. Other positions become 0 because their product includes 0.

Brute Force Approach

The most direct idea processes every index separately.

For each position, every other array element is multiplied while the current position is skipped. This follows the problem definition exactly, but the same values are multiplied repeatedly for different indices.

Algorithm

  • Store the array size in n. If n == 0, return an empty array because there is no index for which a product can be calculated.

  • Create an answer array of size n, where answer[index] will store the product of all elements except nums[index].

  • Treat every index excludedIndex as the position that must be excluded from the current product.

  • Initialize product with 1 for each excludedIndex, since 1 is the multiplicative identity and does not affect the product.

  • Traverse the complete array and multiply product by nums[currentIndex] only when currentIndex != excludedIndex. After all other elements have been processed, store the completed product in answer[excludedIndex].

  • Return answer after the product for every index has been calculated.

Dry Run

Product of Array Except Itself Brute Force Approach.png

Product of Array Except Itself Brute Force Approach.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<long long> productExceptSelf(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return {};
}
vector<long long> answer(n);
for (int excludedIndex = 0; excludedIndex < n; excludedIndex++) {
long long product = 1;
/*
* Multiply every element except
* the value at excludedIndex.
*/
for (int currentIndex = 0; currentIndex < n; currentIndex++) {
if (currentIndex != excludedIndex) {
product *= nums[currentIndex];
}
}
answer[excludedIndex] = product;
}
return answer;
}
};
int main() {
vector<int> nums = {1, 2, 3, 4};
Solution solution;
vector<long long> answer = solution.productExceptSelf(nums);
for (long long value : answer) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N²), where N represents the array size. Every index requires another complete traversal of the array.

Space Complexity: O(N) for the output array. No additional data structure is required apart from the returned result.

Better Approach

The product except the current element can be divided into two independent parts:

  • Product of all elements before the current index.

  • Product of all elements after the current index.

Storing both products in prefix and suffix arrays removes the need to multiply the complete array again for every position.

Algorithm

  • Store the array size in n. If the array is empty, return an empty array.

  • Create prefix, suffix, and answer arrays of size n. Here, prefix[index] stores the product of elements before index, while suffix[index] stores the product of elements after it.

  • Set prefix[0] = 1 because no element exists before the first index. Build the remaining values using prefix[index] = prefix[index - 1] × nums[index - 1].

  • Set suffix[n - 1] = 1 because no element exists after the last index. Traverse from right to left and build each value using suffix[index] = suffix[index + 1] × nums[index + 1].

  • For every index, multiply prefix[index] and suffix[index]. Their product contains every array element except the value at the current position.

  • Store the result in answer[index] and return the completed answer array.

Dry Run

Product of Array Except Itself Better Force Approach.png

Product of Array Except Itself Better Force Approach.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<long long> productExceptSelf(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return {};
}
vector<long long> prefix(n);
vector<long long> suffix(n);
vector<long long> answer(n);
// No element exists before index 0.
prefix[0] = 1;
for (int index = 1; index < n; index++) {
prefix[index] =
prefix[index - 1] * nums[index - 1];
}
// No element exists after the last index.
suffix[n - 1] = 1;
for (int index = n - 2; index >= 0; index--) {
suffix[index] =
suffix[index + 1] * nums[index + 1];
}
/*
* Combining both sides excludes
* the value at the current index.
*/
for (int index = 0; index < n; index++) {
answer[index] = prefix[index] * suffix[index];
}
return answer;
}
};
int main() {
vector<int> nums = {1, 2, 3, 4};
Solution solution;
vector<long long> answer = solution.productExceptSelf(nums);
for (long long value : answer) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the array size. Linear traversals build the prefix products, suffix products, and final result.

Space Complexity: O(N) auxiliary space for the prefix and suffix arrays. The returned answer array also requires O(N) space.

Optimal Approach

Separate prefix and suffix arrays are not both necessary.

The output array can first store the product of every element on the left. A running product from the right can then complete each result by multiplying the already stored left product with the product of all elements on the right.

Algorithm

  • Store the array size in n. If n == 0, return an empty array.

  • Create an answer array of size n and initialize leftProduct = 1. This variable stores the product of all elements appearing before the current index.

  • Traverse from left to right. Store leftProduct in answer[index] before multiplying it by nums[index], ensuring that the current value is excluded from its own result.

  • Initialize rightProduct = 1, where it represents the product of all elements appearing after the current index.

  • Traverse from right to left. Multiply answer[index] by rightProduct, then include nums[index] in rightProduct so it becomes available for the next position to the left.

  • Return answer after both traversals are complete.

Dry Run

Product of Array Except Itself Optimal Force Approach.png

Product of Array Except Itself Optimal Force Approach.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<long long> productExceptSelf(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return {};
}
vector<long long> answer(n);
long long leftProduct = 1;
/*
* Store the product of all elements
* appearing before each index.
*/
for (int index = 0; index < n; index++) {
answer[index] = leftProduct;
leftProduct *= nums[index];
}
long long rightProduct = 1;
/*
* Multiply the stored left product
* by the product of elements on the right.
*/
for (int index = n - 1; index >= 0; index--) {
answer[index] *= rightProduct;
rightProduct *= nums[index];
}
return answer;
}
};
int main() {
vector<int> nums = {1, 2, 3, 4};
Solution solution;
vector<long long> answer = solution.productExceptSelf(nums);
for (long long value : answer) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the array size. One traversal stores the left products, and another traversal includes the right products.

Space Complexity: O(1) auxiliary space when the returned answer array is excluded. Only leftProduct and rightProduct require additional storage.

FAQs

Q1. Why are the missing prefix and suffix products represented by 1?

1 is the multiplicative identity. Multiplying by 1 leaves the available product unchanged, making boundary indices work without special calculations.

Q2. How does the approach handle one zero in the array?

Every result except the zero position becomes 0. The zero position receives the product of all non-zero elements.

Q3. What happens when the array contains more than one zero?

Every result becomes 0 because excluding any single index still leaves at least one zero in the remaining product.

Q4. Why is division usually avoided for this problem?

Division requires separate handling for zero values and may be disallowed by the problem constraints. Prefix and suffix products handle zero naturally.

Q5. What is returned when the array contains one element?

The result is [1]. After excluding the only element, no values remain, and the product of an empty collection is treated as 1.

Q6. What should be considered when array values are large?

Intermediate products may exceed the standard integer range. A wider numeric type should be used when the constraints allow large products.

Arrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0