This problem is called Product of Array Except Self, most commonly asked by Amazon. We create two auxillary arrays Left and Right which store the multiplication of all the elements to the left and right, and then multiply these 2 together to get our final answer. This allows for a solution in O(n) time. Drop a like if you found this helpful, and follow for more! :)
Why can’t we just get product of all the elements in one go. Then, For num in nums: Print(total_product//num) Won’t this work? Only issue would be handling big numbers but that should be the case anyways. Also why do we need extra space?
@HeatCode24 on this level of abstraction your idea needs less space and less time (both are in O(n) but yours needs two passes through the array, his needs 3). However the implementation of division is normally quite a bunch slower than multiplication and division might be less numerically stable. So I guess there's a good reason to more multiplications and use 3 times the space to avoid division. The way he teaches the problems in those shorts often seem however like he saw the solution somewhere and just regurgitates them. More than once painfully wrong. Here, I think this solution is very valid, but so is your question.
@@HeatCode24 well one obvious problem with the numerical stability of division is if one of the numbers is 0. You'd have to deal with that as well. It would be a special case, not harder, but a totally different algorithm. You'd have to check the number of zeros. If there's more than 1, everything is 0, if there's exactly one, everything is zero except that one place which is the product of all other numbers. If there's no 0, you can use your algorithm. And that instability exists for all numbers close to zero. Multiplication can underflow, but division can have arbitrarily large errors, which I think is less desirable.
There's a different solution: you multiply all elements of the array, and record the product. Then you loop over the array and divide the product by the current item, thus getting you what you need.
That is an overoptimistic solution. The input is a array of n numbers, so 0 can be one of them. Division only makes the code more messy because you have to check whether 0 exists
In 1 iteration, calculate the total number of zeros + total multiplication without zero If total zero is more then 1 your answer will be [0]*(len(input_arr)) Elif number is one then ans to index where zero is present else where put zeros Else simply iterate over each element and divide total with current value.... Space O(1) Time O(N)
@@wij8044I understand these problems have constraints, I also want to share the sentiment that I think the use of these problems are interview questions is so utterly stupid, especially with arbitrary constraints. The tech industry needs to improve their interviewing process. So rare that you need to actually DIY your data structures, and even if you did, all you need to recognize is if a problem is complex enough and is probably eolveable with some algo, then you can just look it up. Because a good software engineer is so much more than just some person who grinded leet code and can do DSA problems.
@@wij8044 that's dumb, why not use the full capability of the system? Instead you have to use double the space of the original array and 3 traversals instead of 2. How about, since it's integer division, use multiple subtraction in order not to use division? Sure it will suck for large numbers but so does the "no division" solution
Since it nowhere says you cannot use division it makes no sense why would someone not use it as it's the most efficient method, especially with large data sets, especially on bigger data sets. Division can indeed be a bit slow, but is it really worth making 2N sized temporary arrays just to avoid it?
@arsenypogosov7206 no, it could be a problem If L is a first number that can't fit in Integer you will have problem for example with arrays [L^0,5 , L^0,5] [L^(1/3), L^(1/3),L^(1/3)] And so on Obviously those number will need to be rounded up if it's a integer numbers And it's a lower limit for number that will cause problems
Do this instead - 1. Make a integer variable and product each element one by one. 2. Now again traverse the array for each index you will get the answer by dividing whole Array Product by i th index element
If you have two zeros, the result will be only zeros. If you have one, then only this number will be non zero. So, you need a product of non zero numbers plus counter of number of zeros (0, 1 or more than one)
@@saiprabath That came across my mind but didn’t give it much thought. You’re right, the point of the question would be useless if there was a 0 in the array. I’m going to take my first Data Structures class in a few weeks, any advice?
@@yomom4281 if basic are clear, then pick up blind 75 DSA sheet on leet code and try to solve all 75 problems, for any assistance u can refer striver's A to Z DSA sheet which have video solutions too for better understanding.
The time complexity of that solution is O(n^2). I'd rather deal with the edge cases involved in finding the total product and dividing. If 2 or more zeros exist, return array of zeros. If only one zero, do the calculation for zero manually and return zeros for the rest.
Simply feed the array into a loop, that multiplies by each spot, unless it is the spot its currently on, then you only do a single pass for each number, instead of 2 for each, and then another pass to combine them, and you dont need 3 arrays, just 2, its better in every respect
@@jbparkes190 How do Python multiply the values to the left / right in an array without using a for loop in the background? Or am I missing something here? edit: I checked internet, and very misleading in the video cause it looks like he traverse the original array and store the data in L or R which is not how it works. Then I understand.
This will not work if you have 0 as an element in the array. Multiplication of every element will zero the array and you will lose information about product of array except 0. Look: [ 1, 2, 0, 4] should return: [0, 0, 8, 0]. Product of whole array is just 0, so we loose that 8 in response
We can get the multiplication of all array then output in each index this multiplication devised by the element of this index(you can handle the places having zeroes).
Fill the target array with the product of all elements = [24, 24, 24, 24] and then loop through the original array and divide the number in the target array by the original value at that index. If you're using numpy, which you should be for anything numeric, this will be fastest.
@@GregHogg Hopefully in an actual coding interview they'd be more lenient. It's literally a one-liner in numpy ( np.divide(np.full(len(n), np.prod(n)), n) )
For wveryone coming up with the solution of multiplying all the numbers and the iterating and dividing by the current index, the problem asked us to do it without division
@@abhishekkumarsahu7228 Yes, although you could easily check for that. I think the reason for banning division is, that this algorithm will work for any 2 element opperation no matter if it is invertable or not. I justs was confused because I think the short does not specify that division is banned.
I think you can calculate the product of the array and simply skip the value at i. No risk of dividing by zero and less calculations. Literally the problem description.
@@GregHogg startList = [1, 2, 3, 4] resultList = [0] * len(startList) for i in range(len(startList)): result = 1 for j in range(len(resultList)): if i == j: continue result *= startList[j]
You could always just find the product of every number, then set each element in the return list to that value divided by the corresponding input value. O(1) in space (not counting the input/output data) and O(n) in time.
Yes absolutely, well done. There's a weird constraint in this problem I didn't have time to discuss which is that you can't use division operator. Awesome job 😊
We can have mul =1 then use nested for loop for the given list if i== j then continue else multiply and append in newlist called result btw this is in python by doing this we probably solve this and dont forget to rest value of mul to 1 after appending plz let me know if this logic is right
🔴🔴✅ *since the time complexity is O(n), can we iterate the array twice? In the first iteration we calculate the product of all the array elements and in the second iteration we just divide the product by current value. can It be another solution or something will go wrong?*
I hate how everybody is so crazy about arrays. I literally never had to deal with these examples, and I wrote linters, parsers and even filesystems. Never.
Either way the space complexity is still O(n) because you still have to make an array to store the result in your method However, having another loop in a loop causes a time complexity of O(n²), which is worse than the solution in the video O(n)
Is there a reason you couldn't instead multiply the array and for each value, divide the array by the position n and store it into a new array at the same position? Or is this way more efficient computationally?
I don't like this interview question It requires specialised knowledge for a very specific question, and essentially functions to test if you have done your research on the company and memorized its interview questions, unless you basically re-invent the solution on the spot. Especially if division is just artificially banned in your answer - its so unintuitive compared to the actual problems you'd be solving as a programmer. Division isn't a costly operation unless you care about miniscule differences in latency from the processor, and that's especially true in comparison to doubling the number of times you have to loop through the array and multiply. A similar but more applicable question could be a novel dynamic programming problem. It gets at the same technical level and type of lateral thinking problem solving skills, whilst also being useful in a practicable real world setting.
I mean yes, it does achieve that, but my point is: would you really argue that a problem that requires you to set artificial rules is the best way of testing someone's ability to use memoization? And especially in a real world scenario?
The naming is confusing not gonna lie Instead of productexpectself(L) you can write productExceptSelf(nums) Instead of P just write result Things like that Also flag is always the same as i in the outer for loop so I'm not sure why it is there instead of just using i Finally your code includes a double for loop so the time complexity is O(n²) which is normal but can be improved.
@@GregHogg my bad I was replying someone else's comment which is a piece of code with a double for loop I know you code is O(n) and is way better :) Not sure why my comment got here tho
def productexpectself(L): P=[] l=L flag=0 for i in range(len(L)): p=1 y=l.pop(flag) for x in l: p*=x P.append(p) l.insert(flag,y) flag += 1 print(P) productexpectself([1,2,3,4,5]) hlo, kindly view the code and share your opinion please..
The naming is confusing not gonna lie Instead of productexpectself(L) you can write productExceptSelf(nums) Instead of P just write result Things like that Also flag is always the same as i in the outer for loop so I'm not sure why it is there instead of just using i Finally your code includes a double for loop so the time complexity is O(n²) which is normal but can be improved.
Why not just use a for loop to do the multiplication? int *mul(int *src, int length) { int *res = (int *)malloc(sizeof(int) * length); if (!res) return NULL; int res_val = 1; for (int i = 0; i < length; i++) { for (int j = 0; j < i; j++) { res_val *= src[j]; } for (int j = i + 1; j < length; j++) { res_val *= src[j]; } res[i] = res_val; } return res; }
The interviewer always expects an efficient solution, your code might be correct but it uses two nested for loops, which brings your time complexity to O(n). Try to study about space and time complexities if u don't know. It will he helpful.
This problem is called Product of Array Except Self, most commonly asked by Amazon. We create two auxillary arrays Left and Right which store the multiplication of all the elements to the left and right, and then multiply these 2 together to get our final answer. This allows for a solution in O(n) time. Drop a like if you found this helpful, and follow for more! :)
Why can’t we just get product of all the elements in one go.
Then,
For num in nums:
Print(total_product//num)
Won’t this work? Only issue would be handling big numbers but that should be the case anyways.
Also why do we need extra space?
I have been asked a Variation of this question on my interview... Even more interesting
@HeatCode24 on this level of abstraction your idea needs less space and less time (both are in O(n) but yours needs two passes through the array, his needs 3).
However the implementation of division is normally quite a bunch slower than multiplication and division might be less numerically stable.
So I guess there's a good reason to more multiplications and use 3 times the space to avoid division.
The way he teaches the problems in those shorts often seem however like he saw the solution somewhere and just regurgitates them. More than once painfully wrong.
Here, I think this solution is very valid, but so is your question.
@@thimowellner7686 i most likely don’t see any flaws here except multiplication causing overflow which anyways should be the case here
@@HeatCode24 well one obvious problem with the numerical stability of division is if one of the numbers is 0. You'd have to deal with that as well.
It would be a special case, not harder, but a totally different algorithm. You'd have to check the number of zeros. If there's more than 1, everything is 0, if there's exactly one, everything is zero except that one place which is the product of all other numbers. If there's no 0, you can use your algorithm. And that instability exists for all numbers close to zero.
Multiplication can underflow, but division can have arbitrarily large errors, which I think is less desirable.
There's a different solution: you multiply all elements of the array, and record the product. Then you loop over the array and divide the product by the current item, thus getting you what you need.
Pensei o mesmo
That is an overoptimistic solution.
The input is a array of n numbers, so 0 can be one of them. Division only makes the code more messy because you have to check whether 0 exists
@@not_vinkami additionally, the product of all numbers may overflow even if the product except self does not.
@@not_vinkami if exists.
@@tobiaslangner267won't overflow in python 😊
In 1 iteration, calculate the total number of zeros + total multiplication without zero
If total zero is more then 1 your answer will be [0]*(len(input_arr))
Elif number is one then ans to index where zero is present else where put zeros
Else simply iterate over each element and divide total with current value....
Space O(1)
Time O(N)
Nice detail about zeros
The problem statement on LC actually ask to do this without division.
@@wij8044I understand these problems have constraints, I also want to share the sentiment that I think the use of these problems are interview questions is so utterly stupid, especially with arbitrary constraints.
The tech industry needs to improve their interviewing process. So rare that you need to actually DIY your data structures, and even if you did, all you need to recognize is if a problem is complex enough and is probably eolveable with some algo, then you can just look it up.
Because a good software engineer is so much more than just some person who grinded leet code and can do DSA problems.
@@wij8044 that's dumb, why not use the full capability of the system? Instead you have to use double the space of the original array and 3 traversals instead of 2.
How about, since it's integer division, use multiple subtraction in order not to use division? Sure it will suck for large numbers but so does the "no division" solution
@@vladk2kit’s for practice
Also, please send an email to greg.hogg1@outlook.com if you're interested in 1 on 1 private tutoring services with me! Have a great day :)
This channel is the best thing I have ever found on TH-cam shorts.
Awe so glad to hear it! Make sure you follow me on IG too if you ever use that platform, their algorithm really pushed the videos to followers
Me too
Since it nowhere says you cannot use division it makes no sense why would someone not use it as it's the most efficient method, especially with large data sets, especially on bigger data sets.
Division can indeed be a bit slow, but is it really worth making 2N sized temporary arrays just to avoid it?
The leetcode problem states that u can't use division
@@teodorgrigore290 thats stupid restriction
Good point.
Cons of division that you can get too big to be stored on some systems
@@Ford-ju9yr not in this problem though cause you will multiply all the numbers anyway.
@arsenypogosov7206 no, it could be a problem
If L is a first number that can't fit in Integer you will have problem for example with arrays
[L^0,5 , L^0,5]
[L^(1/3), L^(1/3),L^(1/3)]
And so on
Obviously those number will need to be rounded up if it's a integer numbers
And it's a lower limit for number that will cause problems
Awesome Greg! Keep these tutorials coming!
Thank you so much for the kind words! Will do 😊
Do this instead -
1. Make a integer variable and product each element one by one.
2. Now again traverse the array for each index you will get the answer by dividing whole Array Product by i th index element
The problem generally comes with a condition that do not use the division operation
Wouldn't work as if there was a single 0 then your product will be 0, so each element 0
@@PratyushSudarshanwe can use a flag to detect zero and the multiplication without zero
If you have two zeros, the result will be only zeros. If you have one, then only this number will be non zero. So, you need a product of non zero numbers plus counter of number of zeros (0, 1 or more than one)
@@PratyushSudarshan Isn't that correct? It's the product of array except self. If there's a 0 in the array the product should be 0.
this was my first problem where i come up with my own solution and it was better then this left and right array.
calculate the whole array multiplication then divide by each index
Wouldn’t work if one of the numbers is in the array is 0. But you can just have an if(Array[n]==0) don’t divide
For i loop -> (product of array / ith element) as simple as that
Wouldn’t work if one of the elements in the array is 0. But you can just have an if statement that’s if(Array[n]==0) don’t divide.
@@yomom4281 yes, but i don't think they'll give 0 in the array, because the answers will be array of zeros except the 0th element.
@@saiprabath That came across my mind but didn’t give it much thought. You’re right, the point of the question would be useless if there was a 0 in the array. I’m going to take my first Data Structures class in a few weeks, any advice?
This the logic I used as well
@@yomom4281 if basic are clear, then pick up blind 75 DSA sheet on leet code and try to solve all 75 problems, for any assistance u can refer striver's A to Z DSA sheet which have video solutions too for better understanding.
The time complexity of that solution is O(n^2). I'd rather deal with the edge cases involved in finding the total product and dividing. If 2 or more zeros exist, return array of zeros. If only one zero, do the calculation for zero manually and return zeros for the rest.
Simply feed the array into a loop, that multiplies by each spot, unless it is the spot its currently on, then you only do a single pass for each number, instead of 2 for each, and then another pass to combine them, and you dont need 3 arrays, just 2, its better in every respect
Incorrect. Your arrays from left and right can be done in a single pass of the array, rather than through N loops of the array.
@@jbparkes190 How do Python multiply the values to the left / right in an array without using a for loop in the background? Or am I missing something here? edit: I checked internet, and very misleading in the video cause it looks like he traverse the original array and store the data in L or R which is not how it works. Then I understand.
p = reduce(×, array)
map(λ x: p/x, array)
Nice lambda haha that's awesome
Glad someone else has the same idea!
How about you times all the numbers together and divide by the ith element of the array? It’s more efficient.
This question has a caveat that says you can’t use divisions. Otherwise yeah it’s pretty simple
There is a constraint to not use division operator
@@Swifty1412 Can't use division? Ok, use subtraction.
This will not work if you have 0 as an element in the array. Multiplication of every element will zero the array and you will lose information about product of array except 0. Look: [ 1, 2, 0, 4] should return: [0, 0, 8, 0]. Product of whole array is just 0, so we loose that 8 in response
you get multiplication overflow with large arrays or large values
We can get the multiplication of all array then output in each index this multiplication devised by the element of this index(you can handle the places having zeroes).
Handling zeros make that way more complex than this method tbh
Fill the target array with the product of all elements = [24, 24, 24, 24] and then loop through the original array and divide the number in the target array by the original value at that index. If you're using numpy, which you should be for anything numeric, this will be fastest.
Yeah you're absolutely right unfortunately the silly question just doesn't allow this solution
@@GregHogg Hopefully in an actual coding interview they'd be more lenient. It's literally a one-liner in numpy ( np.divide(np.full(len(n), np.prod(n)), n) )
Just get the product of the whole list. Return a list of the product divided by the original int in the position
O(1) space (replaces original list) and (n) time.
n = 1
for i in lst:
n *= i
for i in range(len(lst)):
lst[i] = n / lst[i]
return lst
If 0 in lst
@@Indian-dollar you got a point
For wveryone coming up with the solution of multiplying all the numbers and the iterating and dividing by the current index, the problem asked us to do it without division
pre compute the product and iterate through array replace arr[i] with product/arr[i]
Error! Cannot divide by zero.
why not multiply all the numbers together and then divide by the number you don't want?
Problem specifies not to use division!
can cause issue when one element is zero
@@abhishekkumarsahu7228 Yes, although you could easily check for that.
I think the reason for banning division is, that this algorithm will work for any 2 element opperation no matter if it is invertable or not.
I justs was confused because I think the short does not specify that division is banned.
Just multiply every element to get a number and then divide that number by the current element
I think you can calculate the product of the array and simply skip the value at i. No risk of dividing by zero and less calculations. Literally the problem description.
This isn't mathing to me
@@GregHogg startList = [1, 2, 3, 4]
resultList = [0] * len(startList)
for i in range(len(startList)):
result = 1
for j in range(len(resultList)):
if i == j:
continue
result *= startList[j]
resultList[i] = result
print(f"{resultList[i]}")
This gives the same result as far as I can tell
@@Pevi70 here is some javascript instead, easier to read nums = [1, 43, 3, 4, 3, 6];
array_length = nums.length;
prefix = 1;
suffix = 1;
result = [...nums]
result.fill(1, 1, array_length)
for (i = 1; i < array_length; i++) {
prefix *= nums[i - 1];
result[i] *= prefix;
suffix_i = array_length - i - 1;
suffix *= nums[suffix_i + 1];
result[suffix_i] *= suffix;
}
console.log(result);
how about using a deque. pop the current , product the rest up, append it back. and loop
Interesting idea!
In one loop find the product of all values, in the other divide the product by the number and save it, why isn't that easier?
You could always just find the product of every number, then set each element in the return list to that value divided by the corresponding input value. O(1) in space (not counting the input/output data) and O(n) in time.
Yes absolutely, well done. There's a weird constraint in this problem I didn't have time to discuss which is that you can't use division operator. Awesome job 😊
when you explained it, it sounded like you can not use 1 in any of the multiplications.. so I was very confused.
We can have mul =1 then use nested for loop for the given list if i== j then continue else multiply and append in newlist called result btw this is in python by doing this we probably solve this and dont forget to rest value of mul to 1 after appending plz let me know if this logic is right
Sounds like a zip of a tee of a left and right fold...
🔴🔴✅ *since the time complexity is O(n), can we iterate the array twice? In the first iteration we calculate the product of all the array elements and in the second iteration we just divide the product by current value. can It be another solution or something will go wrong?*
This would work, but the problem bans the division operator
"banning the division" is just a nice way of saying there may be 0 in the array somewhere
First comment 🙌
NEEEERRRRRRDDDDD!!!!
Just kidding, well done.
Oh definitely a nerd haha
Isn't that a permutation problem?
Top G
Hahaha ty
Yesss i’ve been waiting for this ❤❤
Wait no longer :)
I hate how everybody is so crazy about arrays. I literally never had to deal with these examples, and I wrote linters, parsers and even filesystems. Never.
Just practice problems for interviews
What if use 2 loops it could more easy, then no need to create two extra array
Either way the space complexity is still O(n) because you still have to make an array to store the result in your method
However, having another loop in a loop causes a time complexity of O(n²), which is worse than the solution in the video O(n)
Why don't you just use each number to divide the product of all? Of course you need to consider the situation where there is 0 in the array.
Is there a reason you couldn't instead multiply the array and for each value, divide the array by the position n and store it into a new array at the same position? Or is this way more efficient computationally?
Division by zero is possible
I don't like this interview question
It requires specialised knowledge for a very specific question, and essentially functions to test if you have done your research on the company and memorized its interview questions, unless you basically re-invent the solution on the spot.
Especially if division is just artificially banned in your answer - its so unintuitive compared to the actual problems you'd be solving as a programmer. Division isn't a costly operation unless you care about miniscule differences in latency from the processor, and that's especially true in comparison to doubling the number of times you have to loop through the array and multiply.
A similar but more applicable question could be a novel dynamic programming problem. It gets at the same technical level and type of lateral thinking problem solving skills, whilst also being useful in a practicable real world setting.
Not sure I agree. This is basically trying to find out if you can apply a form of memoization.
@@drcl7429 Then ask for an O(n) fibonnacci sequence, dont outright ban division
I mean yes, it does achieve that, but my point is:
would you really argue that a problem that requires you to set artificial rules is the best way of testing someone's ability to use memoization? And especially in a real world scenario?
A=[1,2,3,4]
ans=1
lst=[]
n=len(A)
for i in range(n):
ans=ans*A[i]
for j in range(n):
s=ans//A[j]
lst.append(s)
print(lst)
Yeah, this works :). For some reason the question bans use of the division operator though
The naming is confusing not gonna lie
Instead of productexpectself(L) you can write productExceptSelf(nums)
Instead of P just write result
Things like that
Also flag is always the same as i in the outer for loop so I'm not sure why it is there instead of just using i
Finally your code includes a double for loop so the time complexity is O(n²) which is normal but can be improved.
The code is actually O(n) :)
@@GregHogg my bad
I was replying someone else's comment which is a piece of code with a double for loop
I know you code is O(n) and is way better :)
Not sure why my comment got here tho
Why not do a cumulative product and then divide by each element? It's much simpler and faster.
Yeah this is a good idea, unfortunately the problems doesn't allow this solution via a constraint
Why not something like this?
import math
total = math.prod(array)
map(lambda x: total / x, array)
Great solution! The problem just doesn't allow this via a constraint:)
Dude just compute product of the elements and divide the product by each element. E.g. b*c*d = a*b*c*d / a
Yeah that would work if the problem didn't specifically have that as a constraint that you can't
Why to not just do division, if I have 1,2,3 and I want to have the product with without 2 I can take 1*2*3/2 and I will get the right answer
one continue can solve it too
Division takes a whole lot more time than multiplication. The original problems also forbids it from being used.
You describe the problems a bit complex, most of the times I don't understand what is the desired result of the interview when you explain!
Sorry about that I'll try harder to explain better
.
def productexpectself(L):
P=[]
l=L
flag=0
for i in range(len(L)):
p=1
y=l.pop(flag)
for x in l:
p*=x
P.append(p)
l.insert(flag,y)
flag += 1
print(P)
productexpectself([1,2,3,4,5])
hlo, kindly view the code and share your opinion please..
The naming is confusing not gonna lie
Instead of productexpectself(L) you can write productExceptSelf(nums)
Instead of P just write result
Things like that
Also flag is always the same as i in the outer for loop so I'm not sure why it is there instead of just using i
Finally your code includes a double for loop so the time complexity is O(n²) which is normal but can be improved.
Is this valid..
void except_self(int arr[],int n,int ans[]){
for(int i=0;i
Messed up
What is?
lmao how is this a medium
Why not just use a for loop to do the multiplication?
int *mul(int *src, int length)
{
int *res = (int *)malloc(sizeof(int) * length);
if (!res) return NULL;
int res_val = 1;
for (int i = 0; i < length; i++) {
for (int j = 0; j < i; j++) { res_val *= src[j]; }
for (int j = i + 1; j < length; j++) {
res_val *= src[j];
}
res[i] = res_val;
}
return res;
}
The interviewer always expects an efficient solution, your code might be correct but it uses two nested for loops, which brings your time complexity to O(n). Try to study about space and time complexities if u don't know. It will he helpful.