Solving the DSA Prefix Sum Product Array Puzzle

Problem Statement

Given an array of integers A, let's find and return a new array of the same size. In this new array, each element at index i will be the product of all the elements in the original array except the one at i.

Note: You can always create this product array using 32-bit integer values. Try solving it without using the division operator.

Input Format

The only argument given is the integer array A.

Output Format

Return the product array.

Constraints

2 <= length of the array <= 1000
1 <= A[i] <= 10

For Example

Input 1:
    A = [1, 2, 3, 4, 5]
Output 1:
    [120, 60, 40, 30, 24]

Input 2:
    A = [5, 1, 10, 1]
Output 2:
    [10, 50, 5, 50]

Solution:

public class PuzzelArraySolution {
    public int[] solve(int[] A) {
         int n = A.length;
        int leftArrayResult[] = new int[n];

        leftArrayResult[0] = 1;
        for(int i=1; i< n ; i++){
            leftArrayResult[i] = A[i-1]*leftArrayResult[i-1];

        }
        int rightArrayResult[] = new int[n];
        rightArrayResult[n-1] = 1;
        for(int i=n-2; i>=0 ; i--){
            rightArrayResult[i] = A[i+1]*rightArrayResult[i+1];

        }

        int result[] = new int[A.length];
        for(int i=0;i<A.length;i++){
            result[i] = leftArrayResult[i]*rightArrayResult[i];
        }
        return result;
    }
}

• n is the length of the input array A.

• leftArrayResult is an array used to store the product of all elements to the left of each index in A.

• leftArrayResult[0] is initialized to 1 because there are no elements to the left of the first element.

• The loop iterates through the array starting from the second element (index 1):

• For each index i, leftArrayResult[i] is set to the product of A[i-1] (the element just before the current index) and leftArrayResult[i-1] (the product of all elements to the left of the previous index).

This effectively computes the product of all elements to the left of each index.

• rightArrayResult[n-1] is initialized to 1 because there are no elements to the right of the last element.

• The loop iterates backward through the array starting from the second-to-last element (index n-2):

• For each index i, rightArrayResult[i] is set to the product of A[i+1] (the element just after the current index) and rightArrayResult[i+1] (the product of all elements to the right of the next index).

This computes the product of all elements to the right of each index.

• result is the final array where each element at index i is the product of the corresponding elements from leftArrayResult and rightArrayResult.

Essentially, this means result[i] contains the product of all elements in A except A[i], which is the desired output.

Summary

The method computes the product of all elements except the current one for each index in the input array A. It does this by:

• Calculating the product of elements to the left of each index.

• Calculating the product of elements to the right of each index.

• Combining these two results to get the final product for each index.

This approach ensures that you get the correct result efficiently, avoiding the need for nested loops, and operates in linear time complexity, O(n).