3ms Java solution , with 3 for loop. easy to understand


  • 0
    V
    //solution0: total time + divsion 
    //solution1: O(n^2) for-for scan
    //solution2: O(n) two arrays , scan forward, and scan back
    //solution3: solution 2 space improve
    /*
    1     2    3    4     5
    1     2    6    24   120   (put in result array) -> 
    120  120   60   20    5   (change original array) <-
    
    120  1*60  2*20 6*5  24    (process to result array)    left*right
    
    */
    public class Solution {
        public int[] productExceptSelf(int[] nums) {
            int[] result = new int[nums.length];
    
            // (put in result array) -> 
            for(int i = 0; i < nums.length; i++) { 
                 int left = i-1 < 0? 1:result[i-1];
                 result[i] = left * nums[i];
            }
            //(change original array) <-
            for(int i = nums.length - 1; i >= 0; i--) { 
                int right = i+1 > nums.length - 1? 1:nums[i+1];
                nums[i] = right *nums[i]; 
            }
            //(process to result array)
            int left = 1;
            for(int i = 0; i < result.length; i++) {
                int right = i+1 > result.length - 1? 1:nums[i+1];
                int temp = result[i];
                result[i] = left * right;
                left = temp;
            }
    
            return result;
        }
    }
    

    also, after this method, you can convert to 2-for


Log in to reply
 

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