Leetcode 238: Product Of Array Except Self

This problem looks simple to solve in linear time and space. This problem builds on some of the fundamental concepts of arrays.

1. Array traversals.
2. Prefix and Suffix sum.

Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe, and many more top tech companies.

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

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.

Test case#1:

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

Test case#2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Understanding the problem

This problem looks simpler to solve in linear time and space, but it is tricky when writing the pseudocode or actual code implementation.

Illustration

Let us see what the results that are expected from a simple array containing 4 elements:

input = {1, 2, 3, 4}

So, the value at each index is the product of all the other elements in the array except the value itself. The following figure illustrates this.

Based on the above figure, we can come up with a formula. For any given index i, we can find the value using the product of the elements from o to (i - 1) plus product of elements from (i + 1) to (N - 1). This is illustrated in the following figure:

Thought process

Before writing pseudo code, come up with questions and ask the interviewer.

1. Should I be worried about duplicates?
2. What if the array is empty or has a single element? What are the expected results?
3. Should I consider/ignore 0 value in any of the indexes in the array? because all other values get 0 except the index containing 0.
4. What are the corner/edge cases for this problem?

Once you and the interviewer have discussed the above questions, devise various approaches to solving the problem.

1. Naive approach/brute-force.
2. Product of all elements.
3. Left and Right products.
4. Prefix and suffix sums.

Approach 1: Naive/Brute-force

Intuition

To employ the brute force approach, we must execute two for-loops. When the outer loop index matches the inner loop index value, we should skip the product; otherwise, we proceed with the product.

Algorithm

1. Initialize Variables:
   • N = nums.length (length of the input array).
   • result = new int[N] (array to store the results).
2. Outer Loop (Iterate through each element in nums):
   • For i = 0 to N-1:Initialize currentProduct = 1.
3. Inner Loop (Calculate product for current element), for j = 0 to N-1:
   • If i == j, skip the current iteration using continue.
   • Multiply currentProduct by nums[j].
   • Assign currentProduct to result[i].
4. Return result.

Code

// brute force
static int[] bruteForce(int[] nums) {
    int N = nums.length;
    int[] result = new int[N];

    for (int i = 0; i < N; i++) {
        int currentProduct = 1;
        for (int j = 0; j < N; j++) {
            if (i == j) {
                continue;
            }
            currentProduct *= nums[j];
        }
        result[i] = currentProduct;
    }
    return result;
}

Complexity analysis

1. Time complexity: O(n^2), for iterating the array twice in outer and inner loops.
2. Space complexity: O(n), for the auxiliary space (result[] array) we used.

Approach 2: Product of array ❌

One way most developers think is to run a product sum of all elements, divide the product sum by each array value, and return the result.

Pseudocode

// O(n) time and O(1) space
p = 1
for i -> 0 to A[i]
  p * = A[i]
for i -> 0 to (N - 1)
  A[i] = p/A[i] // if A[i] == 0 🤔 BAM error‼️  

Code

// code implementation
static int[] productSum(int[] nums) {
    int product_sum = 1;
    for(int num: nums) {
        product_sum *= num;
    }

    for(int i = 0; i < nums.length; i++) {
        nums[i] = product_sum/nums[i];
    }
    return nums;
}

What if one of the array elements contain 0? 🤔

The value at all the indexes except the index containing 0 will definitely be infinity. Also, the code throws java.lang.ArithmeticException.

Exception in thread "main" java.lang.ArithmeticException: / by zero
    at dev.ggorantala.ds.arrays.ProductOfArrayItself.productSum(ProductOfArrayItself.java:24)
    at dev.ggorantala.ds.arrays.ProductOfArrayItself.main(ProductOfArrayItself.java:14)

Approach 3: Find Prefix and Suffix product

Learn more about prefix and suffix sum in the Arrays Mastery Course on my website https://ggorantala.dev

Intuition & formulae's

Prefix and Suffix are calculated before writing an algorithm for the result. Prefix and Suffix sum formulae are given below:

Algorithm Steps

1. Create an array result of the same length as nums to store the final results.
2. Create two additional arrays prefix_sum and suffix_sum of the same length as nums.
3. Calculate Prefix Products:
   • Set the first element of prefix_sum to the first element of nums.
   • Iterate through the input array nums starting from the second element (index 1). For each index i, set prefix_sum[i] to the product of prefix_sum[i-1] and nums[i].
4. Calculate Suffix Products:
   • Set the last element of suffix_sum to the last element of nums.
   • Iterate through the input array nums starting from the second-to-last element (index nums.length - 2) to the first element. For each index i, set suffix_sum[i] to the product of suffix_sum[i+1] and nums[i].
