Product of Array Except Self

Given an array ofnintegers wheren> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[i].

Solve it without division and in O(n).

For example, given[1,2,3,4], return[24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output arraydoes notcount as extra space for the purpose of space complexity analysis.)

Brainstorm

Approach #1: Use Two Arrays to Track Products

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> output(n);
    int fromBegin = 1, fromEnd = 1;

    for (int i = 0; i < n; i++) {
        output[i] = fromBegin * fromEnd;
        fromBegin *= nums[i-1];
        fromEnd *= nums[n-i];
    }
    return output;
}

Time complexity: $$O(n)$$

We perform our calculations in one loop, and each element will only be considered once as a result of our marking of visited integers as negative.

Space complexity: $$O(1)$$