TIC
The Interns Company

Product of Array Except Self

MediumAcceptance: 64.2%
ArrayPrefix 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]. 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.

Constraints:

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Input Format:

  • An integer array nums

Output Format:

  • An array answer where answer[i] is equal to the product of all the elements of nums except nums[i]

Examples:

Example 1:

Input:

nums = [1,2,3,4]

Output:

[24,12,8,6]

Explanation:

[24,12,8,6] means: - 24 is the product of all array elements except 1 - 12 is the product of all array elements except 2 - 8 is the product of all array elements except 3 - 6 is the product of all array elements except 4

Example 2:

Input:

nums = [-1,1,0,-3,3]

Output:

[0,0,-9,0,0]

Explanation:

With a zero in the array, most of the output elements become 0 except for the element corresponding to the zero, which becomes the product of all other elements.

Solutions

Left and Right Product Arrays

Time: O(n)
Space: O(n)

Create two arrays to represent the product of all elements to the left and the product of all elements to the right of each element. Then multiply these two products to get the answer for each position.

Optimized Space Approach

Time: O(n)
Space: O(1) (excluding the output array)

Optimize space by using the output array to store the left products, and then compute the right products on-the-fly while building the result.

Algorithm Walkthrough

Example input: nums = [1,2,3,4]

Step-by-step execution:

  1. Initialize result array: [?, ?, ?, ?]
  2. Calculate left products:
  3. leftProducts[0] = 1 (no elements to the left)
  4. leftProducts[1] = 1 * 1 = 1
  5. leftProducts[2] = 1 * 2 = 2
  6. leftProducts[3] = 2 * 3 = 6
  7. Calculate right products:
  8. rightProducts[3] = 1 (no elements to the right)
  9. rightProducts[2] = 1 * 4 = 4
  10. rightProducts[1] = 4 * 3 = 12
  11. rightProducts[0] = 12 * 2 = 24
  12. Calculate final result:
  13. result[0] = leftProducts[0] * rightProducts[0] = 1 * 24 = 24
  14. result[1] = leftProducts[1] * rightProducts[1] = 1 * 12 = 12
  15. result[2] = leftProducts[2] * rightProducts[2] = 2 * 4 = 8
  16. result[3] = leftProducts[3] * rightProducts[3] = 6 * 1 = 6
  17. Final result: [24, 12, 8, 6]

Hints

Hint 1
Could you solve the problem without using division?
Hint 2
Think about using two passes: one from left to right and another from right to left.
Hint 3
For each position, consider calculating the product of all elements to the left and the product of all elements to the right.

Video Tutorial

Product of Array Except Self - Prefix and Suffix Products

YouTube•Learn the Product of Array Except Self solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize how the left and right product arrays are built and combined to create the final output.

Key visualization elements:

  • left product calculation
  • right product calculation
  • final multiplication

Similar Questions

Maximum Product Subarray

Medium

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer. A subarray is a contiguous subsequence of the array.

Asked By

AmazonGoogleFacebookMicrosoftAppleLinkedInUber

Implementation Notes

This problem tests the ability to manipulate arrays efficiently. The key insight is to calculate products from both left and right directions to avoid division. For interview practice, focus on the space-optimized O(1) extra space solution.