_238. Product of Array Except Self.md

238. Product of Array Except Self

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 13, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Prefix Sum

Acceptance Rate : 66.72 %

---

Solutions

• m238 v1 O(n) time O(n) space.py
• m238 v2 O(n) time O(1) space.py

Python

m238 v1 O(n) time O(n) space.py

# Question restriction: Must be O(n) and CANNOT use division
# This is O(n) time, O(n) space

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # O(n)
        numsLeftProd = [1] + nums.copy()
        numsRightProd = nums.copy() + [1]

        # O(n)
        for i in range(1, len(numsLeftProd)) :
            numsLeftProd[i] *= numsLeftProd[i - 1]

        # O(n)
        for i in range(len(numsRightProd) - 2, -1, -1) : 
            numsRightProd[i] *= numsRightProd[i + 1]
        
        # O(n)
        output = []
        for i in range(len(nums)) :
            output.append(numsLeftProd[i] * numsRightProd[i + 1])

        return output

m238 v2 O(n) time O(1) space.py

# Question restriction: Must be O(n) and CANNOT use division
# FOLLOWUP RESTRICTION: O(1) space

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # O(n) time and O(n) space
        output = [1] * len(nums)
        output[1] = nums[0]

        # O(n) time O(1) space
        for i in range(2, len(nums)) :
            output[i] = output[i - 1] * nums[i - 1]

        # O(n) time
        for i in range(len(nums) - 2, -1, -1) :
            output[i] *= nums[i + 1]
            nums[i] *= nums[i + 1]

        return output