Product of Array Expect Itself Leetcode Question - 238

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. Example 1: Input: nums = [1,2,3,4] Output: [24,12,8,6] Example 2: Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0] Solution Approach: Prefix and Postfix Products My solution uses a two-pass approach utilizing prefix and postfix products to efficiently solve the problem in O(n) time with O(1) extra space (excluding the output array). Key Insight Prefix product: The product of all elements to the left of the current element Postfix product: The product of all elements to the right of the current element The product of all elements except the current one is: prefix × postfix Algorithm Initialize a result array of the same size as the input array First pass: Calculate prefix products from left to right Second pass: Calculate postfix products from right to left, while multiplying with the existing prefix products Visualization For example, with input array nums = [1, 2, 3, 4]: First Pass (Prefix Products): Start with prefix = 1 For each position, store the current prefix in the result array, then update the prefix After first pass, result = [1, 1, 2, 6] Second Pass (Postfix Products): Start with postfix = 1 For each position (in reverse), multiply the existing value by the current postfix, then update the postfix After second pass, result = [24, 12, 4, 1] This gives us our answer, as each position now contains the product of all elements except the one at that position. Code Implementation Approach: Prefix and Postfix Products My solution uses a two-pass approach utilizing prefix and postfix products to efficiently solve the problem in O(n) time with O(1) extra space (excluding the output array). Key Insight Prefix product: The product of all elements to the left of the current element Postfix product: The product of all elements to the right of the current element The product of all elements except the current one is: prefix × postfix Algorithm Initialize a result array of the same size as the input array First pass: Calculate prefix products from left to right Second pass: Calculate postfix products from right to left, while multiplying with the existing prefix products Visualization For example, with input array nums = [1, 2, 3, 4]: First Pass (Prefix Products): Start with prefix = 1 For each position, store the current prefix in the result array, then update the prefix After first pass, result = [1, 1, 2, 6] Second Pass (Postfix Products): Start with postfix = 1 For each position (in reverse), multiply the existing value by the current postfix, then update the postfix After second pass, result = [24, 12, 4, 1] This gives us our answer, as each position now contains the product of all elements except the one at that position. Code Implementation My solution uses a two-pass approach utilizing prefix and postfix products to efficiently solve the problem in O(n) time with O(1) extra space (excluding the output array). Key Insight Prefix product: The product of all elements to the left of the current element Postfix product: The product of all elements to the right of the current element The product of all elements except the current one is: prefix × postfix Algorithm Initialize a result array of the same size as the input array First pass: Calculate prefix products from left to right Second pass: Calculate postfix products from right to left, while multiplying with the existing prefix products Visualization For example, with input array nums = [1, 2, 3, 4]: First Pass (Prefix Products): Start with prefix = 1 For each position, store the current prefix in the result array, then update the prefix After first pass, result = [1, 1, 2, 6] Second Pass (Postfix Products): Start with postfix = 1 For each position (in reverse), multiply the existing value by the current postfix, then update the postfix After second pass, result = [24, 12, 4, 1] This gives us our answer, as each position now contains the product of all elements except the one at that position. Code Implementation func productExceptSelf(nums []int) []int { // result array of the same size as input array res := make([]int,len(nums)) //calculate prefix prefix :=1 for i,v := range nums{ res[i] = prefix prefix = v } // Calculate postfix products and multiply with prefix products postfix := 1 for i := len(nums)-1; i >= 0 ; i--{ res[i] = postfix postfix *= nums[i] } return res }

Mar 8, 2025 - 07:47

Product of Array Expect Itself Leetcode Question - 238

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.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Solution
Approach: Prefix and Postfix Products
My solution uses a two-pass approach utilizing prefix and postfix products to efficiently solve the problem in O(n) time with O(1) extra space (excluding the output array).
Key Insight

Prefix product: The product of all elements to the left of the current element
Postfix product: The product of all elements to the right of the current element
The product of all elements except the current one is: prefix × postfix

Algorithm

Initialize a result array of the same size as the input array
First pass: Calculate prefix products from left to right
Second pass: Calculate postfix products from right to left, while multiplying with the existing prefix products

Visualization
For example, with input array nums = [1, 2, 3, 4]:
First Pass (Prefix Products):

Start with prefix = 1
For each position, store the current prefix in the result array, then update the prefix
After first pass, result = [1, 1, 2, 6]

Second Pass (Postfix Products):

Start with postfix = 1
For each position (in reverse), multiply the existing value by the current postfix, then update the postfix
After second pass, result = [24, 12, 4, 1]

This gives us our answer, as each position now contains the product of all elements except the one at that position.
Code Implementation
Approach: Prefix and Postfix Products
My solution uses a two-pass approach utilizing prefix and postfix products to efficiently solve the problem in O(n) time with O(1) extra space (excluding the output array).
Key Insight

Algorithm

Visualization
For example, with input array nums = [1, 2, 3, 4]:
First Pass (Prefix Products):

Start with prefix = 1
For each position, store the current prefix in the result array, then update the prefix
After first pass, result = [1, 1, 2, 6]

Second Pass (Postfix Products):

Start with postfix = 1
For each position (in reverse), multiply the existing value by the current postfix, then update the postfix
After second pass, result = [24, 12, 4, 1]

This gives us our answer, as each position now contains the product of all elements except the one at that position.
Code Implementation
My solution uses a two-pass approach utilizing prefix and postfix products to efficiently solve the problem in O(n) time with O(1) extra space (excluding the output array).
Key Insight

Algorithm

Visualization
For example, with input array nums = [1, 2, 3, 4]:
First Pass (Prefix Products):

Start with prefix = 1
For each position, store the current prefix in the result array, then update the prefix
After first pass, result = [1, 1, 2, 6]

Second Pass (Postfix Products):

Start with postfix = 1
For each position (in reverse), multiply the existing value by the current postfix, then update the postfix
After second pass, result = [24, 12, 4, 1]

This gives us our answer, as each position now contains the product of all elements except the one at that position.
Code Implementation

func productExceptSelf(nums []int) []int {
// result array of the same size as input array
    res := make([]int,len(nums))
//calculate prefix
    prefix :=1
    for i,v := range nums{
        res[i] = prefix
        prefix *= v
    }

// Calculate postfix products and multiply with prefix products
    postfix := 1
    for i := len(nums)-1; i >= 0 ; i--{
      res[i] *= postfix
      postfix *= nums[i]
    }

    return res
}