NEETCODE - Arrays and Hashing: Products of Array Except Self

Array manipulation without division - From O(n²) nested loops to O(n) prefix-suffix pattern

Technology: Python, Algorithms
Skill: Array Traversal, O(n) Space

Problem Statement

Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].

Examples:

Input: nums = [1,2,4,6]
Output: [48,24,12,8]
Explanation:
- output[0] = 2*4*6 = 48
- output[1] = 1*4*6 = 24
- output[2] = 1*2*6 = 12
- output[3] = 1*2*4 = 8

Input: nums = [-1,0,1,2,3]
Output: [0,-6,0,0,0]
Explanation:
- output[0] = 0*1*2*3 = 0
- output[1] = (-1)*1*2*3 = -6
- output[2] = (-1)*0*2*3 = 0
- output[3] = (-1)*0*1*3 = 0
- output[4] = (-1)*0*1*2 = 0

Constraints:

• 2 <= nums.length <= 1000
• -20 <= nums[i] <= 20
• Each product is guaranteed to fit in a 32-bit integer
• Follow-up: Could you solve it in O(n) time without using division?

Edge Cases:

• Array with zeros (single or multiple)
• Array with negative numbers
• Array with all same values
• Minimum size array (length 2)

Solutions Progression

Approach 1: Brute Force with Nested Loops (O(n²))

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        output = []

for i in range(n):
            product = 1
            for j in range(n):
                if i != j:
                    product *= nums[j]
            output.append(product)

return output

Time Complexity: O(n²)
Space Complexity: O(1) excluding output array

Approach 2: Division with Edge Case Handling (O(n))

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        zero_count = 0
        product_without_zeros = 1

for num in nums:
            if num == 0:
                zero_count += 1
            else:
                product_without_zeros *= num

output = []
        for num in nums:
            if zero_count > 1:
                output.append(0)
            elif zero_count == 1:
                output.append(product_without_zeros if num == 0 else 0)
            else:
                output.append(product_without_zeros // num)

return output

Time Complexity: O(n)
Space Complexity: O(1) excluding output

Approach 3: Prefix and Suffix Products (Optimal - Two Arrays)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)

prefix = [1] * n
        for i in range(1, n):
            prefix[i] = prefix[i-1] * nums[i-1]

suffix = [1] * n
        for i in range(n-2, -1, -1):
            suffix[i] = suffix[i+1] * nums[i+1]

output = [prefix[i] * suffix[i] for i in range(n)]

return output

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

Approach 4: Space-Optimized Prefix-Suffix (Optimal - O(1) Space)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        output = [1] * n

for i in range(1, n):
            output[i] = output[i-1] * nums[i-1]

suffix = 1
        for i in range(n-1, -1, -1):
            output[i] *= suffix
            suffix *= nums[i]

return output

Time Complexity: O(n)
Space Complexity: O(1)

Pattern Recognition

Core Pattern: Prefix-Suffix Decomposition

This problem exemplifies a fundamental array pattern: decomposing a computation into prefix and suffix components.

product_except_self[i] = product(nums[0...i-1]) * product(nums[i+1...n-1])
                       = prefix[i] * suffix[i]

Real-World Applications

1. Financial Risk Modeling - Portfolio variance calculations excluding specific assets
2. Image Processing (Convolutions) - Computing filter responses with missing pixels
3. Machine Learning (Leave-One-Out Cross-Validation) - Training models excluding each sample
4. Database Query Optimization - Selectivity estimation for join ordering
5. Network Traffic Analysis - Calculating bandwidth excluding specific flows

Common Mistakes

1. Forgetting zero handling - Multiple zeros make all products zero
2. Integer overflow - Consider using long or BigInteger types
3. Off-by-one errors in prefix/suffix
4. Not considering negative numbers
5. Inefficient space usage - Creating both prefix and suffix arrays when one suffices

Complexity Summary Table