7. Product of Array Except Self · DSA Practice

Return an array answer where answer[i] is the product of every element of nums except nums[i]. Solve it in O(n) time without using division.

Example 1

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

Output: [60,40,30,24]

Example 2

Input: nums = [1,0,3]

Output: [0,3,0]

Constraints

2 ≤ nums.length ≤ 10⁵
Products fit in a 32-bit integer

Hint 1

answer[i] = (product of everything to the left) × (product of everything to the right).

Hint 2

Build the left products in one pass and multiply in the right products in a second pass.

ArrayPrefix Sum

Approach 1: Brute force

For each i, multiply all other elements.

⏱ Time O(n²)💾 Space O(1)

Approach 2: Prefix × suffix ✅

First pass stores left products in the answer; second pass multiplies a running right product.

⏱ Time O(n)💾 Space O(1) extra

Reference solution for Prefix × suffix (time O(n), space O(1) extra). Each solution passes every test in all four languages.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n
        left = 1
        for i in range(n):              # res[i] = product of everything left of i
            res[i] = left
            left *= nums[i]
        right = 1
        for i in range(n - 1, -1, -1):  # times the product of everything right of i
            res[i] *= right
            right *= nums[i]
        return res

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int left = 1;
        for (int i = 0; i < n; i++) { res[i] = left; left *= nums[i]; }       // prefix products
        int right = 1;
        for (int i = n - 1; i >= 0; i--) { res[i] *= right; right *= nums[i]; } // suffix products
        return res;
    }
}

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        int left = 1;
        for (int i = 0; i < n; i++) { res[i] = left; left *= nums[i]; }       // prefix products
        int right = 1;
        for (int i = n - 1; i >= 0; i--) { res[i] *= right; right *= nums[i]; } // suffix products
        return res;
    }
};

function productExceptSelf(nums) {
  const n = nums.length, res = new Array(n).fill(1);
  let left = 1;
  for (let i = 0; i < n; i++) { res[i] = left; left *= nums[i]; }        // prefix products
  let right = 1;
  for (let i = n - 1; i >= 0; i--) { res[i] *= right; right *= nums[i]; } // suffix products
  return res.map(v => v + 0); // normalise -0 to 0
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Arrays, Hashing & Prefix Sums.