Big O Practice: Product Except Self

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

Variables

• n - length of the input array nums

Explanation

Two linear passes - **O(n)** time. By convention the output array is excluded from auxiliary space, so this is **O(1)** auxiliary; only `left` and `right` accumulators are kept. (If you count the output, it is O(n).)

More Big O practice problems · Today's daily problem