Product of Array Except self

238.Product of Array Except Self

Array

Prefix Products

Problem Statement:

Given an 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 algorithm must run in O(n) time and without using division.

Example:

Input:

nums = [1,2,3,4]

→

Output:

[24,12,8,6]

Java Solution:

public int[] productExceptSelf(int[] nums) {
    int[] res = new int[nums.length];
    Arrays.fill(res, 1);  // Initialize result array with 1s

    int left = 1, right = 1, l = nums.length;  // Track products from both ends

    for (int i = 0; i < nums.length; i++) {
        res[i] *= left;              // Multiply by left products
        left *= nums[i];             // Update left product

        res[l - i - 1] *= right;     // Multiply by right products
        right *= nums[l - i - 1];    // Update right product
    }

    return res;
}

Python Solution:

def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    answer = [1] * n
    
    left = right = 1
    for i in range(n):
        answer[i] *= left
        left *= nums[i]
        
        answer[n-1-i] *= right
        right *= nums[n-1-i]
        
    return answer

C++ Solution:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> answer(n, 1);
        
        int left = 1, right = 1;
        for(int i = 0; i < n; i++) {
            answer[i] *= left;
            left *= nums[i];
            
            answer[n-1-i] *= right;
            right *= nums[n-1-i];
        }
        
        return answer;
    }
};

Explanation:

The solution uses two running products (left and right) to compute products of all elements to the left and right of each position simultaneously. This achieves O(1) space complexity by updating the result array in-place.

Complexity:

Time: O(n) | Space: O(1) not counting output array