5. Calculate the result: Iterate through the input array nums.
   • For the first element (i == 0), set result[i] to suffix_sum[i + 1].
   • For the last element (i == nums.length - 1), set result[i] to prefix_sum[i - 1].
   • For all other elements, set result[i] to the product of prefix_sum[i - 1] and suffix_sum[i + 1].
6. Return the result array containing the product of all elements except the current element for each index.

Pseudocode

Function usingPrefixSuffix(nums):
    N = length of nums
    result = new array of length N
    prefix_sum = new array of length N
    suffix_sum = new array of length N

    // Calculate prefix products
    prefix_sum[0] = nums[0]
    For i from 1 to N-1:
        prefix_sum[i] = prefix_sum[i-1] * nums[i]

    // Calculate suffix products
    suffix_sum[N-1] = nums[N-1]
    For i from N-2 to 0:
        suffix_sum[i] = suffix_sum[i+1] * nums[i]

    // Calculate result array
    For i from 0 to N-1:
        If i == 0:
            result[i] = suffix_sum[i+1]
        Else If i == N-1:
            result[i] = prefix_sum[i-1]
        Else:
            result[i] = prefix_sum[i-1] * suffix_sum[i+1]

    Return result

Code

// using prefix and suffix arrays
private static int[] usingPrefixSuffix(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];
    int[] suffix_sum = new int[nums.length];

    // prefix sum calculation
    prefix_sum[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i];
    }

    // suffix sum calculation
    suffix_sum[nums.length - 1] = nums[nums.length - 1];
    for (int i = nums.length - 2; i >= 0; i--) {
        suffix_sum[i] = suffix_sum[i + 1] * nums[i];
    }

    for (int i = 0; i < nums.length; i++) {
        if (i == 0) { // when variable `i` is at 0th index
            result[i] = suffix_sum[i + 1];
        } else if (i == nums.length - 1) { // when variable `i` is at last index 
            result[i] = prefix_sum[i - 1];
        } else { // for all other indexes
            result[i] = prefix_sum[i - 1] * suffix_sum[i + 1];
        }
    }
    return result;
}

Complexity analysis

1. Time complexity: The time complexity of the given code is O(n), where n is the length of the input array nums. This is because:
   • Calculating the prefix_sum products take O(n) time.
   • Calculating the suffix_sum products take O(n) time.
   • Constructing the result array takes O(n) time.

Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n) = 3O(n), which is O(n).

1. Space complexity: The space complexity of the given code is O(n). This is because:
   • The prefix_sum array requires O(n) space.
   • The suffix_sum array requires O(n) space.
   • Theresult array requires O(n) space. All three arrays are of length n, so the total space complexity is O(n) + O(n) + O(n) = 3O(n), which is O(n).

Optimization 🤩

For the suffix array calculation, we override the input nums array instead of creating one.

private static int[] usingPrefixSuffixOptimization(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];

    // prefix sum calculation
    prefix_sum[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i];
    }

    // suffix sum calculation, in-place - `nums` array override
    for (int i = nums.length - 2; i >= 0; i--) {
        nums[i] = nums[i + 1] * nums[i];
    }

    for (int i = 0; i < nums.length; i++) {
        if (i == 0) { // when variable `i` is at 0th index
            result[i] = nums[i + 1];
        } else if (i == nums.length - 1) { // when variable `i` is at last index
            result[i] = prefix_sum[i - 1];
        } else { // for all other indexes
            result[i] = prefix_sum[i - 1] * nums[i + 1];
        }
    }
    return result;
}

Hence, we reduced the space of O(n). Time and space are not reduced, but we did a small optimization here.

Approach 4: Using Prefix and Suffix product knowledge 🧐

Intuition

This is a rather easy approach when we use the knowledge of prefix and suffix arrays.

For every given index i, we will calculate the product of all the numbers to the left and then multiply it by the product of all the numbers to the right. This will give us the product of all the numbers except the one at the given index i. Let's look at a formal algorithm that describes this idea more clearly.

Algorithm steps

1. Create an array result of the same length as nums to store the final results.
2. Create two additional arrays prefix_sum and suffix_sum of the same length as nums.
3. Calculate Prefix Products:
   • Set the first element of prefix_sum to 1.
   • Iterate through the input array nums starting from the second element (index 1). For each index i, set prefix_sum[i] to the product of prefix_sum[i - 1] and nums[i - 1].
4. Calculate Suffix Products:
   • Set the last element of suffix_sum to 1.
   • Iterate through the input array nums starting from the second-to-last element (index nums.length - 2) to the first element.
   • For each index i, set suffix_sum[i] to the product of suffix_sum[i + 1] and nums[i + 1].
