Product of Array Except Self medium

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.

Example 1

Input: nums = [1,2,3,4] Output: [24,12,8,6] Explanation: The product of all elements except 1 is 24. The product of all elements except 2 is 12. The product of all elements except 3 is 8. The product of all elements except 4 is 6.

Example 2

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

Steps

1. Initialization: Create two arrays, prefix and suffix, of the same size as nums. prefix[i] will store the product of all elements to the left of nums[i], and suffix[i] will store the product of all elements to the right of nums[i].

2. Prefix Product Calculation: Iterate through nums from left to right. prefix[0] will be 1 (no elements to the left). For subsequent elements, prefix[i] = prefix[i-1] * nums[i-1].

3. Suffix Product Calculation: Iterate through nums from right to left. suffix[nums.Length - 1] will be 1 (no elements to the right). For subsequent elements, suffix[i] = suffix[i+1] * nums[i+1].

4. Result Calculation: Create the result array result. For each element, result[i] = prefix[i] * suffix[i].

Explanation

The key idea is to calculate the prefix and suffix products separately. This avoids the need for division. By multiplying the prefix product to the left of an element and the suffix product to the right of an element, we get the product of all elements except the current element.

The time complexity is O(n) because we iterate through the array three times (once for prefix, once for suffix, and once for the result). The space complexity is O(n) because we use three arrays of size n. However, it's possible to optimize space by only using a constant number of variables instead of the prefix and suffix arrays.

Code

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        int[] prefix = new int[n];
        int[] suffix = new int[n];

        prefix[0] = 1;
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }

        suffix[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < n; i++) {
            result[i] = prefix[i] * suffix[i];
        }

        return result;
    }
}

Space Optimized version:

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        result[0] = 1;

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

        int suffix = 1;
        // Calculate suffix product and multiply with prefix product
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }

        return result;
    }
}

Complexity

• Time Complexity: O(n) - We iterate through the array a constant number of times.
• Space Complexity: O(1) for the space optimized version. The original version uses O(n) due to the prefix and suffix arrays. The optimized version only uses constant extra space.