‹ DS&A interview · Socratic
DSA · Arrays & Prefix Products · #140

Product of Array Except Self

Module 80 · difficulty 3/5·⏱ 30:00starts on first keystroke

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**. Implement `productExceptSelf(nums)` which returns the `answer` array.

Examples
  • nums = [1,2,3,4] → [24,12,8,6] — answer[0]=2*3*4=24, answer[1]=1*3*4=12, answer[2]=1*2*4=8, answer[3]=1*2*3=6.
  • nums = [-1,1,0,-3,3] → [0,0,9,0,0] — Only answer[2] is nonzero because every other position multiplies in the single 0.
  • nums = [2,3] → [3,2] — Each element is replaced by the other.
Constraints
  • · 2 <= nums.length <= 10^5
  • · -30 <= nums[i] <= 30
  • · The product of any prefix or suffix of nums fits in a 32-bit integer.
  • · Solve in O(n) time without using division.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.