#7 Medium Time O(n) Space O(1) Animated

Product of Array Except Self

Return an array where each element is the product of all other elements.

LeetCode ↗

Approach: Prefix and Suffix Products (O(1) Space)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Return an array where each element is the product of all other elements.

Constraints

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

Solution — Prefix and Suffix Products (O(1) Space)

O(n) O(1)

def productExceptSelf(nums):
    res = [1] * (len(nums))
    
    prefix = 1
    for i in range(len(nums)):
        res[i] = prefix
        prefix *= nums[i]
        
    postfix = 1
    for i in range(len(nums) - 1, -1, -1):
        res[i] *= postfix
        postfix *= nums[i]
        
    return res

Encode and Decode Strings

Valid Sudoku

Product of Array Except Self

Steps

Description

Constraints

Tags

Solution — Prefix and Suffix Products (O(1) Space)