Product of Array Except Self

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given an array: return an array with product of the array except self at each position
• Do not use division
• Solve in $O(n)$ time & space complexity

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Prefix Sum
• Array

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• Maintain two arrays: prefix and suffix
• Prefix: Go left to right and at each place store product of everything before it
• Suffix: Go right to left and at each place store product of everything after it
• Result: Combine both array by multiplying items at each index

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Prefix Sum

Time & Space Complexity

• Time: $O(n)$ → Reason: We iterate through the array a few times but linearly
• Space: $O(n)$ → Reason: We store few copies of the array

Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        prefix = []
        prev = 1
        for i in range(len(nums)):
            prefix.append(prev)
            prev *= nums[i]

        suffix = []
        prev = 1
        for i in range(len(nums) - 1, -1, -1):
            suffix.append(prev)
            prev *= nums[i]
        suffix.reverse()

        result = []
        for p, s in zip(prefix, suffix):
            result.append(p * s)
        return result