238. Product of Array Except Self — LeetCode Medium Problem — Full Solution and approach explained
In this blog, I would be discussing this question with different approaches which you would come up in an interview in the manner of increasing difficulty. I will be writing this post in such a way as if I were the person being interviewed. So, enjoy 😊
Problem Statement:
Interviewer : 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]
Brute Force Approach
Interviewee: Absolutely, let’s start with the fundamentals. The brute force approach involves looping through the array, excluding the current element, and multiplying the rest. While simple, its time complexity is O(n²).
// Java code for brute force approach
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int ans[] = new int[n];
for(int i = 0; i < n; i++) {
int pro = 1;
for(int j = 0; j < n; j++) {
if(i == j) continue;
pro *= nums[j];
}
ans[i] = pro;
}
return ans;
}
}Interviewer: Indeed, an essential starting point. Now, let’s optimize.
Dividing the Product of Array with the Number
Interviewee: Right, here we calculate the product of all elements and divide by each element to obtain the desired result. However, we face challenges when encountering zeroes in the array due to division by zero.
// Java code for dividing the product of array with the number
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int countZeroes = 0;
int indexZero = -1;
int productWithoutZero = 1;
for(int i = 0 ; i < n ; i++) {
if(nums[i] == 0) {
countZeroes++;
indexZero = i;
}
else productWithoutZero *= nums[i];
}
int [] output = new int [n];
if(countZeroes == 0) {
for(int i = 0 ; i < n ; i++) {
output[i] = productWithoutZero / nums[i];
}
}
else if(countZeroes == 1) {
output[indexZero] = productWithoutZero;
}
return output;
}
}LOGIC — -
maintain the count of zeroes in the array.
1.) If count of zeroes is greater than 1 so the array will be empty
2.) If the count of zeroes is 0 then we need to just divide the product of array with every element
3.) Lastly if the count of zeroes if 1, then we need to find the index of zero and product of array without zero and then just place the product at index of zero and we are done
Note — What if there is more than one zero??
ans: read point no 1
Finding Prefix Product and Suffix Product
Interviewee: Similar to finding prefix sums, we compute prefix and suffix product arrays. Then, the final answer at each index is the product of its prefix and suffix, excluding the element itself. This approach offers a time complexity of O(n) but uses additional space.
class Solution {
public int[] productExceptSelf(int[] nums) {
int prefix[] = new int[nums.length];
prefix[0]=1;
for(int i=1;i<nums.length;i++){
prefix[i]=prefix[i-1]*nums[i-1];
}
int suffix[] = new int[nums.length];
suffix[nums.length-1]=1;
for(int i=nums.length-2;i>=0;i--){
suffix[i]=suffix[i+1]*nums[i+1];
}
int ans[] = new int[nums.length];
for(int i=0;i<nums.length;i++) ans[i]=prefix[i]*suffix[i];
return ans;
}
}LOGIC — -
For any nums[i], calculate its left product and calculate its right product, without including nums[i] as prefix and suffix.
Then multiply these left and right product, This will give product of array excluding nums[i].
Interviewer: Excellent! Now, let’s optimize space.
Directly Store the Product of Prefix and Suffix into the Final Answer Array
Interviewee: Precisely, we can perform the same calculations directly onto our final answer array, minimizing auxiliary space to O(1).
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int ans[] = new int[n];
Arrays.fill(ans, 1);
for(int i = 1; i < n; i++) {
ans[i] = ans[i-1] * nums[i-1];
}
int curr = 1;
for(int i = n - 1; i >= 0; i--) {
ans[i] *= curr;
curr *= nums[i];
}
return ans;
}
}Interviewer: Well done! These approaches showcase your problem-solving skills impressively. Thank you for sharing your insights.
Interviewee: Thank you for the opportunity. It’s been a pleasure discussing these strategies with you.
DO THIS OR I WILL BE SAD 🥺
Do ask in comments if you face any problem in the above solutions. If the prefix and suffix part is not clear to you, my suggestion is to revise or learn these topics thoroughly.
Follow me on medium to get notification for all my amazing LeetCode editorials.
Find my other leetcode solution on my github — https://github.com/Harshit-Raj-14/My-Leetcode-Solutions . (Follow me and star mark the repo)
Best of Luck!
Hope you enjoyed going through the article. You can follow me to get the latest update when I upload more such amazing article.
If you got to learn something valuable from this article and clap and follow me if you found it helpful.
You can encourage me to write more such articles on: https://ko-fi.com/medusaverse
Follow me for more such awesome articles that can help you in your interview preparation and studies and learn coding.
Who am I?
Just someone who is enthusiastic to write what he likes. Tech blogs, tutorials, Coding Question solutions Editorials, Interview Tips and many more stuff that you are bound to like.
Also, I write articles for freelancing so you can contact me through the below link.
If you liked this article, do support me in this endeavor by following me on medium and get latest updates to my amazing and helpful articles.
You can encourage me to write more on: https://ko-fi.com/medusaverse
I will be happy to Connect with you : https://linktr.ee/harshit_raj_14
“This Method Quickly Cured My Procrastination” — The Scientific Trick
Checkout the article now — Click here
