Product of Array Except Self

Given an array nums of n integers where n > 1, the goal is to return an array output such that each element at index i of output is equal to the product of all the numbers in the original array except nums[i].

1. Initialization: result is initialized to store the final output, with all elements set to 1. We also initialize two variables leftRunningProduct and rightRunningProduct to 1, which will be used to store the product of elements to the left and right of the current index, respectively.

2. First Traversal (Left Product): We traverse the array from left to right. For each element at index i, we set result[i] to the current value of leftRunningProduct. Then, we update leftRunningProduct by multiplying it with nums[i].

3. Second Traversal (Right Product): We traverse the array from right to left. For each element at index i, we multiply result[i] by the current value of rightRunningProduct. Then, we update rightRunningProduct by multiplying it with nums[i].

This approach ensures that result[i] contains the product of all elements except nums[i] after both traversals.

Example

Let's illustrate how the solution works:

Input array: nums = [4, 8, 2, 3]

Initialization:
result              = [1, 1, 1, 1]
leftRunningProduct  = 1
rightRunningProduct = 1

First traversal (left product):
result[0] = 1
leftRunningProduct = 1 * 4 = 4

result[1] = 1 * 4 = 4
leftRunningProduct = 4 * 8 = 32

result[2] = 1 * 32 = 32
leftRunningProduct = 32 * 2 = 64

result[3] = 1 * 64 = 64
leftRunningProduct = 64 * 3 = 192

After first traversal:
result = [1, 4, 32, 64]

Second traversal (right product):
result[3] = 64 * 1 = 64
rightRunningProduct = 1 * 3 = 3

result[2] = 32 * 3 = 96
rightRunningProduct = 3 * 2 = 6

result[1] = 4 * 6 = 24
rightRunningProduct = 6 * 8 = 48

result[0] = 1 * 48 = 48
rightRunningProduct = 48 * 4 = 192

After second traversal:
result = [48, 24, 96, 64]

Final result = [48, 24, 96, 64]

Solution

Time Complexity: The time complexity of this solution is O(n), where n is the number of elements in the input array nums. This is because we traverse the array three times (one pass to compute leftProduct, one pass to compute rightProduct, and one pass to compute the result).

Space Complexity The space complexity of this solution is O(n).

The result array, which is necessary to store the final output, requires O(n) space. The additional space used for the left and right running products is O(1) because they are single variables that do not scale with the input size.

Therefore, the total space complexity is O(n) due to the result array.