Product of Array Except Self in Python | Optimal O(n) Solution Without Division
📌 Problem Statement:
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all elements except nums[i].
⚠️ Constraints:
You cannot use the division operation.
Your solution must run in O(n) time complexity.
🔹 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]
💡 Step-by-Step Explanation of the Code:
✅ Step 1: Initialize the Result Array
We first create an array answer of size n filled with 1.
answer = [1] * n
This array will store the final result, where answer[i] will contain the product of all elements except nums[i].
✅ Step 2: Compute Prefix Products
We traverse from left to right, storing the product of all elements before index i in answer[i].
prefix = 1
for i in range(n):
answer[i] = prefix
prefix *= nums[i]
🔹 prefix starts at 1.
🔹 At each step, answer[i] stores the cumulative product before nums[i].
🔹 Then, we update prefix by multiplying it with nums[i].
Example Calculation for [1,2,3,4]:
Index nums[i] prefix (before) answer[i] (stores prefix) prefix (after update)
0 1 1 1 1 × 1 = 1
1 2 1 1 1 × 2 = 2
2 3 2 2 2 × 3 = 6
3 4 6 6 6 × 4 = 24
At the end of this step, answer = [1, 1, 2, 6].
✅ Step 3: Compute Suffix Products
We traverse from right to left, keeping track of the product of all elements after index i.
We multiply answer[i] (which already contains the prefix product) by this suffix product.
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix
suffix *= nums[i]
🔹 suffix starts at 1.
🔹 At each step, we multiply answer[i] (which already contains prefix product) by suffix.
🔹 Then, we update suffix by multiplying it with nums[i].
Example Calculation for [1,2,3,4]:
Index nums[i] suffix (before) answer[i] (prefix × suffix) suffix (after update)
3 4 1 6 × 1 = 6 1 × 4 = 4
2 3 4 2 × 4 = 8 4 × 3 = 12
1 2 12 1 × 12 = 12 12 × 2 = 24
0 1 24 1 × 24 = 24 24 × 1 = 24
At the end of this step, answer = [24, 12, 8, 6]. 🎯
📌 Complete Python Code:
class Solution:
def productExceptSelf(self, nums):
n = len(nums)
answer = [1] * n # Step 1: Initialize result array
Step 2: Compute prefix products
prefix = 1
for i in range(n):
answer[i] = prefix
prefix *= nums[i]
Step 3: Compute suffix products
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix
suffix *= nums[i]
return answer
Example usage:
sol = Solution()
print(sol.productExceptSelf([1, 2, 3, 4])) # Output: [24, 12, 8, 6]
print(sol.productExceptSelf([-1, 1, 0, -3, 3])) # Output: [0, 0, 9, 0, 0]
🚀 Time and Space Complexity Analysis:
🔹 Time Complexity: O(n) - We traverse the array twice.
🔹 Space Complexity: O(1) (excluding output array).
🎯 Why This Solution is Optimal?
✅ Runs in O(n) time complexity
✅ Uses constant extra space (O(1))
✅ Does not use division, as required in the problem constraints