Java DSA Challenge: Product of Array Except Self

How to solve the Product of Array Except Self Data Structures and Algorithms problem in Java!

This problem comes from LeetCode #238: https://leetcode.com/problems/product-of-array-except-self/

Problem Description

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

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

!! You must write an algorithm that runs in O(n) time and without using the division operation.

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

Breaking it Down

The goal of this problem is to compute the desired products and return them into an array in the proper order.

We know we will need to visit each element in the input array once. This means we need to loop through the array. We will also have to remember the original values of each element after we visit them once, because we want the product of each other element except the one at the current index. Remembering these values is most easily achieved by making a copy of the array.

Brute Force Approach

The simplest approach is the best place to start, so let’s brute force the solution and see what insights we get.

Let’s make a copy of our input array, and then loop through it to compute the products and store those products in the original array so that it stores our desired result.

Here is the code:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] numscpy = nums.clone();
        for (int i = 0; i < nums.length; i++) {
            int prod = 1;
            for (int j = 0; j < nums.length; j++)
                if (j != i) prod *= numscpy[j];
            nums[i] = prod;
        }
        return nums;
    }
}

For each element in the input array nums, we compute the product of all the other elements using our copy (numscpy) and store it in nums. After the nested for loop terminates, we have our answer.

Analysis:

This solution certainly works, but it has a major flaw. Namely, it fails a problem constraint: the algorithm must run in O(n) time. The brute force approach runs in O(n²) time.

This is clear if you realize that for each element in the nums array of length n, we will need to loop through the entire numscpy array which also has length n. We do n operations, n times: n x n = n².

Finding a Clever Approach

We need a clever approach. The key realization for me was realizing that we can use the properties of multiplication to our advantage: we can break down the products and compute them in pieces.

What I mean is, say we have input [1, 2, 3, 4] with the desired output [24, 12, 8, 6]. The element in index 2 is 8, which is the product of 1 x 2 x 4 . But we can also compute this product in parts as (1) x (2 x 4) or in a different order entirely like 4 x 1 x 2. We can compute the same product in any order and any number of pieces — these are the commutative and associative properties of multiplication.

We can use this to our advantage: by computing partial products as we loop over the list and storing them for later use, we do not need a nested for loop.

You may have thought about the fact that our result array can also be made by computing the product of all the elements in nums and then dividing out the value of nums at each index. [24 = 24/1, 12 = 24/2, 8 = 24/3, 6 = 24/4] , in our continued example. This would be a good approach, except that division is not allowed per our problem constraints.

The Clever Approach: Left- and Right-Side Products

The solution I came up with is to compute the products of all the elements to the left and right of each element in the array and save those values in other arrays. Then, to get our final answer, we just multiply the right and left side products together at each index.

For example, say we have input [1, 2, 3, 4] with desired output [24, 12, 8, 6]. The left-side product array is [1, 1, 2, 6] (We put 1 at index 0, as there is no left side to that index). The right-side product array is [24, 12, 4, 1] (similarly, we put 1 at the last index, as there is no right side at the right edge). To compute the result, we just multiply the values of the left and right arrays for each index. For example, output[2] = left[2] * right[2] = 1 * 12 = 12 .

Here is my code:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] leftProds = new int[nums.length];
        int[] rightProds = new int[nums.length];
        int[] result = new int[nums.length];
        Arrays.fill(leftProds, 1);
        Arrays.fill(rightProds, 1);
         
        for (int i = 1; i < nums.length; i++) {
            leftProds[i] = leftProds[i-1] * nums[i-1];
        }
        
        for (int i = nums.length-2; i >= 0; i--) {
            rightProds[i] = rightProds[i+1] * nums[i+1];
        }

        for (int i = 0; i < nums.length; i++) {
            nums[i] = leftProds[i] * rightProds[i];
        }

        return nums;
    }
}

Note that when you build the right-side product array, you should loop from the back of the array.

Analysis:

This approach involves creating two auxiliary arrays for storing the left- and right-side products. To build these arrays, we need to loop over the input array two separate times. We then iterate the length of the array one final time when we compute the result. This means our algorithm has time complexity O(3 x n), and our efficiency depends linearly on the size of our input array (n). This simplifies to O(n), which satisfies the original problem constraint. We did it!