# Problem Statement#

We have to implement a productExceptSelf function that takes an integer array nums as input and returns another array answer as output. The element answer[i] will be the product of all elements in inputArray except inputArray[i]. The implementation should not contain a division (/) operation because the answer array could also be created by iterating over all elements in inputArray and dividing them from the product of the complete array.

# Brute Force Solution#

The brute-force solution to this problem could be implemented using nested loops. Where the first loop will select an element from the array and the second loop will be used to calculate the product without the element from the first loop.

## Psuedo-code for the Brute Force Solution#

answer = []
loop index on nums
product = 1
loop index2 on nums
if index!=index2
product *= nums[index2]



## Time Complexity Analysis#

### Best Case Scenario#

The brute-force solution will return the answer array in $O(n^2)$ time for the best-case input. Since both the loops will iterate completely over the nums array.

### Worst Case Scenario#

The worst-case scenario will also take $O(n^2)$ to return the solution.

## Space Complexity Analysis#

The answer array will require additional $O(n)$ memory.

## Code for the Brute Force Solution#

package main

import "fmt"

func productExceptSelf(nums []int)([]int){
for index:=0;index<len(nums);index++{
product := 1
for index2:=0;index2<len(nums);index2++{

// Skip the element selected by the outer loop
if index!=index2{
product *= nums[index2]
}
}
}
}

func main(){
nums := []int{1, 2, 3, 4}
fmt.Println("Product Except Self:", productExceptSelf(nums))

nums = []int{45, 34, 67, 86, 23}
fmt.Println("Product Except Self:", productExceptSelf(nums))
}

// Output
// Product Except Self: [24 12 8 6]
// Product Except Self: [4505884 5963670 3026340 2357730 8815860]


# Optimized Solution#

If we have to improve the time complexity of brute-force solution then we have to think of something other than nested loops.

The “product except self” for an element nums[i] refers to the product of all elements before and after nums[i] i.e. answer[i] = nums[0:i-1] * nums[i+1:]. Thus, we can implement the productExceptSelf function with $O(n)$ time complexity if we calculate two arrays prefix and suffix where

• prefix[i] is the product of all elements before nums[i] • suffix[i] is the product of all elements after nums[i] and multiply them to create the answer array.

## Psuedo code for the Optimized Solution#

prefix = []
loop index on nums
prefixProduct = 1
prefix.append(prefixProduct)
prefixProduct *= nums[index]

suffix = []
loop index from length(nums)-1 to 0
suffixProduct = 1
suffix.append_at_start(suffixProduct)
suffixProduct *= nums[index]

loop index on prefix



## Time Complexity Analysis#

### Best Case Scenario#

The optimized solution will return the answer array in $O(n)$ time (generalized from $O(3n)$) since the time complexity of iterating over all three arrays (prefix, suffix, and answer) is $O(n)$.

### Worst Case Scenario#

The time complexity of iterating over arrays in worst-case input is the same as in the best-case scenario. Thus, the total time complexity of the function remains the same i.e. $O(n)$.

## Space Complexity Analysis#

To store the prefix, suffix, and answer array we will need additional $O(3n)$ memory. We can improve the space complexity if we use a single array for storing the products of prefix and suffix and return it as the answer.

## Code for the Optimized Solution#

package main

import "fmt"

func productExceptSelf(nums []int)([]int){
prefix := []int{}
prefixProduct := 1
for index:=0;index<len(nums);index++{
prefix = append(prefix, prefixProduct)
prefixProduct *= nums[index]
}

suffix := []int{}
suffixProduct := 1

// Loop over the nums array in reverse
// starting from the last element

for index:=(len(nums)-1);index>(-1);index--{
// Append the element at the start
// rather than at the end
suffix = append([]int{suffixProduct}, suffix...)
suffixProduct *= nums[index]
}

for index:=0;index<len(prefix);index++{
// Multiply prefix and suffix elements
// to create the answer array
}

}

func main(){
nums := []int{4, 2, 3, 7}
fmt.Println("Product Except Self:", productExceptSelf(nums))

nums = []int{45, 34, 67, 86, 23}
fmt.Println("Product Except Self:", productExceptSelf(nums))
}

// Output
// Product Except Self: [42 84 56 24]
// Product Except Self: [4505884 5963670 3026340 2357730 8815860]


## Code for the Optimized Solution (Constant Space Complexity)#

Assuming the memory space required by the answer array is constant i.e. $O(1)$.

package main

import "fmt"

func productExceptSelf(nums []int)([]int){

// Fill up the answer array with prefixes
prefixProduct := 1
for index:=0;index<len(nums);index++{
prefixProduct *= nums[index]
}

// Multiply suffixes with the existing
// values in the answer array i.e. prefixes
suffixProduct := 1
for index:=(len(nums)-1);index>(-1);index--{
suffixProduct *= nums[index]
}

}

func main(){
nums := []int{4, 2, 3, 7}
fmt.Println("Product Except Self:", productExceptSelf(nums))

nums = []int{45, 34, 67, 86, 23}
fmt.Println("Product Except Self:", productExceptSelf(nums))
}

// Output
// Product Except Self: [42 84 56 24]
// Product Except Self: [4505884 5963670 3026340 2357730 8815860]


Thank you for taking the time to read this blog post! If you found this content valuable and would like to stay updated with my latest posts consider subscribing to my RSS Feed.