5. Iterate through the input array nums.
   • For each index i, set result[i] to the product of prefix_sum[i] and suffix_sum[i].
6. Return the result array containing the product of all elements except the current element for each index.

Pseudocode

Function prefixSuffix1(nums):
    N = length of nums
    result = new array of length N
    prefix_sum = new array of length N
    suffix_sum = new array of length N

    // Calculate prefix products
    prefix_sum[0] = 1
    For i from 1 to N-1:
        prefix_sum[i] = prefix_sum[i-1] * nums[i-1]

    // Calculate suffix products
    suffix_sum[N-1] = 1
    For i from N-2 to 0:
        suffix_sum[i] = suffix_sum[i+1] * nums[i+1]

    // Calculate result array
    For i from 0 to N-1:
        result[i] = prefix_sum[i] * suffix_sum[i]

    Return result

Code

private static int[] prefixSuffixProducts(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];
    int[] suffix_sum = new int[nums.length];

    prefix_sum[0] = 1;
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i - 1];
    }

    suffix_sum[nums.length - 1] = 1;
    for (int i = nums.length - 2; i >= 0; i--) {
        suffix_sum[i] = suffix_sum[i + 1] * nums[i + 1];
    }

    for (int i = 0; i < nums.length; i++) {
        result[i] = prefix_sum[i] * suffix_sum[i];
    }

    return result;
}

Complexity analysis

1. Time complexity: The time complexity of the given code is O(n), where n is the length of the input array nums. This is because:
   • Calculating the prefix_sum products take O(n) time.
   • Calculating the suffix_sum products take O(n) time.
   • Constructing the result array takes O(n) time.

Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n) = 3O(n), which is O(n).

1. Space complexity: The space complexity of the given code is O(n). This is because:
   • The prefix_sum array requires O(n) space.
   • The suffix_sum array requires O(n) space.
   • The result array requires O(n) space.

All three arrays are of length n, so the total space complexity is O(n) + O(n) + O(n) = 3O(n), which is O(n).

Approach 5: Carry Forward technique

Intuition

The carry forward technique optimizes us to solve the problem with a more efficient space complexity. Instead of using two separate arrays for prefix and suffix products, we can use the result array itself to store intermediate results and use a single pass for each direction.

Here’s how you can implement the solution using the carry-forward technique:

Algorithm Steps for Carry Forward Technique

1. Initialize Result Array:
   • Create an array result of the same length as nums to store the final results.
2. Calculate Prefix Products:
   • Initialize a variable prefixProduct to 1.
   • Iterate through the input array nums from left to right. For each index i, set result[i] to the value of prefixProduct. Update prefixProduct by multiplying it with nums[i].
3. Calculate Suffix Products and Final Result:
   • Initialize a variable suffixProduct to 1.
   • Iterate through the input array nums from right to left. For each index i, update result[i] by multiplying it with suffixProduct. Update suffixProduct by multiplying it with nums[i].
4. Return the result array containing the product of all elements except the current element for each index.

Pseudocode

prefix products
    prefixProduct = 1
    For i from 0 to N-1:
        result[i] = prefixProduct
        prefixProduct = prefixProduct * nums[i]

    // Calculate suffix products and finalize result
    suffixProduct = 1
    For i from N-1 to 0:
        result[i] = result[i] * suffixProduct
        suffixProduct = suffixProduct * nums[i]

    Return result

Code

// carry forward technique
private static int[] carryForward(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];

    // Calculate prefix products
    int prefixProduct = 1;
    for (int i = 0; i < n; i++) {
        result[i] = prefixProduct;
        prefixProduct *= nums[i];
    }

    // Calculate suffix products and finalize the result
    int suffixProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= suffixProduct;
        suffixProduct *= nums[i];
    }
    return result;
}

Explanation

1. Prefix Products Calculation:
   • We initialize prefixProduct to 1 and update each element of result with the current value of prefixProduct.
   • Update prefixProduct by multiplying it with nums[i].
2. Suffix Products Calculation:
   • We initialize suffixProduct to 1 and update each element of result(which already contains the prefix product) by multiplying it with suffixProduct.
   • Update suffixProduct by multiplying it with nums[i].

Complexity analysis

1. Time Complexity: O(n) time
2. Space Complexity: O(n) (for the result array)

This approach uses only a single extra array (result) and two variables (prefixProduct and suffixProduct), achieving efficient space utilization while maintaining O(n) time complexity.

Comments

[Martin Baun]

Great resource! Foundational problems are solved using techniques that are used in many other problems. Once you learn these techniques, then you can solve a lot of other interview problems on your own.

[Bhaskar L]

None of the online tutorials or websites teach prefix-suffix sums. Thank you sir for writing the article.