Java O(n) solution without extra space. 2 Traversals through array


  • 0
    M

    The idea here is to maintain the multiplication while going forward and backward. At any given i, result will be the product of elements before it in forward traversal and product of elements after it in backward traversal. We use output array itself for maintaining products in forward traversal and update it while backward traversal.

    public int[] productExceptSelf(int[] nums) {
            int[] output = new int[nums.length];
            int fp = 1;
            output[0] = fp;
            for(int i=1; i<nums.length; i++){
                fp *= nums[i-1];
                output[i] = fp;
            }
            
            fp = 1;
            for(int i=nums.length-2; i>=0; i--){
                fp *= nums[i+1];
                output[i] *= fp;
            }
            
            return output;
        }
    

Log in to reply
 

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