Product of Array Except Self solution and explanation
TCS
Infosys
9 more videos on this problem
Product of Array Except Self - Leetcode 238 - PythonNeetCode · 11:54 · 1M views
Product of Array Except Self | Brute to Optimal Solution | Leetcode 238Apna College · 29:30 · 340K views
LeetCode 238. Product of Array Except Self (Solution Explained)Nick White · 14:49 · 117K views
Product of Array Except Self (LeetCode 238) | Full solution with visuals | Study AlgorithmsNikhil Lohia · 14:03 · 108K views
Product of array except self | Leetcode #238Techdose · 15:00 · 101K views
Product of Array Except Self - Leetcode 238 - Arrays & Strings (Python)Greg Hogg · 7:58 · 54K views
Product of Array Except Self - LeetCode 238 PythonDeepti Talesra · 12:07 · 16K views
Product of Array Except Self | Leetcode 238 | Top 150 interview question seriesTechnosage · 9:40 · 12K views
Product Of Array Except Self - LeetCode 238 - JavaScriptAlgoJS · 5:51 · 8K views
LeetCode 238. Product of Array Except Self [Coding Interview Solution Explained]Shiran Afergan · 8:27 · 5K views
The problem
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4] Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105-30 <= nums[i] <= 30- The product of any prefix or suffix of
numsis guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
Approach overview
Problem Overview: You are given an integer array nums. For each index i, compute the product of every element in the array except nums[i]. The catch: you cannot use division and the solution must run in linear time.
Approach 1: Prefix and Suffix Product Arrays (O(n) time, O(n) space)
This approach builds two helper arrays. The prefix array stores the product of all elements to the left of each index, while the suffix array stores the product of elements to the right. Iterate from left to right to fill prefix values, then iterate from right to left to compute suffix values. The result for each index is simply prefix[i] * suffix[i]. This works because the prefix holds the product before the index and the suffix holds the product after it.
The technique resembles patterns used in prefix sum problems, but instead of cumulative sums you maintain cumulative products. Time complexity is O(n) since the array is traversed a constant number of times, and space complexity is O(n) due to the two auxiliary arrays. This version is easy to reason about and useful when first learning the pattern.
Approach 2: Single Array as Transformation (O(n) time, O(1) extra space)
This optimized solution removes the need for a separate suffix array. First, build prefix products directly inside the output array. Initialize result[0] = 1, then iterate forward so each position stores the product of all elements before it. Next, iterate from right to left while maintaining a running suffix product variable. Multiply the stored prefix value with the current suffix product and update the suffix as you go.
The key insight: the output array already contains the prefix product, so you only need a single variable to track the suffix product during the backward pass. This reduces auxiliary space while still performing two linear scans. Time complexity remains O(n), while extra space becomes O(1) (excluding the output array). The technique is common in array transformation problems where intermediate results can be reused.
Recommended for interviews: Interviewers usually expect the single-array prefix + running suffix solution. Showing the prefix/suffix array idea first demonstrates understanding of the decomposition, but the optimized version proves you can reduce memory usage while maintaining linear time. That combination signals strong problem-solving skills in array and cumulative computation patterns.
Approach 1: Prefix and Suffix Product Arrays
This approach involves calculating two additional arrays:
- Prefix Products: This array stores the product of all the elements to the left of each element in the original array.
- Suffix Products: This array stores the product of all the elements to the right of each element.
By multiplying the corresponding prefix and suffix product, we obtain the product of all other elements except the one at that given index.
from typing import List
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
left = [1] * n
right = [1] * n
answer = [0] * n
for i in range(1, n):
left[i] = nums[i-1] * left[i-1]
for i in range(n-2, -1, -1):
right[i] = nums[i+1] * right[i+1]
for i in range(n):
answer[i] = left[i] * right[i]
return answerclass Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
int[] answer = new int[n];
left[0] = 1;
right[n-1] = 1;
for (int i = 1; i < n; i++)
left[i] = nums[i-1] * left[i-1];
for (int i = n-2; i >= 0; i--)
right[i] = nums[i+1] * right[i+1];
for (int i = 0; i < n; i++)
answer[i] = left[i] * right[i];
return answer;
}
}#include<vector>
using namespace std;
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> left(n, 1);
vector<int> right(n, 1);
vector<int> answer(n);
for (int i = 1; i < n; i++)
left[i] = nums[i-1] * left[i-1];
for (int i = n-2; i >= 0; i--)
right[i] = nums[i+1] * right[i+1];
for (int i = 0; i < n; i++)
answer[i] = left[i] * right[i];
return answer;
}var productExceptSelf = function(nums) {
let n = nums.length;
let left = Array(n).fill(1);
let right = Array(n).fill(1);
let answer = Array(n);
for (let i = 1; i < n; i++)
left[i] = nums[i - 1] * left[i - 1];
for (let i = n - 2; i >= 0; i--)
right[i] = nums[i + 1] * right[i + 1];
for (let i = 0; i < n; i++)
answer[i] = left[i] * right[i];
return answer;
};#include<stdio.h>
void productExceptSelf(int* nums, int numsSize, int* returnSize) {
int left[numsSize], right[numsSize], answer[numsSize];
left[0] = 1;
right[numsSize-1] = 1;
for (int i = 1; i < numsSize; i++)
left[i] = nums[i-1] * left[i-1];
for (int i = numsSize-2; i >= 0; i--)
right[i] = nums[i+1] * right[i+1];
for (int i = 0; i < numsSize; i++)
answer[i] = left[i] * right[i];
*returnSize = numsSize;
for (int i = 0; i < numsSize; i++)
printf("%d ", answer[i]);
printf("\n");
}public class Solution {
public int[] ProductExceptSelf(int[] nums) {
int n = nums.Length;
int[] left = new int[n];
int[] right = new int[n];
int[] answer = new int[n];
left[0] = 1;
right[n-1] = 1;
for (int i = 1; i < n; i++)
left[i] = nums[i-1] * left[i-1];
for (int i = n-2; i >= 0; i--)
right[i] = nums[i+1] * right[i+1];
for (int i = 0; i < n; i++)
answer[i] = left[i] * right[i];
return answer;
}
}In Python, lists 'left' and 'right' are utilized to store prefix and suffix products. Then, by performing a simple calculation for each index, the final array is derived.
Time Complexity: O(n) since it iterates through the list three times.
Space Complexity: O(n) due to the storage of prefixes and suffixes.
Approach 2: Single Array as Transformation
This approach optimizes space usage by performing the transformations directly on the output array. It first fills the output array with the left product transformation, then updates it with right products.
With the first pass, it calculates the products of elements to the left, and on the second pass, it adjusts for the products of elements to the right by maintaining a right product multiplier.
from typing import List
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
answer = [1] * n
for i in range(1, n):
answer[i] = nums[i - 1] * answer[i - 1]
right = 1
for i in range(n - 1, -1, -1):
answer[i] *= right
right *= nums[i]
return answerclass Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
answer[0] = 1;
for (int i = 1; i < n; i++)
answer[i] = answer[i - 1] * nums[i - 1];
int right = 1;
for (int i = n - 1; i >= 0; i--) {
answer[i] *= right;
right *= nums[i];
}
return answer;
}
}#include<vector>
using namespace std;
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> answer(n, 1);
int right = 1;
for (int i = 1; i < n; i++)
answer[i] = answer[i - 1] * nums[i - 1];
for (int i = n-1; i >= 0; i--) {
answer[i] *= right;
right *= nums[i];
}
return answer;
}var productExceptSelf = function(nums) {
let n = nums.length;
let answer = Array(n).fill(1);
for (let i = 1; i < n; i++)
answer[i] = answer[i - 1] * nums[i - 1];
let right = 1;
for (let i = n - 1; i >= 0; i--) {
answer[i] *= right;
right *= nums[i];
}
return answer;
};#include<stdio.h>
void productExceptSelf(int* nums, int numsSize, int* returnSize) {
int right = 1;
int answer[numsSize];
answer[0] = 1;
for (int i = 1; i < numsSize; i++)
answer[i] = nums[i - 1] * answer[i - 1];
for (int i = numsSize - 1; i >= 0; i--) {
answer[i] = answer[i] * right;
right *= nums[i];
}
*returnSize = numsSize;
for (int i = 0; i < numsSize; i++)
printf("%d ", answer[i]);
printf("\n");
}public class Solution {
public int[] ProductExceptSelf(int[] nums) {
int n = nums.Length;
int[] answer = new int[n];
answer[0] = 1;
for (int i = 1; i < n; i++)
answer[i] = answer[i - 1] * nums[i - 1];
int right = 1;
for (int i = n - 1; i >= 0; i--) {
answer[i] *= right;
right *= nums[i];
}
return answer;
}
}In this Python code, a single-pass modification prepares the left product, whereas another pass enhances it with the right product values.
Time Complexity: O(n) for separate left and right transformations.
Space Complexity: O(1), discounting the answer array.
Approach 3: Two Passes
We define two variables left and right to represent the product of all elements to the left and right of the current element, respectively. Initially, left = 1 and right = 1. We define an answer array ans of length n.
First, we traverse the array from left to right. For the i-th element, we update ans[i] with left, then multiply left by nums[i].
Next, we traverse the array from right to left. For the i-th element, we update ans[i] to ans[i] times right, then multiply right by nums[i].
After the traversal, we return the answer array ans.
The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).
function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const ans: number[] = new Array(n);
for (let i = 0, left = 1; i < n; ++i) {
ans[i] = left;
left *= nums[i];
}
for (let i = n - 1, right = 1; i >= 0; --i) {
ans[i] *= right;
right *= nums[i];
}
return ans;
}func productExceptSelf(nums []int) []int {
n := len(nums)
ans := make([]int, n)
left, right := 1, 1
for i, x := range nums {
ans[i] = left
left *= x
}
for i := n - 1; i >= 0; i-- {
ans[i] *= right
right *= nums[i]
}
return ans
}impl Solution {
pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut ans = vec![1; n];
for i in 1..n {
ans[i] = ans[i - 1] * nums[i - 1];
}
let mut r = 1;
for i in (0..n).rev() {
ans[i] *= r;
r *= nums[i];
}
ans
}
}class Solution {
/**
* @param Integer[] $nums
* @return Integer[]
*/
function productExceptSelf($nums) {
$n = count($nums);
$ans = [];
for ($i = 0, $left = 1; $i < $n; ++$i) {
$ans[$i] = $left;
$left *= $nums[$i];
}
for ($i = $n - 1, $right = 1; $i >= 0; --$i) {
$ans[$i] *= $right;
$right *= $nums[$i];
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix and Suffix Product Arrays | Time Complexity: O(n) since it iterates through the list three times. |
| Single Array as Transformation | Time Complexity: O(n) for separate left and right transformations. |
| Two Passes | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix and Suffix Product Arrays | O(n) | O(n) | When learning the pattern or when clarity matters more than memory usage |
| Single Array Transformation (Prefix + Running Suffix) | O(n) | O(1) extra space | Preferred interview solution and optimal for memory‑constrained scenarios |
Frequently asked questions
Is Product of Array Except Self easy or hard?
Product of Array Except Self is classified as a Medium problem on LeetCode. The challenge comes from computing products without division while maintaining linear time and constant extra space.
Product of Array Except Self Python/Java solution
In Python or Java, the common implementation builds prefix products in the result array and then multiplies by a running suffix product from the right side. Both implementations run in O(n) time and O(1) extra space beyond the output array.
How to solve Product of Array Except Self in O(n)?
Compute prefix products for every index in a forward pass, storing them in the output array. Then traverse the array backward while maintaining a running suffix product and multiply it with the stored prefix value. This produces the final result in O(n) time without using division.
What is the best approach for Product of Array Except Self?
The optimal approach uses prefix products stored in the result array and a running suffix product during a backward pass. This computes each element's product without division in O(n) time and O(1) extra space. It avoids auxiliary arrays while still scanning the array only twice.
Is Product of Array Except Self asked at Google/Amazon/Meta?
Product of Array Except Self is a well-known interview question frequently reported in coding interviews at companies like Amazon, Google, Meta, and Microsoft. It tests understanding of prefix computations, array manipulation, and space optimization techniques.
What data structure is used in Product of Array Except Self?
The problem primarily uses arrays along with cumulative prefix and suffix products. The optimized approach stores prefix results directly in the output array and tracks the suffix product using a single variable during a reverse traversal.
What is the time complexity of Product of Array Except Self?
The optimal solution runs in O(n) time because it performs two linear passes through the array: one to compute prefix products and another to apply suffix products. Each element is processed a constant number of times.