# Product of Array Except Self **Difficulty:** MEDIUM [External](https://leetcode.com/problems/product-of-array-except-self) Canonical: https://scaleengineer.com/dsa/problems/product-of-array-except-self **Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum) **Data structures:** Array **Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Cisco](https://scaleengineer.com/companies/cisco), [Docusign](https://scaleengineer.com/companies/docusign), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Nutanix](https://scaleengineer.com/companies/nutanix), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [Tekion](https://scaleengineer.com/companies/tekion), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [Lyft](https://scaleengineer.com/companies/lyft), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Salesforce](https://scaleengineer.com/companies/salesforce), [Turing](https://scaleengineer.com/companies/turing), [Autodesk](https://scaleengineer.com/companies/autodesk), [Snap](https://scaleengineer.com/companies/snap), [CEDCOSS](https://scaleengineer.com/companies/cedcoss), [Disney](https://scaleengineer.com/companies/disney), [Warnermedia](https://scaleengineer.com/companies/warnermedia), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo), [Sigmoid](https://scaleengineer.com/companies/sigmoid), [Ripple](https://scaleengineer.com/companies/ripple), [Asana](https://scaleengineer.com/companies/asana), [Unity](https://scaleengineer.com/companies/unity), [ZS Associates](https://scaleengineer.com/companies/zs-associates) --- ## Problem 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 <= 105` * `-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.) # Approaches ## Brute Force Approach For each index i, iterate through the array and calculate the product of all elements except nums[i]. **Time:** O(n²) where n is the length of the input array as we use nested loops · **Space:** O(1) extra space (not counting the output array) **Pros:** Simple to understand and implement; No extra space required except output array **Cons:** Time complexity is quadratic; Not efficient for large arrays; Does not meet the required O(n) time complexity ### Explanation The brute force approach involves using nested loops. For each element at index i, we iterate through the array again to calculate the product of all elements except the current element. ```java public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] result = new int[n]; for (int i = 0; i < n; i++) { int product = 1; for (int j = 0; j < n; j++) { if (i != j) { product *= nums[j]; } } result[i] = product; } return result; } ``` ### Algorithm 1. Initialize result array of same length as input array 2. For each index i in the array: - Initialize product as 1 - Iterate through array again - Multiply all elements except nums[i] to product - Store product in result[i] 3. Return result array ## Left and Right Product Arrays Approach Use two additional arrays to store products of all elements to the left and right of each element, then multiply them to get the final result. **Time:** O(n) where n is the length of the input array · **Space:** O(n) extra space for the left and right product arrays **Pros:** Meets O(n) time complexity requirement; Easy to understand and implement; Handles zero values correctly **Cons:** Uses O(n) extra space; Requires three passes through the array; Does not meet the follow-up requirement of O(1) extra space ### Explanation This approach uses two additional arrays to store the products of all elements to the left and right of each index. Then multiply corresponding elements from left and right product arrays to get the final result. ```java public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] leftProducts = new int[n]; int[] rightProducts = new int[n]; int[] result = new int[n]; leftProducts[0] = 1; for (int i = 1; i < n; i++) { leftProducts[i] = leftProducts[i-1] * nums[i-1]; } rightProducts[n-1] = 1; for (int i = n-2; i >= 0; i--) { rightProducts[i] = rightProducts[i+1] * nums[i+1]; } for (int i = 0; i < n; i++) { result[i] = leftProducts[i] * rightProducts[i]; } return result; } ``` ### Algorithm 1. Create leftProducts and rightProducts arrays 2. Fill leftProducts array from left to right - leftProducts[i] contains product of all elements to the left of i 3. Fill rightProducts array from right to left - rightProducts[i] contains product of all elements to the right of i 4. For each index i, multiply leftProducts[i] and rightProducts[i] 5. Return result array ## Optimized Space Approach Use the output array to store the left products and calculate right products on the fly, reducing space complexity to O(1). **Time:** O(n) where n is the length of the input array · **Space:** O(1) extra space (not counting the output array) **Pros:** Optimal O(n) time complexity; Uses O(1) extra space; Only requires two passes through the array; Meets all requirements including follow-up **Cons:** Slightly more complex to understand; Modifies output array during computation ### Explanation This approach optimizes space usage by using only the output array. We first store left products in the output array, then multiply each element by the running right product. ```java public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] result = new int[n]; // Calculate left products result[0] = 1; for (int i = 1; i < n; i++) { result[i] = result[i-1] * nums[i-1]; } // Calculate right products and combine int rightProduct = 1; for (int i = n-1; i >= 0; i--) { result[i] = result[i] * rightProduct; rightProduct *= nums[i]; } return result; } ``` ### Algorithm 1. Initialize result array 2. Fill result array with left products - result[i] contains product of all elements to the left of i 3. Maintain running right product while iterating from right - Multiply each result[i] with right product - Update right product by multiplying with nums[i] 4. Return result array # Solutions ### CSharp ```csharp public class Solution { public int[] ProductExceptSelf(int[] nums) { int n = nums.Length; int[] ans = new int[n]; for (int i = 0, left = 1; i < n; ++i) { ans[i] = left; left *= nums[i]; } for (int i = n - 1, right = 1; i >= 0; --i) { ans[i] *= right; right *= nums[i]; } return ans; } } ``` ### Java ```java class Solution { public int [] productExceptSelf ( int [] nums ) { int n = nums . length ; int [] ans = new int [ n ]; for ( int i = 0 , left = 1 ; i < n ; ++ i ) { ans [ i ] = left ; left *= nums [ i ]; } for ( int i = n - 1 , right = 1 ; i >= 0 ; -- i ) { ans [ i ] *= right ; right *= nums [ i ]; } return ans ; } } ``` ### JavaScript ```javascript /** * @param {number[]} nums * @return {number[]} */ var productExceptSelf = function (nums) { const n = nums.length; const ans = new Array(n); for (let i = 0, left = 1; i < n; ++i) { ans[i] = left; left *= nums[i]; } for (let i = n - 1, right = 1; i >= 0; --i) { ans[i] *= right; right *= nums[i]; } return ans; }; ``` ### CPP ```cpp class Solution { public: vector productExceptSelf(vector &nums) { int n = nums.size(); vector ans(n); for (int i = 0, left = 1; i < n; ++i) { ans[i] = left; left *= nums[i]; } for (int i = n - 1, right = 1; ~i; --i) { ans[i] *= right; right *= nums[i]; } return ans; } }; ``` ### Python ```python class Solution : # 2 extra arrays def productExceptSelf ( self , nums ): if nums is None or len ( nums ) == 0 : return nums # Product from index=0 to index=i-1 from_left = [ 1 ] * len ( nums ) for i in range ( 1 , len ( nums )): from_left [ i ] = nums [ i - 1 ] * from_left [ i - 1 ] # Product from index=n-1 to current position from_right = [ 1 ] * len ( nums ) for i in range ( len ( nums ) - 2 , - 1 , - 1 ): from_right [ i ] = nums [ i + 1 ] * from_right [ i + 1 ] # Calculate result result = [ 0 ] * len ( nums ) for i in range ( len ( nums )): result [ i ] = from_left [ i ] * from_right [ i ] return result ############ class Solution : # follow up, no extra space def productExceptSelf ( self , nums : List [ int ]) -> List [ int ]: n = len ( nums ) ans = [ 0 ] * n left = right = 1 for i , v in enumerate ( nums ): ans [ i ] = left left *= v for i in range ( n - 1 , - 1 , - 1 ): ans [ i ] *= right right *= nums [ i ] return ans ############ class Solution ( object ): def productExceptSelf ( self , nums ): """ :type nums: List[int] :rtype: List[int] """ dp = [ 1 ] * len ( nums ) for i in range ( 1 , len ( nums )): dp [ i ] = dp [ i - 1 ] * nums [ i - 1 ] prod = 1 for i in reversed ( range ( 0 , len ( nums ))): dp [ i ] = dp [ i ] * prod prod *= nums [ i ] return dp ```