Problem - Leetcode

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements ofnums 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]

Constraints:

• 2 <= nums.length <= 10<sup>5</sup>

• -30 <= nums[i] <= 30

• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Answer-1 in Golang

func productExceptSelf(nums []int) []int {
    answer := make([]int, len(nums))
    pre := 1
    pos := 1
    for i := 0; i < len(nums); i++ {
        answer[i] = pre
        pre = nums[i] * pre
    }
    for i := len(nums) - 1; i >= 0; i-- {
        answer[i] *= pos
        pos = nums[i] * pos
    }
    return answer
}

This code defines a function named productExceptSelf that takes an array of integers nums as input and returns an array of integers. The returned array contains the product of all elements in the input array except the element at the same index.

Here's a step-by-step explanation of how the code works:

1. The function initializes an array called answer to store the final results. The size of this array is the same as the size of the input nums array.

2. It also initializes two variables pre and suf to keep track of products before and after the current element, respectively. pre is initially set to 1, and suf is also initially set to 1.

3. The first loop (for-loop) runs through the nums array from left to right. For each element at index i, it assigns the value of pre to the corresponding index in the answer array. Then, it updates the value of pre by multiplying it with the current element nums[i].

4. After the first loop, the pre variable holds the product of all elements to the left of the current element.

5. The second loop (for-loop) runs through the nums array from right to left. For each element at index i, it multiplies the corresponding index in the answer array with the value of suf. Then, it updates the value of suf by multiplying it with the current element nums[i].

6. After the second loop, the suf variable holds the product of all elements to the right of the current element.

7. Finally, the answer array contains the product of all elements except the element at the same index.

8. The function returns the answer array, which now holds the desired product of elements except self.

In summary, this code efficiently calculates the product of all elements except the current element for each index in the input array by using two passes through the array. The first pass calculates the products to the left of each element, and the second pass calculates the products to the right of each element, effectively giving the product of all elements except self.

Answer-2 Top Runtime in Golang

func productExceptSelf(xs []int) (ys []int) {
    n := len(xs)
    ys = make([]int, n)
    ys[0] = 1
    for i := 1; i < n; i++ {
        ys[i] = ys[i-1] * xs[i-1]
    }
    r := 1
    for i := n - 1; i >= 0; i-- {
        ys[i] *= r
        r *= xs[i]
    }
    return
}

This code is implementing a function called productExceptSelf that takes a slice of integers xs as input and returns another slice of integers ys. The goal of this function is to generate a new slice ys where each element at index i contains the product of all elements in the input xs except the element at index i.

Here's a step-by-step breakdown of how the code works:

1. n := len(xs) calculates the length of the input slice, which is the number of elements in the array.

2. ys = make([]int, n) initializes a new integer slice ys of the same length as the input xs.

3. ys[0] = 1 sets the first element of the ys slice to 1. This serves as a starting point for the product calculations.

4. The loop for i := 1; i < n; i++ iterates through the input slice starting from index 1. It calculates the product of all elements to the left of index i and stores it in the corresponding position in the ys slice. This is done using the formula: ys[i] = ys[i-1] * xs[i-1]. Essentially, it accumulates the product of elements to the left.

5. r := 1 initializes a variable r to store the running product of elements to the right of the current element.

6. The loop for i := n - 1; i >= 0; i-- iterates through the input slice in reverse order. For each element at index i, it updates the value of ys[i] by multiplying it with the running product r. It then updates the running product r by multiplying it with the corresponding element in the input slice xs.

7. Finally, the function returns the ys slice, which now contains the products of all elements in the input xs except the corresponding element at each index.

In summary, this code calculates the product of all elements in the input slice xs except the element at each index, using two passes through the input slice and some clever multiplication and accumulation techniques. The first pass accumulates the product of elements to the left of each index, and the second pass combines it with the product of elements to the right of each index to get the final result.

Answer-3 Top Memory in Golang

func productExceptSelf(nums []int) []int {
    g := make([]int, len(nums), len(nums))
    s := make([]int, len(nums), len(nums))

    g[0] = 1
    s[len(nums) - 1] = 1

    for i := 1; i < len(nums); i++ {
        g[i] = g[i-1] * nums[i-1]
    }

    for i := len(nums) - 2; i >=0; i-- {
        s[i] = s[i+1] * nums[i+1]
    }

    for i := 0; i < len(nums); i++ {
        nums[i] = g[i] * s[i]
    }

    return nums
}

This code is implementing a function called productExceptSelf that takes an array of integers nums as input and returns an array of integers where each element is the product of all the elements in the input array except the one at the current index. In other words, the function calculates the product of all elements except the current one.

Here's a step-by-step explanation of how the code works:

1. Two arrays, g and s, are initialized with the same length as the input nums array. These arrays will store the product of all elements to the left and right of the current index, respectively.

2. The initial values of g and s are set. g[0] is initialized to 1 because there are no elements to the left of the first element. Similarly, s[len(nums) - 1] is initialized to 1 because there are no elements to the right of the last element.

3. The first loop calculates the cumulative product of elements to the left of the current index and stores it in the g array. Starting from index 1, each element in g is calculated by multiplying the previous element in g with the corresponding element in the input array nums.

4. The second loop calculates the cumulative product of elements to the right of the current index and stores it in the s array. Starting from the second-to-last index (len(nums) - 2), each element in s is calculated by multiplying the next element in s with the corresponding element in the input array nums.

5. The final loop calculates the product of elements at each index by multiplying the corresponding values from the g and s arrays. The resulting product is assigned back to the nums array, effectively replacing the original values.

6. Finally, the modified nums array is returned as the output of the function.

In essence, this code uses two separate arrays to keep track of products to the left and right of each index, and then combines these products to calculate the final product except self for each element in the input array. This approach avoids the need for repeated multiplication and results in a linear time complexity solution.