Efficiently Solving the “Product of Array Except Self” Problem in Java

In algorithmic problem-solving, the “Product of Array Except Self” problem is a fascinating challenge. It requires creating a new array where each element at index i of the new array is the product of all the numbers in the original array except the one at i. The catch? You must achieve this without using division and in optimal time complexity. Let’s explore this problem in depth and implement a solution in Java.

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

Example:

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

Constraints:

1. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
2. You must write an algorithm that runs in O(n) time and without using the division operation.

Approach

To solve this problem, we need to use a strategy that involves prefix and suffix products. The idea is to calculate the product of all elements to the left of each element and the product of all elements to the right. Then, multiply these two products to get the desired result.

Step-by-Step Solution

1. Initialize Arrays:

• Create two auxiliary arrays, left and right, of the same length as the input array nums.
• The left array will store the product of all elements to the left of the current element.
• The right array will store the product of all elements to the right of the current element.

1. Fill the Left Array:

• Traverse the nums array from left to right.
• For each element, calculate the product of all previous elements and store it in the left array.

1. Fill the Right Array:

• Traverse the nums array from right to left.
• For each element, calculate the product of all subsequent elements and store it in the right array.

1. Construct the Answer Array:

• Multiply the corresponding elements of the left and right arrays to get the final product for each position in the answer array.

Code Implementation

Here is the Java implementation of the above approach:

public class ProductOfArrayExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] answer = new int[n];

        // Step 1: Fill the left array
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }

        // Step 2: Fill the right array
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }

        // Step 3: Construct the answer array
        for (int i = 0; i < n; i++) {
            answer[i] = left[i] * right[i];
        }

        return answer;
    }

    public static void main(String[] args) {
        ProductOfArrayExceptSelf solution = new ProductOfArrayExceptSelf();
        int[] nums = {1, 2, 3, 4};
        int[] result = solution.productExceptSelf(nums);

        // Print the result array
        for (int value : result) {
            System.out.print(value + " ");
        }
    }
}

Explanation

• Initialization: We start by initializing the left, right, and answer arrays. The left array at index i will store the product of all elements to the left of i, and the right array at index i will store the product of all elements to the right of i.
• Left Array Calculation: For each element in the nums array, the left array at index i stores the product of all elements to its left.
• Right Array Calculation: Similarly, for each element in the nums array, the right array at index i stores the product of all elements to its right.
• Final Calculation: The answer at each index i is obtained by multiplying the corresponding elements of the left and right arrays.

Optimized Space Complexity

The above solution uses O(n) space for the left and right arrays. However, we can optimize it to use O(1) additional space by storing the left product in the answer array itself and calculating the right product on the fly.

Here is the optimized implementation:

public class ProductOfArrayExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        // Calculate left product and store it in answer array
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        // Calculate right product and multiply with the left product in answer array
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return answer;
    }

    public static void main(String[] args) {
        ProductOfArrayExceptSelf solution = new ProductOfArrayExceptSelf();
        int[] nums = {1, 2, 3, 4};
        int[] result = solution.productExceptSelf(nums);

        // Print the result array
        for (int value : result) {
            System.out.print(value + " ");
        }
    }
}

Conclusion

The “Product of Array Except Self” problem is a great example of how algorithmic challenges can be solved efficiently with thoughtful strategies. By using prefix and suffix products, we can achieve the desired result in O(n) time without division. Implementing such solutions in Java provides a clear understanding of array manipulation and optimization techniques. Whether you are preparing for coding interviews or honing your problem-solving skills, mastering this problem is a valuable addition to your toolkit.

Read More …

Solving the Square of a Rotated Array Problem – https://kamleshsingad.com/solving-the-square-of-a-rotated-array-problem/

Differences Between Arrays and Strings in Java – https://kamleshsingad.com/differences-between-arrays-and-strings-in-java/

Mastering Bit Manipulation: Squaring a Number Using Bitwise Operations in Java – https://kamleshsingad.com/mastering-bit-manipulation-squaring-a-number-using-bitwise-operations-in-java/