0238 - Product of Sorted Array Except Self

0238 - Product of Sorted Array Except Self

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.

Examples

Input: nums = [1,2,3,4] Output: [24,12,8,6]

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

Constraints

2 <= nums.length <= 105 -30 <= nums[i] <= 30 The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Java Solution

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        result[0] = 1;
        
        for(int i = 1; i < nums.length; i++) {
            result[i] = nums[i-1] * result[i-1];
        }
        
        int temp = 1;
        for(int i = nums.length-1; i >= 0; i--) {
            result[i] = result[i] * temp;
            temp = temp * nums[i];
        }
        
        return result;
    }
}