Product of Array Except Self

LeetCode 238 | Difficulty: Medium

Medium

Problem Description

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 <= 10^5`

- `-30 <= nums[i] <= 30`

- The input is generated such that `answer[i]` is **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.)

Topics: Array, Prefix Sum

---

Approach

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 324 ms)

Metric	Value
Runtime	324 ms
Memory	N/A
Date	2018-08-21

Solution

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int len = nums.Length;
    int[] output = new int[len];
    
    int left = 1;
    for (int i = 0; i < len; i++)
    {
        output[i] = left;
        left *= nums[i];
    }

    int right = 1;
    for (int i = len-1; i >= 0; i--)
    {
        output[i] *= right;
        right *= nums[i];
    }
    
    return output;
    }
}

---

Complexity Analysis

Approach	Time	Space
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Think how you can efficiently utilize prefix and suffix products to calculate the product of all elements except self for each index. Can you pre-compute the prefix and suffix products in linear time to avoid redundant calculations?

Hint 2: Can you minimize additional space usage by reusing memory or modifying the input array to store intermediate results?