Simple Java O(n) time and O(1) space solution with explanation


  • 1
    S
    // The algorithm for the problem is as follows.    
    // Create the answer array. 
    // Traverse the actual array from right to left store the left side number cumulative
    // product into answer array.
    // Traverse the actual array from left to right multiply answer array with left side 
    // number cumulative  products.
    // code passing all the test cases with O(n) time and O(1) space complexity (excluding answer array)
    // is as follows
    
    public int[] productExceptSelf(int[] nums) {
                int[] answer = new int[nums.length];
                int leftProd = 1;
                answer[nums.length-1] = 1;
                for(int i = nums.length-2;i>=0;i--)
                    answer[i] = answer[i+1]*nums[i+1];
                leftProd = leftProd*nums[0];
                for(int i=1;i<=nums.length-1;i++){
                    answer[i] = answer[i]*leftProd;
                    leftProd = leftProd*nums[i];
                }
                return answer;
            }

Log in to reply
 

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