238. Product of Array Except Self
mediumAsked at ElasticReturn an array where each element is the product of all other elements, without using division. Elastic uses this to test prefix/suffix scan thinking — the same cumulative-scan pattern drives Elasticsearch's pipeline aggregations that compute running totals across document sets.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Elastic loops.
- Glassdoor (2025-12)— Elastic SWE candidates report prefix-product and prefix-sum problems appearing as mid-round algorithm questions.
- Blind (2025-09)— Elastic interview threads list this problem as a reliable test of O(1) extra space thinking under the no-division constraint.
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.
Constraints
2 <= nums.length <= 10^5−30 <= nums[i] <= 30The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Examples
Example 1
nums = [1,2,3,4][24,12,8,6]Explanation: answer[0] = 2*3*4=24; answer[1] = 1*3*4=12; answer[2] = 1*2*4=8; answer[3] = 1*2*3=6.
Example 2
nums = [-1,1,0,-3,3][0,0,9,0,0]Explanation: Presence of zero makes most products zero.
Approaches
1. Two-pass prefix and suffix products
First pass: compute left prefix products into the output array. Second pass: multiply by right suffix products using a running variable — no extra array needed.
- Time
- O(n)
- Space
- O(1) excluding output
function productExceptSelf(nums) {
const n = nums.length;
const result = new Array(n).fill(1);
// Left pass: result[i] = product of all nums[j] for j < i
let prefix = 1;
for (let i = 0; i < n; i++) {
result[i] = prefix;
prefix *= nums[i];
}
// Right pass: multiply result[i] by product of all nums[j] for j > i
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
result[i] *= suffix;
suffix *= nums[i];
}
return result;
}Tradeoff: O(n) time, O(1) auxiliary space (the output array does not count). This is the optimal and expected solution.
Elastic-specific tips
Explicitly state the O(1) extra space constraint before coding: 'The output array doesn't count as extra space per the problem — so I need one extra variable for the right suffix.' Walk through the example step-by-step. Elastic interviewers appreciate knowing you understand WHY division is forbidden: presence of zeros would require special-casing. Connect to pipeline aggregations: 'This is how a running-total pipeline works — accumulate from left, then from right, and combine.'
Common mistakes
- Using division — fails when any element is zero and is explicitly prohibited.
- Allocating two separate O(n) arrays for left and right products instead of reusing the output array.
- Initializing prefix or suffix to 0 instead of 1 — the multiplicative identity is 1.
- Off-by-one in the left pass — result[i] should be the product of elements BEFORE i, not including i.
Follow-up questions
An interviewer at Elastic may pivot to one of these next:
- What if the constraint of no-division is lifted — how would you handle zeros?
- Sum of all elements except self — can you do this in O(1) space? (prefix + suffix sums, same pattern.)
- Maximum product subarray (LC 152) — uses a related running-max-and-min pattern.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does prefix start as 1 and not nums[0]?
result[0] should be the product of all elements to the LEFT of index 0, which is an empty product — equal to 1 (the multiplicative identity).
Why is the output array not counted as extra space?
The problem statement explicitly allows O(n) output space — the O(1) constraint refers to space used beyond what is needed for the output.