Leetcode 238. Product of Array Except Self

Problem

Leetcode 238 - Product of Array Except Self

Example:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Approach

We can do this in 2 iteration where first solves the prefix and second solves for suffix of the nums array.

We can calculate the prefix and suffix like this: - res[i] *= prefix (we’re updating the prefix of res) - prefix *= nums[i] (we’re updating prefix)

Visualization of the Approach:

nums = [1,2,3,4]

First Iteration:
res = [1,1,1,1]
prefix = 1

res = [1,1,1,1]
prefix = 1

res = [1,1,1,1]
prefix = 2

res = [1,1,2,1]
prefix = 6

res = [1,1,2,6]
prefix = 24

Second Iteration:
res = [1,1,2,6]
prefix = 1

res = [1,1,2,6]
prefix = 4

res = [1,1,8,6]
prefix = 12

res = [1,12,8,6]
prefix = 24

res = [24,12,8,6]
prefix = 24

Thus, res = [24, 12, 8, 6]

Here is the Python code for the solution:

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

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

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$ since The output array does not count as extra space for space complexity analysis