Product of Array Except Self

# Product of Array Except Self ## Difficulty Medium ## Tags `array`, `prefix sum` ## Problem Statement 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]`. You must solve it **without using division** and in O(N) time complexity. ## Constraints - 2 ≤ nums.length ≤ 10⁵ - -30 ≤ nums[i] ≤ 30 - The product of any prefix or suffix of nums fits in a 32-bit integer. ## Signatures ### Python ```python def product_except_self(nums: List[int]) -> List[int]: pass ``` ### Java ```java public class Solution { public List<Integer> product_except_self(List<Integer> nums) { return null; } } ``` ### Csharp ```csharp public class Solution { public IList<int> product_except_self(IList<int> nums) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: vector<int> product_except_self(vector<int> nums) { } }; ``` ### C ```c int* product_except_self(int* nums) { } ``` ### Ruby ```ruby def product_except_self(nums) end ``` ### Perl ```perl sub product_except_self { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def product_except_self(nums: List[Int]): List[Int] = { } } ``` ### Haskell ```haskell product_except_self :: ... -> ... product_except_self args = undefined ``` ### Clojure ```clojure (defn product_except_self [nums] ) ``` ### Scheme ```scheme (define (product_except_self nums) ) ``` ## Examples ### Example 1 **Input:** ``` nums = [1, 2, 3, 4] ``` **Output:** ``` [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 **Input:** ``` nums = [-1, 1, 0, -3, 3] ``` **Output:** ``` [0, 0, 9, 0, 0] ``` **Explanation:** Any product that includes the 0 becomes 0. Only answer[2] excludes the 0. ### Example 3 **Input:** ``` nums = [2, 3] ``` **Output:** ``` [3, 2] ``` ## Hints 1. Think about prefix and suffix products. 2. `left_products[i]` = product of all elements to the left of index i. 3. `right_products[i]` = product of all elements to the right of index i. 4. `answer[i] = left_products[i] × right_products[i]` 5. Can you do this in O(1) extra space (excluding the output array)?