NUHMAN.com

🔍 Problem Statement

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

Note:

• You must solve it without using division and in O(n) time complexity.
• The answer is guaranteed to be fit in the 32-bit integer range.

Example 1:

go

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

Example 2:

go

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

🧠 Approach

The goal is to construct the answer array where each element at index i is the product of all elements in the array except the element at index i.

We can solve this problem efficiently in O(n) time by utilizing the following approach:

1. Prefix Products: Build an array where each element contains the product of all elements before the current element.
2. Suffix Products: Build another array where each element contains the product of all elements after the current element.
3. Multiply the prefix product with the suffix product for each index to get the result.

However, to optimize further, we can use a single array to store the results, and calculate the prefix products first, then update the array by multiplying with the suffix products in a second pass. This way, we only need O(n) space and O(n) time.

Steps:

1. First pass (Prefix Products):

• Iterate through the array from left to right and maintain a variable prefix to store the product of all elements before the current index.
• Store the prefix product in the answer array at each index.

1. Second pass (Suffix Products):

• Iterate through the array from right to left and maintain a variable suffix to store the product of all elements after the current index.
• Multiply the current value in the answer array with the suffix to get the final result.

✅ Go Implementation

go

package main

import "fmt"

// Function to return the product array except self
func productExceptSelf(nums []int) []int {
    n := len(nums)
    result := make([]int, n)

    // First pass: Compute the prefix product for each element
    prefix := 1
    for i := 0; i < n; i++ {
        result[i] = prefix
        prefix *= nums[i]
    }

    // Second pass: Compute the suffix product for each element
    suffix := 1
    for i := n - 1; i >= 0; i-- {
        result[i] *= suffix
        suffix *= nums[i]
    }

    return result
}

// Helper function to print the array
func printArray(arr []int) {
    for _, num := range arr {
        fmt.Print(num, " ")
    }
    fmt.Println()
}

// Test the productExceptSelf function
func main() {
    // Example 1: Input nums = [1, 2, 3, 4]
    nums1 := []int{1, 2, 3, 4}
    result1 := productExceptSelf(nums1)
    printArray(result1) // Output: [24, 12, 8, 6]

    // Example 2: Input nums = [-1, 1, 0, -3, 3]
    nums2 := []int{-1, 1, 0, -3, 3}
    result2 := productExceptSelf(nums2)
    printArray(result2) // Output: [0, 0, 9, 0, 0]
}

🧑‍💻 Explanation of the Code

1. productExceptSelf function:

• We initialize the result array to store the product for each index.
• In the first loop, we compute the prefix product and store it in the result array.
• In the second loop, we compute the suffix product and update the result array by multiplying it with the corresponding value.

1. printArray function:

• A helper function to print the elements of the array.

1. main function:

• Tests the productExceptSelf function with two example inputs and prints the results.

📦 Example Usage

go

func main() {
    // Example 1: Input nums = [1, 2, 3, 4]
    nums1 := []int{1, 2, 3, 4}
    result1 := productExceptSelf(nums1)
    printArray(result1) // Output: 24 12 8 6

    // Example 2: Input nums = [-1, 1, 0, -3, 3]
    nums2 := []int{-1, 1, 0, -3, 3}
    result2 := productExceptSelf(nums2)
    printArray(result2) // Output: 0 0 9 0 0
}

Example Output:

24 12 8 6
0 0 9 0 0

⏱️ Time & Space Complexity

• Time Complexity: O(n)
• We only traverse the array twice (one for prefix products and one for suffix products), so the time complexity is linear, O(n).
• Space Complexity: O(n)
• We use an additional array result to store the final result, so the space complexity is O(n). However, we could reduce the space complexity to O(1) by modifying the result array in-place (if we ignore the input/output space).