238.product-of-array-except-self.md

238. Product of Array Except Self

For the index i, we can calculate the product of all elements before i and all elements after i. That is the prefix and suffix product. So we can iterate to calculate the product of all elements to the left of each element and all elements to the right of each element.

|Prefix| i |Suffix|

• prefix[i] = prefix[i - 1] * nums[i - 1]
• suffix[i] = suffix[i + 1] * nums[i + 1]

input     [2, 3, 5]
prefix[i]  1  2  6   
suefix[i] 15  5  1

Then we multiple the prefix and suffix together.

def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    prefix_prod = [1] * n
    suffix_prod = [1] * n
    for i in range(1, n):
        prefix_prod[i] = prefix_prod[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        suffix_prod[i] = suffix_prod[i + 1] * nums[i + 1]

    answer = [1] * n
    for i in range(0, n):
        answer[i] = prefix_prod[i] * suffix_prod[i]
    return answer

fun productExceptSelf(nums: IntArray): IntArray {
    val prefixProducts = IntArray(nums.size) 
    val suffixProducts = IntArray(nums.size)
    prefixProducts[0] = 1
    for (i in 1 until nums.size) {
        prefixProducts[i] = prefixProducts[i - 1] * nums[i - 1]
    }
    suffixProducts[nums.size - 1] = 1
    for (i in nums.size - 2 downTo 0) {
        suffixProducts[i] = suffixProducts[i + 1] * nums[i + 1]
    }

    val answers = IntArray(nums.size)
    for (i in 0 until nums.size) {
        answers[i] = prefixProducts[i] * suffixProducts[i]
    }
    return answers
}

• Time Complexity: O(n).
• Space Complexity: O(n).

Space Optimization

We can use answer array as prefix product (the answer array does not count as extra space), and keep track the suffix to get the answer.

def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    answers = [1] * n
    for i in range(1, n):
        answers[i] = answers[i - 1] * nums[i - 1]
    suffix = nums[n - 1]
    for i in range(n - 2, -1, -1):
        answers[i] *= suffix
        suffix *= nums[i]
    return answers

fun productExceptSelf(nums: IntArray): IntArray {
    val answers = IntArray(nums.size)
    answers[0] = 1
    for (i in 1 until nums.size) {
        answers[i] = answers[i - 1] * nums[i - 1]
    }
    var suffix = nums[nums.size - 1]
    for (i in nums.size - 2 downTo 0) {
        answers[i] *= suffix
        suffix *= nums[i]
    }
    return answers
}

• Time Complexity: O(n).
• Space Complexity: O(1).