Problem Statement (Asked By Uber)

Given a list of integers, return a new list such that each element at index i of the new list is the product of all the elements in the original list except the one at i.

For instance, if the input is [1, 2, 3, 4, 5], the expected output is [120, 60, 40, 30, 24]. If the input is [3, 2, 1], the expected output is [2, 3, 6].

Follow-up: How would you approach this problem if division is not allowed?

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

Problem link: https://leetcode.com/problems/product-of-array-except-self

Solution:

Approach 1: The brute force approach iterates through every pair of numbers in the array. For each index, it calculates the product of all numbers except the current one by using nested loops.

public static int[] bruteForce(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    
    for (int i = 0; i < n; i++) {
        int product = 1;
        for (int j = 0; j < n; j++) {
            if (i != j) {
                product *= nums[j];
            }
        }
        result[i] = product;
    }
    return result;
}

Time Complexity: O(N^2)
Space Complexity: O(1) (excluding result array)

Approach 2: This approach calculates the product of all elements in the array and divides it by the current element to get the result. This assumes there are no zeros in the array.

public static int[] optimalWithDivision(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int totalProduct = 1;
    
    // Calculate the total product of all numbers
    for (int num : nums) {
        totalProduct *= num;
    }
    
    // Fill the result by dividing totalProduct by the current number
    for (int i = 0; i < n; i++) {
        result[i] = totalProduct / nums[i];
    }
    return result;
}

Time Complexity: O(N)
Space Complexity: O(1) (excluding result array)

Approach 3: This approach uses two arrays (prefix and suffix) to store the product of all numbers before and after the current index, respectively, and combines them to get the result. It avoids division.

public static int[] bestWithoutDivision(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int[] prefix = new int[n];
    int[] suffix = new int[n];
    
    // Compute prefix products
    prefix[0] = 1;
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] * nums[i - 1];
    }
    
    // Compute suffix products
    suffix[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--) {
        suffix[i] = suffix[i + 1] * nums[i + 1];
    }
    
    // Compute result by multiplying prefix and suffix
    for (int i = 0; i < n; i++) {
        result[i] = prefix[i] * suffix[i];
    }
    return result;
}

Time Complexity: O(N)
Space Complexity: O(N) (for prefix and suffix arrays)

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.

Hassan Raza