Data Structures & Algorithms

Leetcode Problem Product of Array Except Self (Java) With Video

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,5,6,4]
Output: [120,24,20,30]

The below solution takes O(N) time complexity and O(N) space complexity

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        int[] result= new int[nums.length];
        
        //fill the left array
        int p =1;
        for(int i =0;i<nums.length;i++){
            left[i] = p;
            p = p* nums[i];
        }
        
        //fill right array from the end
        int r =1;
        
        for(int i= nums.length-1;i>=0;i--){
            right[i] = r;
            r= r* nums[i];
        }
        
        for(int i=0;i<nums.length;i++){
            result[i] = left[i] * right[i];
        }
        
        return result;
        
        
    }
}

Here is the video explanation.

rajendra

Recent Posts

Largest Unique Number Java Solution

Question : Given an array of integers A, return the largest integer that only occurs once.…

10 months ago

Jump Search Algorithm In Java

Jump search algorithm is a pretty new algorithm to search for an element in a…

1 year ago

Knuth Morris Pratt Pattern Search Algorithm

What is Knuth Morris Pratt or KMP algorithm ? KMP is an algorithm which is…

1 year ago

Binary Search Algorithm In Java

Binary Search is a Logarithmic search which finds the target element in a sorted array…

1 year ago

Leetcode Integer to Roman Java Solution

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X…

2 years ago

Leetcode Container With Most Water Java Solution

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such…

2 years ago

This website uses cookies.