238. Product of Array Except Self

func productExceptSelf(nums []int) []int {
    length := len(nums)
    resultArr := make([]int, length)

    // Initialize the result array with 1's because 1 is the neutral element for multiplication.
    for i := range resultArr {
        resultArr[i] = 1
    }

    // Accumulate the left products
    leftProduct := 1
    for i := 0; i < length; i++ {
        resultArr[i] = leftProduct
        leftProduct *= nums[i]
    }

    // Accumulate the right products directly into the result array
    rightProduct := 1
    for i := length - 1; i >= 0; i-- {
        resultArr[i] *= rightProduct
        rightProduct *= nums[i]
    }

    return resultArr
}        

Time Complexity

• First for loop (Initializing the result array): This loop runs once for each element in the input array, giving us a time complexity of O(n), where n is the length of the input array.
• Second for loop (Accumulating left products): Similarly, this loop also iterates over all elements of the array once, contributing another O(n) to the time complexity.
• Third for loop (Accumulating right products): This loop, like the others, iterates over the entire array once, adding another O(n) to the time complexity.

Since these loops are sequential and not nested, the overall time complexity is the sum of their complexities. However, since each loop is O(n), the total time complexity remains O(n).

Space Complexity

• Extra Space for the Output Array (resultArr): The function allocates an array resultArr with the same length as the input array to store the result. This contributes O(n) to the space complexity.
• Auxiliary Space (Variables leftProduct and rightProduct): Aside from resultArr, the function only uses a few variables (leftProduct, rightProduct, and loop counters) that occupy constant space, O(1).

Considering the output array as part of the space requirement, the total space complexity is O(n). However, if we consider the output space not part of the auxiliary space complexity (as is common in many complexity analyses since the output does not count towards the "extra" space used by the algorithm), then the auxiliary space complexity would be O(1), indicating that the function uses constant extra space aside from the space needed for the output.