Problem Statement in English

You’re given an array nums. Your task is to return an array where array[i] is the product of values at all indices in the array except $i$.

Further, you must solution must run in linear time, $O(n)$, and you must not use division!

Approach

This problem would have been really easy had it not been for the restriction on division operations. But no matter, we have a trick up our sleeve: Prefix Sums. Let’s deviate for just a bit and get the hang of this technique.

Imagine you had an array arr, say you had to return an array where each index contained the sum of all values at all indices before it, and you had to do it in linear time, without subtraction. Sounds a little like the original problem? That’s because it is. You can use the exact same approach. Here’s what the answer would look like:

arr = [1,2,3,4], ans = [0,1,3,6]

But how do we do it? Instead of me explaining, try going through this code snippet and understanding. It’s way shorter than any explanation I can provide.

ans = []

for i in range(len(arr)):
    if i == 0:
        ans.append(0)
    else:
        ans.append(ans[-1]+arr[i-1])

return ans

We utilise a similar approach with the original problem. But since we need the product of values at indices before and after this one, we’ll need to make a forward and backward pass.

Step 1: Forward Pass

  • Step 1.1: Store the product of all terms before index $i$, at leftPass[i]

Step 2: Backward Pass

  • Step 2.1: Store the product of all terms after index $i$, at leftPass[i]

Step 3: Combined Pass

  • Step 3.1: Calculate value at index $i$ as leftPass[i]*rightPass[i]

Solution in Python


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # we store products calculated 
        # in the left pass here
        forwardPass = []

        # we store products calculated
        # in the right pass here
        backwardPass = []

        # we store our final answer here
        ans = []

        # forward pass
        for i in range(len(nums)):
            if i == 0:
                forwardPass.append(1)
            else:
                forwardPass.append(forwardPass[-1]*nums[i-1])
            pass

        # backward pass
        for i in range(len(nums)-1, -1, -1):
            if i == len(nums)-1:
                backwardPass.insert(0, 1)
            else:
                backwardPass.insert(0, backwardPass[0]*nums[i+1])
            pass

        # combined pass
        for i in range(len(nums)):
            ans.append(forwardPass[i]*backwardPass[i])

        return ans

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements atmost. The fact that we iterate over them thrice is inconsequential, since this is Big O complexity.

  • Space: $O(n)$
    Since we store at most $n$ elements. The fact that we store $3\text{n}$ elements is inconsequential, since this is Big O complexity.

Mistakes I Made

This approach didn’t occur to me. I needed a nudge in the right direction - the question tags.

And we are done.