noodleProblems/
Product of Array Except Self
#128

Product of Array Except Self

AlgorithmmediumArrayPrefix Sum

Given an integer array nums, return an array answer such that answer[i] is the product of every element of nums **except** nums[i].

You must solve it **without using division** and in O(n) time. The product of any prefix or suffix of nums fits in a 32-bit integer.

Example cases

  • basic
    in nums = [1,2,3,4]
    out [24,12,8,6]
    answer[0] = 2·3·4 = 24, answer[1] = 1·3·4 = 12, and so on.
  • with a zero
    in nums = [-1,1,0,-3,3]
    out [0,0,9,0,0]
    Only the slot at the single zero gets a non-zero product.
  • two elements
    in nums = [2,3]
    out [3,2]
  • negatives
    in nums = [-2,-3,4]
    out [-12,-8,6]

Constraints

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix fits in a 32-bit integer.
  • Division is not allowed.
Saved
nums =
[1,2,3,4]