Product Of Array Except Self Solution for TCS NQT
Company: TCS NQT · Difficulty: Medium · Topics: 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].
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.
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:
- answer[0] = 1 × 0 × (-3) × 3 = 0
- answer[1] = (-1) × 0 × (-3) × 3 = 0
- answer[2] = (-1) × 1 × (-3) × 3 = 9
- answer[3] = (-1) × 1 × 0 × 3 = 0
- answer[4] = (-1) × 1 × 0 × (-3) = 0
Example 3:
Input: nums = [2,3,4,5]
Output: [60,40,30,24]
Explanation:
- answer[0] = 3 × 4 × 5 = 60
- answer[1] = 2 × 4 × 5 = 40
- answer[2] = 2 × 3 × 5 = 30
- answer[3] = 2 × 3 × 4 = 24
Intuition
The key insight is to use two passes through the array:
1. First pass: Calculate the product of all elements to the left of each position
2. Second pass: Calculate the product of all elements to the right of each position and multiply with the left product
This approach avoids division and achieves O(n) time complexity.
Approach
Approach 1: Two-Pass with Extra Space
1. Create a result array of the same size
2. First pass (left to right): Calculate left products
- For each position i, result[i] = product of all elements from index 0 to i-1
3. Second pass (right to left): Calculate right products and combine
- Use a running product variable for right side
- Multiply result[i] with the running product
Approach 2: Two-Pass with Constant Space (Optimal)
1. Use the result array to store left products in the first pass
2. Use a running product variable for right side in the second pass
3. Multiply and update the result array in-place
Approach 3: Single Pass with Division (Not Allowed)
1. Calculate the total product of all elements
2. For each element, divide total product by the element
3. This approach is not allowed by the problem constraints
Dry Run
Let's trace through Example 1: nums = [1,2,3,4]
Two-Pass Approach:
First Pass (Left Products):
- result[0] = 1 (no elements to the left)
- result[1] = 1 (product of elements to the left: 1)
- result[2] = 2 (product of elements to the left: 1×2)
- result[3] = 6 (product of elements to the left: 1×2×3)
Second Pass (Right Products):
- rightProduct = 1
- result[3] = 6 × 1 = 6, rightProduct = 1 × 4 = 4
- result[2] = 2 × 4 = 8, rightProduct = 4 × 3 = 12
- result[1] = 1 × 12 = 12, rightProduct = 12 × 2 = 24
- result[0] = 1 × 24 = 24
Final Result: [24,12,8,6]
Key Insights
1. Two-Pass Strategy: Use left and right products to avoid division
2. In-Place Calculation: Can use the result array to store intermediate values
3. Running Product: Use a variable to track the product of elements on the right
4. Edge Cases: Handle arrays with zeros and negative numbers
Edge Cases
1. Array with zeros: Product becomes zero for positions with non-zero elements
2. Single element: Result is [1] (empty product is 1)
3. All zeros: Result is all zeros
4. Negative numbers: Handle sign changes correctly
Time and Space Complexity
- Time Complexity: O(n) - Two passes through the array
- Space Complexity: O(1) - Only using the result array (not counting input/output)