Hello readers, let’s solve a LeetCode problem today.
In this blog, let’s solve the problem Product of Array Except Self which is one of the Blind 75 List of LeetCode Problems.
This is a LeetCode Medium problem with multiple potential solutions, which we will go through in this blog.
Understand the Problem
The Objective of the problem is to calculate the product of all elements in an input array, except for the element at each index. The problem also mentions writing an algorithm that runs in O(n) time and without using the division operation.
Understand the Testcases
To test the solution, we can consider the following cases:
- Input: [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation: The product of all elements except the one at index 0 is 2 * 3 * 4 = 24. The product of all elements except the one at index 1 is 1 * 3 * 4 = 12. Similarly, for index 2, the product is 1 * 2 * 4 = 8, and for index 3, the product is 1 * 2 * 3 = 6. - Input: [4, 2, 1, 5, 3]
Output: [30, 60, 120, 24, 40]
Explanation: The product of all elements except the one at index 0 is 2 * 1 * 5 * 3 = 30. The product of all elements except the one at index 1 is 4 * 1 * 5 * 3 = 60. Similarly, for index 2, the product is 4 * 2 * 5 * 3 = 120, for index 3, the product is 4 * 2 * 1 * 3 = 24, and for index 4, the product is 4 * 2 * 1 * 5 = 40. - Input: [1, 1, 1, 1, 1]
Output: [1, 1, 1, 1, 1]
Explanation: Since all elements are the same, the product of all elements except the one at each index will be the same element itself. - Input: [0, 0, 0, 0]
Output: [0, 0, 0, 0]
Explanation: Since there are zero values in the input array, the product of all elements except the one at each index will be zero. - Input: [2, 3, 0, 4]
Output: [0, 0, 24, 0]
Explanation: The product of all elements except the one at index 0 is 3 * 0 * 4 = 0. The product of all elements except the one at index 1 is 2 * 0 * 4 = 0. For index 2, the product is 2 * 3 * 4 = 24, and for index 3, the product is 2 * 3 * 0 = 0.
Brute Force Approach
The brute force approach will be to calculate the product of all values in the array except the current value using two nested iterations.
Key Points:
- For each value, calculate the product of all other values by iterating through the array twice.
- This approach uses two nested loops to multiply each element with all other elements, excluding itself.
- However, this method is inefficient and may lead to a Time Limit Exceeded (TLE) error for larger test cases.
class Solution {
public int[] productExceptSelf(int[] nums) {
int size = nums.length;
int[] answer = new int[size];
for(int i=0; i<size; i++) {
answer[i] = 1;
}
for(int i=0; i<size; i++) {
for(int j=0; j<size; j++) {
if(i==j) continue;
answer[i] *= nums[j];
}
}
return answer;
}
}
Time Complexity: O(N²)
- The time complexity of the brute force approach is quadratic, as it involves nested loops that iterate through the array.
Space Complexity: O(1)
- The brute force approach doesn’t require any additional space other than the answer array, so the space complexity is constant.
Better Approach
class Solution {
public int[] productExceptSelf(int[] nums) {
int size = nums.length;
int[] answer = new int[size];
int[] prefix = new int[size];
int[] suffix = new int[size];
int temp = 1;
for(int i=0; i<size; i++) {
prefix[i] = temp;
temp *= nums[i];
}
temp = 1;
for(int j=size-1; j>=0; j--) {
suffix[j] = temp;
temp *= nums[j];
}
for(int i=0; i<size; i++) {
answer[i] = prefix[i] * suffix[i];
}
return answer;
}
}
Key Points:
- The better approach uses separate iterations to calculate prefix and suffix values for each element.
- In this approach, we calculate the prefix products while traversing the array from left to right and storing them in the prefix array.
- Then, we calculate the suffix products while traversing the array from right to left and storing them in the suffix array.
- Finally, we multiply the corresponding prefix and suffix values to get the final products.
Time Complexity: O(N)
- The better approach performs two linear passes through the array, resulting in a linear time complexity.
Space Complexity: O(N)
- The better approach requires additional space to store the prefix and suffix arrays, resulting in linear space complexity.
Optimal Approach
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] answer = new int[nums.length];
int prefix = 1;
for(int i=0; i<nums.length; i++) {
answer[i] = prefix;
prefix *= nums[i];
}
int suffix = 1;
for(int j=nums.length-1; j>=0; j--) {
answer[j] *= suffix;
suffix *= nums[j];
}
return answer;
}
}
Key Points:
- The optimal approach further improves efficiency by using the output array to store the prefix products.
- In this approach, we calculate the prefix products while traversing the array from left to right.
- Then, we calculate the suffix products while traversing the array from right to left.
- Finally, we multiply the suffix product with the corresponding prefix product to obtain the final answer.
Time Complexity: O(N)
- The optimal approach also performs two linear passes through the array, resulting in a linear time complexity.
Space Complexity: O(1)
- The optimal approach doesn’t require any additional space other than the output array, so the space complexity is constant.
Conclusion
- The brute force solution has a time complexity of O(N²) but no extra memory usage.
- Using two extra arrays improves the time complexity to O(N) but also requires extra memory with the complexity of O(N).
- Using the linear traversals and answer array offers the best time complexity of O(N) but doesn’t require any additional space other than the output array, so the space complexity is constant, O(1).
NeetCode Solution Video
Recommended Resources to Learn Data Structures and Algorithms
Basics of DS Algo Blogs:
Recommended YouTubers for LeetCode Problems:
1. NeetCode
Free Resources for Learning Data Structures and Algorithms:
Recommended Courses for Learning Data Structures and Algorithms:
- NeetCode Courses
- ZTM: Mastering the Coding Interview (Big Tech): Available on Udemy and ZTM Academy
- ZTM: Mastering the Coding Interview: Available on Udemy and ZTM Academy
- Data Structures & Algorithms, Level-up for Coding Interviews Course
- Become a Job Ready Programmer (Java)
- Striver’s A2Z (Free) Course
Top Coursera Courses for Learning Data Structures and Algorithms:
- Coding Interview Preparation (Meta)
- Algorithms Course Part I (Princeton University)
- Algorithms Course Part II (Princeton University)
- Data Structures and Algorithms Specialization (UC San Diego)
- Algorithms Specialization (Stanford)
(Note: The Coursera courses can be audited to get free access to the lectures)
🎙 Disclosure: Please note that some of the links mentioned on this page may be affiliate links. This means that if you click on one of these links and make a purchase, I may earn a small commission from the sale.
Who Am I?
I’m Aswin Barath, a Software Engineering Nerd who loves building Web Applications, now sharing my knowledge through Blogging during the busy time of my freelancing work life. Here’s the link to all of my craziness categorized by platforms under one place: https://linktr.ee/AswinBarath
Keep Learning
Now, I guess this is where I say goodbye 👋. But, hey it’s time for you to start learning with your newfound Knowledge(Power)👨💻👩💻. Good Job that you made it this far 👏 & Thank you so much for reading my Blog 🙂.
Product of Array Except Self — LeetCode Java Solution was originally published in TechSoftware on Medium, where people are continuing the conversation by highlighting and responding to this story.
