LeetCode Meditations: Product of Array Except Self

The description of this problem states that:

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

For example:

productExceptSelf([1, 2, 3, 4]);
// -> [24, 12, 8, 6]

productExceptSelf([-1, 1, 0, -3, 3]);
// -> [0, 0, 9, 0, 0]

---

If we want to ignore the runtime having to be $O(n)$ , a very naive idea is to get the product of the filtered version of the array... for each element (where the indices of the array do not include the current item's index).

Yes, I know that sounds terrible, but well, it works for most of the test cases until it hits one with a Time Limit Exceeded error because it's far from optimal:

function productExceptSelf(nums: number[]): number[] {
  let result = [];
  for (let i = 0; i < nums.length; i++) {
    result[i] = nums
      .filter((_, idx) => idx !== i)
      .reduce((acc, item) => acc * item, 1);
  }

  return result;
};

Time and space complexity

This is not a solution to the problem, but the time complexity will be $O(n^3)$ as we do filter and reduce for each element. As we create another array using filter() for each iteration, the space complexity is, I think, $O(n^2)$ .

So, after a deep breath, let's see NeetCode's solution.

---

Here is a very clever solution. We'll make use of prefix and postfix variables. They have to be 1 as default, as it is the identity for multiplication. Prefix will start from the first element of the array and calculate the product so far up to the last element, and it'll be updated with the new value as we go.

So, for example, if the nums array is [2, 3, 5], we'll go up to 5:

[2, 3, 5] // nums


1 -> initial value of prefix


2 * 1 = 2 -> nums[0] * prefix = new prefix

3 * 2 = 6 -> nums[1] * prefix = new prefix


[1, 2, 6] // result

It might be easier to see with code:

let result: number[] = [];
let prefix = 1; // Initial value

for (let i = 0; i < nums.length; i++) {
  result[i] = prefix;
  prefix *= nums[i];
}

Postfix will start from the end of the array, and starting from the last item, it'll calculate the products so far as well. But we need to multiply it with the values calculated with the prefix, so that we get what we want: the total product of all elements before and after the $i$ th element.

In the example above, our result looked like [1, 2, 6] so far. We're going reverse this time, starting from the last element, up to the first one:

[2, 3, 5] // nums
[1, 2, 6] // result created so far thanks to prefix

1 -> initial value for postfix


6 * 1 = 6
-> result[result.length - 1] * postfix = new result[result.length - 1]

5 * 1 = 5
-> nums[nums.length - 1] * postfix = new postfix



2 * 5 = 10
-> result[result.length - 2] * postfix = new result[result.length - 2]

3 * 5 = 15
-> nums[nums.length - 2] * postfix = new postfix



1 * 15 = 15
-> result[result.length - 3] * postfix = new result[result.length - 3]


[15, 10, 6] // end result

Again, in code:

let result: number[] = [];
let prefix = 1; // Initial value

for (let i = 0; i < nums.length; i++) {
  result[i] = prefix;
  prefix *= nums[i];
}

// focus(1:6)
let postfix = 1; // Initial value

for (let i = nums.length - 1; i > -1; i--) {
  result[i] *= postfix;
  postfix *= nums[i];
}

Note
We multiply the value in result[i] with postfix this time, instead of just assigning result[i] the value of postfix (as we did with prefix).

---

One deep breath, and here is the Python version of the whole thing:

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

        for i in range(len(nums)):
            result[i] = prefix
            prefix *= nums[i]

        for i in range(len(nums) - 1, -1, -1):
            result[i] *= postfix
            postfix *= nums[i]

        return result

And, here is the TypeScript version:

function productExceptSelf(nums: number[]): number[] {
    let result = Array.from({ length: nums.length }, () => 1);
    let prefix = 1;
    let postfix = 1;

    for (let i = 0; i < nums.length; i++) {
        result[i] = prefix;
        prefix *= nums[i];
    }

    for (let i = nums.length - 1; i > -1; i--) {
        result[i] *= postfix;
        postfix *= nums[i];
    }

    return result;
};

---

Once again, to understand the idea better, if our array is this:

[🌸, 🍁, 🍀, 🌼]

Then, at the end of the first loop where we used prefix, result looks like this:

[
    1, 
    🌸, 
    🌸 * 🍁, 
    🌸 * 🍁 * 🍀
]

And, after the second loop where we used postfix, result looks like this:

[
    🍁 * 🍀 * 🌼 * (1),
    🍀 * 🌼 * (🌸),
    🌼 * (🌸 * 🍁),
    1 * (🌸 * 🍁 * 🍀)
]

Note
The values inside the parentheses are the previous values of result.

Time and space complexity

This version has $O(n)$ time complexity, as each loop just iterates through the elements of nums once, which is linear time.

Since we use a fixed amount of space, the space complexity is technically $O(n)$ because we initialize result with the length of nums, but the description for this problem states that the output array does not count as extra space, so it is $O(1)$ .

---

Next up is Longest Consecutive Sequence, until then, happy coding.