I have been trying out this problem on leetcode. 238.Product of array except self
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1 :
Input: nums = [1,2,3,4] Output: [24,12,8,6]Example 2:
Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
This was my solution to the above-given problem.
public int[] productExceptSelf(int[] nums) {
int answer[]=new int[nums.length];
for(int i=0;i<nums.length;i++){
int prod=1;
for(int j=0;j<nums.length;j++){
if(j!=i)
prod=prod*nums[j];
}
answer[i]=prod;
}
return answer;
}
This is passing 19/20 test cases. There is one test case that is not working and I'm getting an error "Time limit exceeded."
Test case which is failing is given below:
Input: [-1,-1,-1,-1,..............]; Output: Time limit exceeded.
If someone can help me with what edition I have to do to my code?
4 Answers
i too do leetcode, it's giving you TLE, because it's not the solution they are expecting. it's correct but it will O(N*N) operations to compute, there is much better solution with O(N),
public int[] productExceptSelf(int[] nums) {
int output[] = new int[ nums.length];
output[0] = 1;
// left prefix product
for(int i=1;i<nums.length;i++){
output[i] = output[i-1] * nums[i-1];
}
int product = 1;
for(int i=nums.length-1;i>=0;i--){
output[i] = output[i] * product;
product*= nums[i];
}
return output;
}
The above problem is giving TLE (Time Limit Exceeds) because the above problem is solved in O(N^2) time complexity. As mentioned in the Question, Algorithm should run in O(N) time and without using the division operator.
Approach-1
public int[] productExceptSelf(int[] nums) {
int[] leftProduct = new int[nums.length];
int[] rightProduct = new int[nums.length];
/**
calculate the left Prefix and right Suffix Product.
*/
for (int i=0,j= nums.length-1; i < nums.length; i++, j--) {
if (i == 0) {
leftProduct[i] = nums[i];
rightProduct[j] = nums[j];
}else {
leftProduct[i] = leftProduct[i-1] * nums[i];
rightProduct[j] = rightProduct[j+1] * nums[j];
}
}
for (int i=0; i < nums.length; i++) {
if (i == 0) {
nums[i] = rightProduct[1];
}else if (i == (nums.length - 1)) {
nums[i] = leftProduct[i-1];
}else {
nums[i] = leftProduct[i-1] * rightProduct[i+1];
}
}
return nums;
}
Time Complexity: O(N), Space Complexity: O(N)
This can also be solved in O(1) space (as it's mentioned Output array does not count as extra space.)
Hint: use the output array to store the left Prefix Product & traverse the array from the right side.
This solution also gives O(N) but use only 1 cycle.
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
res[0] = 1;
res[nums.length-1] = 1;
int n = 1;
int k = nums.length-2;
int fromLeft = 1;
int fromRight = 1;
while(n < nums.length) {
fromLeft = nums[n-1] * fromLeft;
fromRight = nums[k+1] * fromRight;
if (n < k) {
res[n] = fromLeft;
res[k] = fromRight;
} else {
if (n == k) {
res[n] = fromLeft * fromRight;
} else {
res[n] = fromLeft * res[n];
res[k] = fromRight * res[k];
}
}
n++;
k--;
}
return res;
}
class Solution {
public int[] productExceptSelf(int[] arr) {
int[] res = new int[arr.length];
for(int i =0, temp =1; i < arr.length;i++){ // first iteration to make res making temp inc
res[i] = temp;
temp *= arr[i];
}
for(int i = arr.length -1 , temp =1;i>=0;i--){
res[i] *= temp;
temp *= arr[i];
}
return res;
}
}
**Time Complexity O(N) Space Complexity O(N)**
