Product of array except self | Leetcode #238

Показать описание

This video explains a very interesting and important problem for interview which is to find product of array except self. I have shown the solution along with example and code using 3 optimizations and the optimal approach solves the problem in just O(N) time and O(1) extra space. As usual, the CODE LINK is present below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

Рекомендации по теме

Комментарии

the cumulative multiplication at 10:41 will be 1 2 6 24

cronypau

This is the clearest, most succinct explainer of this problem that I have come across on YouTube. Kudos.

abhid

Thanks for you explanation! Although as a beginner I can only roughly understand until 10:00, but I'm gonna save this to my playlist and come back again when I improved myself in the future!

rynnxj

Most understandable approach on Youtube ... Appreciate your effort and time

adhirajmajumder

Bro, I feel i can solve this question if I have seen this before. First time, it's not possible. I could only come with division solution. Person who can come up with solution is a genius.

md-ayaz

Bhai, solving it in O(1) space was pure genius! It was like watching a thrilling suspense movie. I had solved the mystery to the point that you would you the o/p array in the calculation, but using that extra product variable was genius. Very nice!

ashishm

@4:18, code for this approach 🙂🙂
*TC-> O(N), SC->O(1) but using division operation* ✅✅

// CODE

class Solution {
public:
vector<int> nums) {

int n = nums.size();

int p = 1;
int countZero = 0;
// multiplying the elements, ignoring zero in the multiplication
// also counts the number of zeroes
for(int i=0; i<n; i++){

if(nums[i] ==0 ){
countZero++;
continue;
}

p = p*nums[i];

}

vector<int> ans(n, 0);

// if number of zeroes >= 2, then all elements in answer will be zero
if(countZero >= 2){
return ans;
}

for(int i=0; i<n; i++){

// if current element is zero, check to avoid divide by zero
if(nums[i]==0){
ans[i] = p;
continue;
}

if(countZero==1)
ans[i] = 0;
else if(countZero==0)
ans[i] = p/nums[i];

}

return ans;

}
};

anshumaan

This question came in goldman sachs exam in 2k19

shubhamsonal

Great explanation, thank you! I cannot come up with such algorithms on my own, I guess I just have to memorize it for interviews.

sapnokiranii

I did come up with my long solution but the last test case was like a millions of 1s and -1s and the time limit exceeded there. Your approach makes a lot of sense. Just clicking in my head. Nice approach and explanation.

dhruvmaindola

The last example it should be 24 instead of 12, the initial o/p array value

geekystuffs

Very smooth explanation. Due to u I m falling in love of dsa .

shikujha

Here is a pure Javascript solution:
var productExceptSelf = function(nums) {
let n = nums.length;
let output = Array(n).fill(1);

for(let i = 1; i < n; i++) {
output[i] = output[i - 1] * nums[i - 1];
}

let R = 1;
for (let i = n - 1; i >= 0; i--) {
output[i] *= R;
R *= nums[i];
}
return output;
};

merabdu

JS solution -
const productExceptSelf = function(nums) {
let result = []
let product = 1;
for (let i = 0; i < nums.length; i++) {
if (i > 0) {
product *= nums[i-1];
} else {
product *= 1;
}
result[i] = product;
}
product = 1;
for (let i = nums.length - 1; i >= 0; i--) {
if (i < nums.length - 1) {
product *= nums[i+1];
} else {
product *= 1;
}
result[i] *= product;
}

return result;
};

serenestrolls-db

Man, finally I understood this problem.. thank you very much

rakshith

Beautifully explained, I just needed the missing piece of the puzzle and you just provided me with this video thanks a lot

OilUp

This video finally helped me understand the solution. Thank you!

marhawk

very well explained... i cam across this question while searching for another similar but a littile more complex... can you please help solve..
The Question is:- Given an array of integers of size N, count all possible distinct triplets whose sum is exactly divisible by given integer K. for triplets i, j, k --> i<j<k

stupidbutcurious

Your explanations are clear and easy to understand, thank you!

andersvn

Nailed it man!!, u made me fall in the problem!!

neeleshkumar

Product of array except self | Leetcode #238

Product of Array Except Self - Leetcode 238 - Python

Product of Array Except Self - Leetcode 238 - Arrays & Strings (Python)

Product of Array Except Self - Leetcode 238

Medium Amazon Interview Question - Product of Array Except Self - Leetcode 238

LeetCode 238. Product of Array Except Self (Solution Explained)

Product of Array Except Self (LeetCode 238) | Full solution with visuals | Study Algorithms

FAANG Interview Question! Product of Array Except Self - Leetcode 238

LeetCode #238: Product of Array Except Self | Prefix Sum

Product of array except self | Leetcode #238

Product Of Array Except Self - LeetCode 238 - JavaScript

Product of Array Except Self | Brute to Optimal Solution | Leetcode 238

Product of Array Except Self | Leetcode 238 | Top 150 interview question series

Leetcode Q238: Product Of Array Except Self Solution VISUALIZED

Product of Array Except Self - LeetCode 238 Python

FAANG Interview Question! | Product of Array Except Self - Leetcode 238

PRODUCT OF ARRAY EXCEPT SELF | LEETCODE # 238 | PYTHON SOLUTION

Apple Coding Interview Question - Product Of Array Except Self

Leetcode | 238. Product of Array Except Self | Medium | Java Solution [2 Solutions]

238. Product of Array Except Self | Math | Prefix Product | 4 Approaches

Leetcode - 238 : Product of Array Except Self | Solution Explained | Java

Product of Array Except Self | Решение на Python | LeetCode 238

Product of Array Except Self | 4 Approaches | Detailed Explanation | Leetcode 238 | codestorywithMIK

LEETCODE 238 (JAVASCRIPT) | PRODUCT OF ARRAY EXCEPT SELF

Leetcode Product of Array Except Self | O(n) and O(1) | Python