Product of Array Except Self
MedPrompt
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
3 approaches with complexity analysis and trade-offs.
For each index i, iterate through the array and calculate the product of all elements except nums[i].
Algorithm
- Initialize result array of same length as input array
- 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]
- Return result array
Walkthrough
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.
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;}Complexity
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)
Trade-offs
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
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.
Algorithm
- Create leftProducts and rightProducts arrays
- Fill leftProducts array from left to right
- leftProducts[i] contains product of all elements to the left of i
- Fill rightProducts array from right to left
- rightProducts[i] contains product of all elements to the right of i
- For each index i, multiply leftProducts[i] and rightProducts[i]
- Return result array
Walkthrough
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.
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;}Complexity
Time
O(n) where n is the length of the input array
Space
O(n) extra space for the left and right product arrays
Trade-offs
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
Use the output array to store the left products and calculate right products on the fly, reducing space complexity to O(1).
Algorithm
- Initialize result array
- Fill result array with left products
- result[i] contains product of all elements to the left of i
- Maintain running right product while iterating from right
- Multiply each result[i] with right product
- Update right product by multiplying with nums[i]
- Return result array
Walkthrough
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.
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;}Complexity
Time
O(n) where n is the length of the input array
Space
O(1) extra space (not counting the output array)
Trade-offs
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
Solutions
Solution
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; }}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 ; } }/** * @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; };class Solution {public: vector<int> productExceptSelf(vector<int> &nums) { int n = nums.size(); vector<int> 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; }};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 dpVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.