Skip to content

238. Product of Array Except SelfΒΆ

Problem Link

The catch of problem is we can't use division operator. If that wasn't the case, we could simply have aggregated multiplication of whole array and divide each element by it get their own product without self.

When translated to equations, this would look like: \(\prod_{i=1}^{n} nums_i \over nums_i\). By removing the division -> \(\prod_{i=1}^{i-1} nums_i * \prod_{i=i+1}^{n} nums_i\), which is basically product of prefix and postfix array to index i.

One way to implement this is to store prefix and postfix multiplication in two separate arrays and combine them to generate the result.

Follow Up

Instead of saving the prefix and postfix multiplication within separate array, we can simply store them within output array (since multiplication is communicative)

Pseudocode
  • To generate prefix, iterate from start of nums and using a variable to aggregate the multiplication over the iteration.
  • To generate postfix, iterate from end of nums and repeat same.
Runtime Complexity

Time: \(O(n)\)

Space: \(O(1)\) <- output isn't considered

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = []
        pre, post = 1, 1

        for i in range(len(nums)):
            result.append(pre)
            pre *= nums[i]

        for i in reversed(range(len(nums))):
            result[i] *= post
            post *= nums[i]
        print(result)
        return result

func productExceptSelf(nums []int) []int {
    result := make([]int, len(nums))
    var pre, post int = 1, 1
    for idx := range nums {
        result[idx] = pre
        pre *= nums[idx]
    }

    for idx := len(nums) - 1; idx >= 0; idx-- {
        result[idx] *= post
        post *= nums[idx]
    }
    return result
}