238. Product of Array Except Self

Link: https://leetcode.com/problems/product-of-array-except-self

Description:

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].

Solution:

This solution calculates the product of all elements in the array except for the element at each specific index, without using division. The approach uses prefix and postfix products to achieve this. Let's break down the code step by step, example array nums = [1,2,3,4].

Initial Setup:

res is initialized as an empty array to store the result. prefix and postfix are initialized to 1. They are used to calculate the product of all elements to the left (prefix) and right (postfix) of the current element, respectively.

First Loop - Prefix Product Calculation:

Iterate through the nums array from left to right. For each i, set res[i] to prefix. Initially, prefix is 1, so for the first element, it simply sets res[0] to 1. Multiply prefix by nums[i] to update the prefix for the next iteration. This means prefix accumulates the product of all elements to the left of the current index. After the first loop for nums = [1,2,3,4], res would be [1, 1, 2, 6]. This represents the product of all numbers to the left of each index (for the first element, there are no elements to the left, hence the product is 1).

Second Loop - Postfix Product Calculation:

Iterate through the nums array from right to left. Multiply res[i] by postfix and update res[i] with this product. This step combines the product of all elements to the left (already in res[i]) with the product of all elements to the right (represented by postfix). Multiply postfix by nums[i] to update the postfix for the next iteration. This updates postfix to include the product of all elements to the right of the current index. After the second loop for nums = [1,2,3,4], res is updated to [24, 12, 8, 6]. Here's how it works step-by-step for each element:

For index 3 (nums[3] = 4): The postfix is 1 (since there are no elements to the right), and res[3] was 6 from the first loop. Multiplying gives 6, which is correct since the product of all elements except nums[3] is 123 = 6. Then, postfix becomes 4. For index 2 (nums[2] = 3): res[2] is 2 from the first loop, and postfix is now 4. Multiplying gives 8, which matches the product of all elements except nums[2] (124 = 8). This process repeats for the remaining elements.

var productExceptSelf = function (nums) {
  const res = []
  let prefix = 1
  let postfix = 1

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

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

  return res
}