7. Product of Array except self

1. Brute Force Solution

Time Complexity: O(n²)
Space Complexity: O(n)

public class ProductExceptSelf {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        // Brute force: multiply all elements except the current one
        for (int i = 0; i < n; i++) {
            result[i] = 1;
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    result[i] *= nums[j];
                }
            }
        }
        return result;
    }
}

Explanation:

• For each element in the array, we multiply all other elements (using a nested loop).
• Time Complexity: O(n²), as the nested loops are used.
• Space Complexity: O(n), due to the extra result array.

---

2. Prefix and Suffix Arrays Solution

Time Complexity: O(n)
Space Complexity: O(n)

public class ProductExceptSelf {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        int[] result = 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 the final result by multiplying prefix and suffix products
        for (int i = 0; i < n; i++) {
            result[i] = prefix[i] * suffix[i];
        }

        return result;
    }
}

Explanation:

• This solution calculates prefix and suffix products separately in two arrays and then multiplies the corresponding values.
• Time Complexity: O(n), as we loop through the array twice.
• Space Complexity: O(n), due to the extra arrays (prefix and suffix).

---

3. Division-Based Solution (with limitation)

Time Complexity: O(n)
Space Complexity: O(1) (excluding output array)

public class ProductExceptSelf {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        // Calculate the total product of all elements
        int totalProduct = 1;
        for (int num : nums) {
            totalProduct *= num;
        }

        // Calculate the result for each element by dividing totalProduct by nums[i]
        for (int i = 0; i < n; i++) {
            result[i] = totalProduct / nums[i];
        }

        return result;
    }
}

Explanation:

• We calculate the total product of all elements and then divide this total product by each element.
• Time Complexity: O(n), as we loop through the array twice.
• Space Complexity: O(1), because we don’t use any extra arrays other than the result.

Limitation:

• This solution fails when the array contains zero, as dividing by zero is undefined.

---

4. Optimal Solution with O(1) Space (No Division)

Time Complexity: O(n)
Space Complexity: O(1) (excluding output array)

public class ProductExceptSelf {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        // Step 1: Compute prefix products in the result array
        result[0] = 1;
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }

        // Step 2: Compute suffix products and multiply directly in the result array
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }

        return result;
    }
}

Explanation:

• In the first pass, we calculate the prefix products and store them in the result array.
• In the second pass, we compute the suffix products using a single variable and multiply them directly into the result array.
• Time Complexity: O(n), as we loop through the array twice.
• Space Complexity: O(1), as we only use a single variable for the suffix product.

---

Correct Order of Optimality (From Brute Force to Most Optimal):

1. Brute Force Solution

• Time Complexity: O(n²)
• Space Complexity: O(n)

1. Prefix and Suffix Arrays Solution

• Time Complexity: O(n)
• Space Complexity: O(n)

1. Division-Based Solution (with limitation for zero elements)

• Time Complexity: O(n)
• Space Complexity: O(1) (excluding output array)

1. Optimal Solution (O(1) Space)

• Time Complexity: O(n)
• Space Complexity: O(1) (excluding output array)

---

Final Conclusion:

The most optimal solution that works in all cases (including when there are zeros) is the Optimal Solution with O(1) Space (using the prefix and suffix product approach). The division-based solution works in O(n) time but should be avoided when there are zeros in the input array.