algoadvance

Leetcode 238. Product of Array Except Self

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 problem must be solved without using division and in O(n) time complexity.

Clarifying Questions

  1. Constraints on Array Elements:
    • What is the range of values that elements in nums can take?

    Typically, the elements are within the range of -30 to 30, and the length of the array is between 1 to 10^5.

  2. Edge Cases:
    • What should be returned if the input nums contains only one element?

    Since the problem statement implicitly expects length >= 1, this is not a practical concern for the given constraints.

  3. Handling Zeros in the Array:
    • How are zeros handled in nums?

    The method should correctly handle multiple zeros, ensuring the product result respects those zeros.

Strategy

  1. Initialize Arrays for Left and Right Products:
    • Use two additional arrays (leftProducts and rightProducts) to store the cumulative products of all elements to the left and right of each element, respectively.
  2. Calculate Left Products:
    • Traverse the array from left to right to populate leftProducts.
  3. Calculate Right Products:
    • Traverse the array from right to left to populate rightProducts.
  4. Compute Result Array:
    • Combine the leftProducts and rightProducts to produce the result based on the formula: answer[i] = leftProducts[i] * rightProducts[i]

By using this approach, we avoid division and ensure the solution adheres to O(n) time complexity because each traversal is linear with respect to the array length.

Code

Here’s the implementation based on the described strategy:

public class ProductOfArrayExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        
        // Prepare arrays to store products of all elements to the left and right of each element
        int[] leftProducts = new int[n];
        int[] rightProducts = new int[n];
        int[] result = new int[n];
        
        // Initialize the first element of leftProducts array and the last element of rightProducts array
        leftProducts[0] = 1;
        rightProducts[n - 1] = 1;
        
        // Fill leftProducts array with cumulative products from the left
        for (int i = 1; i < n; i++) {
            leftProducts[i] = nums[i - 1] * leftProducts[i - 1];
        }
        
        // Fill rightProducts array with cumulative products from the right
        for (int i = n - 2; i >= 0; i--) {
            rightProducts[i] = nums[i + 1] * rightProducts[i + 1];
        }
        
        // Construct the result array using leftProducts and rightProducts
        for (int i = 0; i < n; i++) {
            result[i] = leftProducts[i] * rightProducts[i];
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        ProductOfArrayExceptSelf solution = new ProductOfArrayExceptSelf();
        int[] nums = {1, 2, 3, 4};
        int[] result = solution.productExceptSelf(nums);
        
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI