O(n) time complexity with constant space


  • 1
    S
    public class Solution {
    public int[] productExceptSelf(int[] nums) {
        if(nums == null)
            return nums;
        int[] result = new int[nums.length];
        
        // required for logic. make it zero later on.
        result[nums.length-1] =1;
        for(int i =nums.length -2; i >= 0 ; i--)
        {
            result[i] = nums[i+1]*result[i+1];
        }
        result[nums.length-1] =0;
        
        int curr =nums[0];
        int prev = nums[0];
        nums[0] =1;
        for(int i =1; i < nums.length; i++)
        {
            curr = nums[i];
            nums[i] = nums[i-1]*prev;
            prev = curr;
            result[i] *= nums[i]; 
        }
        result[nums.length-1] = nums[nums.length-1];
        
        
        return result;
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.