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].
• You must not use division, and the solution must run in O(n) time.

Example:

Input:

nums = [1, 2, 3, 4]

Output:

[24, 12, 8, 6]

Explanation:

• answer[0] = 2 × 3 × 4 = 24
• answer[1] = 1 × 3 × 4 = 12
• answer[2] = 1 × 2 × 4 = 8
• answer[3] = 1 × 2 × 3 = 6

Intuition and Approach (Without Division)

We cannot use division, so we need to calculate the product of elements before and after each index, then multiply them.

Idea:

Let:

• prefix[i] = product of all elements to the left of i
• suffix[i] = product of all elements to the right of i
• Then, result[i] = prefix[i] * suffix[i]

But to save space, we reuse the result array and use just one temp variable for suffix.

Java Solution (Optimal O(n) time, O(1) space)

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

        // Step 1: Build prefix products
        result[0] = 1;  // Nothing on the left of index 0
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }

        // Step 2: Multiply with suffix products from right to left
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] = result[i] * suffix;
            suffix *= nums[i];
        }

        return result;
    }

    // For testing
    public static void main(String[] args) {
        ProductOfArrayExceptSelf obj = new ProductOfArrayExceptSelf();
        int[] nums = {1, 2, 3, 4};
        int[] output = obj.productExceptSelf(nums);

        for (int val : output) {
            System.out.print(val + " ");
        }
    }
}

Dry Run (Step-by-step)

Let nums = [1, 2, 3, 4]

Step 1: Compute Prefix Products (Left-to-Right)

i	result[i]
0	1
1	1 × nums[0] = 1
2	1 × nums[1] = 2
3	2 × nums[2] = 6

Now result = [1, 1, 2, 6]

Step 2: Multiply by Suffix Products (Right-to-Left)

Initialize suffix = 1

i	result[i] × suffix	suffix update
3	6 × 1 = 6	suffix = 1 × 4 = 4
2	2 × 4 = 8	suffix = 4 × 3 = 12
1	1 × 12 = 12	suffix = 12 × 2 = 24
0	1 × 24 = 24	suffix = 24 × 1 = 24

Final result = [24, 12, 8, 6]