Super easy (Java) solution in O(N) time and O(1) space


  • 36
    K

    You traverse twice, applying the appropriate multiplier.

    public int[] productExceptSelf(int[] nums) {
    
        int len = nums.length;
        int [] output = new int[len];
        
        int leftMult = 1, rightMult = 1;
        
        for(int i = len-1; i >= 0; i--){
            output[i] = rightMult;
            rightMult *= nums[i];
        }
        for(int j = 0; j < len; j++){
            output[j] *= leftMult;
            leftMult *= nums[j];
           
        }
        
        return output; 
    
    }

  • 0
    W

    bravo! It really helps!


  • 0
    S

    Is this really O(1) space?? Because we create a new array and the length of new array is the length of nums array, so isn't this O(n) space?


  • 1
    I

    It is written in the description: (Note: The output array does not count as extra space for the purpose of space complexity analysis.). So yes, it is indeed O(1) extra space.


Log in to reply
 

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