Product of array except self

Medium

Given an array of integer called nums, return the array such that the element at position i is equal to the product of all elements of nums except nums[i].

 

To solve this problem without using the division operation and in O(n) time complexity, we can utilize the concept of prefix and suffix products.

The idea is to calculate the product of all elements to the left of each element in the input array and store it in a separate array. Then, calculate the product of all elements to the right of each element and multiply it with the corresponding element in the left product array. This will give us the desired product except for the current element.

 

Algorithm

  1. Initialize an empty array called answer with the same length as the input nums array.
  2. Initialize a variable product to 1.
  3. Iterate through the nums array from left to right.
  4. Set answer[i] to the current value of product.
  5. Update the product by multiplying it with nums[i].
  6. Reset product to 1.
  7. Iterate through the nums array from right to left.
  8. Update answer[i] by multiplying it with the current value of product.
  9. Update the product by multiplying it with nums[i].
  10. Return the answer array.

 

Complexity

  • Time Complexity: O(N), where N is the size of the Array
  • Space Complexity: O(N), where N is the size of the Array

 

Code

## Java Code

import java.util.Arrays;

public class ProductExceptSelf {
    public static int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] result = new int[length];

        // Calculate the product of all elements to the left
        int leftProduct = 1;
        for (int i = 0; i < length; i++) {
            result[i] = leftProduct;
            leftProduct *= nums[i];
        }

        // Calculate the product of all elements to the right and combine with left product
        int rightProduct = 1;
        for (int i = length - 1; i >= 0; i--) {
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return result;
    }

    public static void main(String[] args) {
        // Example usage
        int[] nums = {1, 2, 3, 4};
        int[] result = productExceptSelf(nums);

        // Print the result
        System.out.print("Product except self: ");
        System.out.println(Arrays.toString(result));
    }
}
Output
Product except self: [24, 12, 8, 6]


Thanks for feedback.



Read More....
Find the no of islands in a 2D Array/Matrix
3 Sum
4 Sum - Find four elements that sum to a given target value
Chocolate Distribution Problem
Find the missing number in a sorted array
Best Time to Buy and Sell Stock