Ac solution code


  • 0

    The basic idea is as the following,

    Calculate leftProduct and rightProduct for each nums[i]:

    products[i][j]: Product from nums[i] to nums[j] 
    
    leftProduct  = products[0][i-1]
    rightProduct = products[i+1][n-1]
    

    Then, res[i] = products[0][i-1] * products[i+1][n-1] = leftProduct * rightProduct.

    JAVA Code - Runtime=O(n); Space=O(1)

    public int[] productExceptSelf(int[] nums) {
    	if (nums == null) return null;
    	int res[] = new int[nums.length];
    	int leftProduct = 1;
    	for (int i = 0; i < nums.length; i++) {//Calculate leftProduct
    		res[i] = leftProduct;
    		leftProduct *= nums[i];// products[0][i-1] 
    	}
    	
    	int rightProduct = 1;
    	for (int i = nums.length - 1; i >= 0; i--) {// Calculate rightProduct
    		res[i] *= rightProduct;
    		rightProduct *= nums[i];// products[i+1][n-1]
    	}		
    	return res;
    }

Log in to reply
 

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