I love how nick treats you like you know absolutely nothing; it helps so much; everyone else just speeds through the solution and I couldn't understand it; you're #1 for algo explanations, dude, gj
You can easily come by that. In the first loop calculate the product of all non-zero numbers and set a boolean wheater or not you have seen a zero. If you run across a second zero, you can imedially return an all zero-array of the of the orginial length, otherwise replace the zero with the product and all other values with zero. Otherwise do the "division". Python Code: def productExceptSelf(inputArray): seenZero=False product=1 for i in inputArray: if i==0: if seenZero: return [0]*len(inputArray) seenZero=True else: product*=i outputArray=[] for i in inputArray: if seenZero: outputArray.append(0 if i!=0 else product) else: outputArray.append(product//i)
The first time I did this I did it recursively. Basically pass in the current product * the current number to the recursive function. Then you can set the current answer to the current product (what was initially passed in) * whatever was returned from your recursive function. Then return the returned product * current number.
Division is also much more expensive operation than multiplication. So even if second algorithm looks more complex (O(3n) versus O(2n)) it will be much faster since there is no excessive usage of slow / operator. Time analysis gives us time complexity in regards to n. But it doesn't tell us how much time individual operations take. Something interesting to know... And btw, I got this question for internship interview in Microsoft Development Center in my country (Serbia)
I woke up and i fell on this video . It's my first time seeing and interview qiestion and i just did the code in c it worked,but i guest there are more stronger and effective algorithms . Thanks for posting such question.
Even if you do can not use division, it can still be done in O(n) with only one for loop going from 1 to n-2, computing left array and right array at the same time. For left array, the value at i-th position is a[i-1]*left[i-1], and for right array, the value is a[i+1]*right[i+1]. But the algo is very smart. Good job and nice video
mine solution: simplicity is a king : def solution(arr): out = [] mul = 1 for i in range(len(arr)): mul *= arr[i] for i in range(len(arr)): out.append(int(mul/arr[i])) return out print(solution([1,3,7,5])) if there is another way to get multiply of all members we can get ride off that first for loop 😊
Initially, 😁 , I came up with this just after looking at the thumbnail (before watching) : def pro(l): p=1 for x in l: p*=x for i in range(len(l)): k=l[i] l[i]=p//k return l
Number of operations would still be the same, still 3n. First loop: n. Second loop: 2n, so the total is still 3n :) Comes out to being a simple question of which solution is more legible or error-prone.
Having not seen the solution in the video yet, my brute force approach would be to have two loops, the first loop goes through each element in the input array to keep track of the element we are skipping in the calculation. The next loop simply goes through the array again, this time we skip the element pointed to in the first loop, and simply get the product of every other element in the array, storing the result in a new array (we keep track of our location in this new array using the outer loop). I believe this is O(N^2) complexity, so not sure if it would be an acceptable solution in an interview however, but this would be where I would start with this problem: public static int[] productExcludingSelf(int[] input) { int[] products = new int[input.length]; for(int i=0; i
Hey man! I also tried doing it this way but the output is way too different than what I expected it to be. I'm kind of new to programming so I didn't really go into complexity for this question and following the boilerplate code mentioned in the question. Can you pls tell me where I'm going wrong? Would be a great help. Here's my logic. public static void prod(int[] arr) { for(int i=0; i
@@nayanyadav6919 hi man do not use this approach as you get it wrong when the particular element is repeated in the array. I will paste my sol in the below you can check it out you can do it by taking to loops and inputting the number of the second loop where both the loops run from 0 to the len(array)-1 and you can create two lists one outside the two loops and one inside the 1st loop and you will check that if the number in the 1st loop != number In the second loop in this way you can eliminate the element repetition and you will append it with the 2nd list which is present inside and then at last you can append the second loop with the first loop in this way you can append only those numbers which are not same as the 1st loop number and at the end you can create another loop where it is in the form of a list inside the list and you can multiply the numbers in the end. The solution in python:- a=[2,2,3,4] r=[] for j in range(len(a)): s=[] for m in range(len(a)): if j==m: s=s else: s+=[m] r+=[s] for ch in r: s=1 for m in ch: s*=a[m] print(s)
@@freeshavaacadooo1095 1000? you've gotta be kidding me :D besides multiplication anyway will suffer for any large numbers due to overflow - from this point you'll find yourself solving quite another puzzle than pesky logarithm expensiveness :)
I noticed you had the same problem open at CodeSignal. However, if you tried to solve that one, you'd have probably seen that the challenge is a bit different. They do not guarantee that the product of all numbers in the input array fits any of the integer sizes in e.g. C++. It would be interesting to see a video on that one too
You can rotate the array every time abd gthan you can multiply everything that in the array to m-1 so every time you rotate it will be to the number you dont want to multiply in and than you can just to it but i dont thing its good for time complicity
A way of making it O(n) instead of O(2n) which the problem asks for is to put them into the same for loop and put them both in at the same time, however, you do have to add an if statement to check whether the item is already in the list, and if so, times it by the item already in the list, if not, just add it in. However, you do have to have to keep track of the current multiplier which means an extra two variables, but these are only ints. This is it in PHP: function productExceptSelf($nums){ $length = count($nums); $output_arr = array(); $left_current=1; $right_current = 1; $j=$length-2; $output_arr[0]=1; for($i=1;$i
O specifies a class/set of functions; accordingly, O(n) = O(2n) = O(an) for a in R* . Having multiple for loops does not violate the constraints (not to mention, 1. doing more work in a single loop isn’t all that different from having multiple separate for loops [in the sense that you would be doing, say, 2 units of work per iteration instead of 1], and 2. having simpler separated for loops can be more easily unrolled and optimized, so your solution is likely *slower* than having multiple separate for loops).
To anyone who still says something like 'languages are all the same except different syntax' , this is litterally a one-liner in haskell (this legitimately took me 2 mins) pes l = (product . (`delete`l)) l Or in a less point-free style: pes l = map (\x -> product (delete x l)) l
I was asked this exact question in a recent interview by Goldmann Sachs. First I used division, then the interviewer asked to do it without division. I followed up with precalculating suffix products and calculating prefix products on the go.
When it comes to job interview coding questions what are they mainly looking for? It is mostly or heavily Algorithms and understand how they perform???
I have read a lot about this, so tldr; you are expected to 'get the job done' but talking your way trough is very important, since they can't tell what you are thinking; so you've got to talk! You have to try make it more like a friendly technical-conversation, rater than technical question and answer test :)
My solution would be (JS): function productExceptSelf(input) { var output = []; for (var i = 0; i < input.length; i++) { var product = 1; for (var j = 0; j < input.length; j++) { if (j != i) { product *= input[j]; } } output.push(product) } return output; } Seems the least complicated to me, because while multiplying with left and right is true, its easier to say it multiplies with everything except the own index (j != k)
Nick - how is this explanation ? Its essentially the same as yours but condensed. Take S = [2,3,4,5] as an example. The expected answer is P = [60, 40, 30, 24]. "DIAGRAM" : "1"[3,4,5]. product = "1", 3,4,5. [2][4,5]. product = 2,4,5. [2,3][5]. product = 2,3,5. [2,3,4]"1". product = 2,3,4, "1". S = the given array, Ni = the i-th element of S, Pi = product for Ni, Li = product of numbers on left of Ni, Ri = product of numbers on right of Ni. Thus, Pi = Li * Ri, for each Ni. We also see it the above "diagram". STEPS - (1) First find only Li for each element in S ["1", {1 * 2}, {2 * 3} , {6 * 4}] == [1, 2, 6, 24] (2) Next we find only Ri for each element in S [{20 * 3}, {5 * 4}, {5 * 1}, "1"] == [60, 20, 5, 1] (3) Now, multiply the corresponding elements of Li & Ri to get Pi == [60, 40, 30,24]. Thus, step 3 gives us the answer we expected. Notice that we can combine steps 2,3 as discussed at 8:20 instead of doing them separately.
we can divide so we get to 2n (1. loop to multiple all elements to get product of all, 2. loop again to take elements and divide product) but without division and with this solution it's 3n (left product , right product , result) but why tho ... without division
Using the first approach If we cannot divide then we can instead of dividing by 2 we can multiply by 1/2 so generalizing it instead of dividing by n we will multiply by 1/n just a trick to get around this problem using the first approach.
This solution is correct only for small arrays. E.g. if all elements >= 2, it will overflow for lengths of 64+. If it is not correct for n > 63, what is the point to have O(n), while O(n*n) is simpler and likely not slower in real CPU architecture?
Before even watching the video, this is how I would do it (in C): int input[4] = {1, 2, 3, 4}; // input array of the example int output[4] = {1, 1, 1, 1}; // initialize output array to 1's (neutral element of multiplication) for (int i = 0 ; i < 4 ; i++) { // multiply the current position in the OUTPUT array with every value to the left of the current position in the INPUT array (except first one). if (i != 0) { for (int j = i-1 ; j > 0 ; j--) { output[i] *= input[j]; } } // Do the same thing but to the right. if (i != 3) { for (int j = i+1 ; j < 4 ; j++) { output[i] *= input[j]; } } } Edit: I'll take it as a win
This left of it and right of it like key to solving half the array questions I have tried ... It's kind of like recursion so I like it but it always ends up taking a lot of space
const produce = arr => { return arr.map((e, i, a) => { const sub = [...a]; sub.splice(i, 1); return sub.reduce((a, b) => a * b) }) } console.log(produce([1, 2, 3, 4]));
Im an electrical engineer. I can code but Im not familiar with any of the computer science jargon you used. I solved it with a nested for loop. What is time complexity and space complexity?
I solved it with a nested for loop. The first loop loops over the array, the second loop does the multiplying, and skips over the index of the current item. Less complicated and it allows you to make only 1 new array. Your indexes are tracked by the for loops and you only need to make 1 variable, the array.
Hey man! I also tried doing it this way but the output is way too different than what I expected it to be. I'm kind of new to programming so I didn't really go into complexity for this question and following the boilerplate code mentioned in the question. Can you pls tell me where I'm going wrong? Would be a great help. Here's my logic. public static void prod(int[] arr) { for(int i=0; i
My go to solution was to have 2 for loops (1 is nested), *= a variable (initialized at 1). Only thing is that if the iteration variable of inner loop == interation variable of outer loop, continue through inner for loop. Store to temp, return temp, but I guess this is too long?
My progress (3 functions for this one, last one is the Nick's version) def func(arr): ans = [0]*len(arr) x = 1 for i in arr: x *= i for i, e in enumerate(arr): ans[i] = x // e return ans def func2(arr): ans = [0]*len(arr) x = 1 for i in arr: x *= i cnt_global = 0 for i, e in enumerate(arr): m = e cpy = x cnt = 0 while cpy >= m: cnt += 1 cpy -= m cnt_global += 1 ans[i] = cnt # print(cnt_global) return ans def func3(arr): length = len(arr) ans = [0]*length left = [1]*length right = [1]*length cnt = 0 x = 1 for i in range(length-1): x *= arr[i] left[i+1] = x cnt += 1 x = 1 for i in range(length-1, 0, -1): x *= arr[i] right[i-1] = x cnt += 1 for i in range(length): ans[i] = left[i]*right[i] cnt += 1 # print(cnt) return ans arr = [1, 2, 3, 4, 5] print(func(arr)) print(func2(arr)) print(func3(arr))
input = [1,2,3,4] # output = [24,12,8,6] n = input o = [ ] y=1 for i in input: for j in n: if(i!=j): y=y*j o.append(y) y=1 print(o) # i have solved it by my self using python
we can get the product of every element in the array and then loop through the array one by one and divide that product with each element and store it in a new array of the same size
@Nick White I noticed that in your previous video you initalized a hashSet and went ahead without looking at the complexity of it but I thought creating a null hash table required time O(m)
First iterate a loop and multiply all elements of an array and store into result variable. After that iterate same loop and divide result variable with ith element give ans for that position
No division? How about this: Log(a/b) = log(a)-log(b); a=b*exp(log(a)-log(b)). We gotta deal with the negatives and zeroes additionally though, which is not a problem
I agree it's clever, but you can potentially lose precision and get the wrong result. Floating point operations are not good when solving integer problems.
hey im curious if i followed the rule , my step is to gather all number in inputarray and then remove one of the number depend on the i or how many time it loops (example if the second loop remove the number from index 1) and then multiply all the number within the array after that store it to outputrray
Great explanation and technique. I had a solution in my mind that can't we just loop through the array and multiply each element and store it. Then loop again and divide the stored value by every element and store it in output array.
If the numbers have a bounded range, you could do exactly that but use bitshifts and multiplication by the modular inverse (acquired via lookup table) to get around the division restriction. Then you could do it in-place.
How about having a single for loop and each time making that particular index element as 1 and multiplying the whole array... Thus ending without division and O(n).
hey nick! I have been watching your videos a lot recently. I am 16 and still in my sophomore year of high school. I am learning my first language (python) and i have gotten to OOP. Do you have any advice for my future (hopefully a SWE). Thanks!
Would we not want to use the length call and instead check to see if the end of the array was nil and do all of that if this was in C since it’s O(n). I mean it would increase runtime by only alittle, it would still be O(n) lol.
We can also solve this by simply taking the except element to 0th index in single loop and splitting the list from 0th index and finding the product of elements of list from first index to end, so no notation of left and right required..🙌
How about this solution (Python) using a sliding window? import numpy as np if len(arr) == 0: raise Exception("Invalid array") else: products = [] for i in range(len(arr)): product = np.prod(arr[:i] + arr[i + 1:]) products.append(product) return products
I'm gonna take a stab at 2:23, before you show your solution. create a variable total_product, set it equal to the product of all numbers in nums. go through nums and set output[i] to total_product / nums[i] Edit: 3:10.... I see the problem here... power of -1 then!
what about creating a duplicate of given array and swapping the element of whose product without self is to calculate with the first element then multiplying index 1 to 4 and storing it in result array on corresponding index... then assigning resetting the previous value of duplicate array again and do it for the next element till last element to ignore dividing? pretty easy question
What advantage does the leftproduct and rightproduct arrays provide as opposed to calculating and multiplying the elements in the list to the left and right of that index in the loop itself?
Raahel Baig time complexity. If you calculate the product of elements to the left and right of every single index (which would be necessary to be able to use your implementation), you have a time complexity of O(n^2) which is too long for the problem
if array element cant be 0, then this solution is faster. int[] input = {1, 2, 3, 4}; int[] output = new int[input.length]; double temp, result = 1; for(Integer i : input) result *= i; for (int i = 0; i < input.length; i++) { temp = result * Math.pow(input[i], -1); output[i] = (int)temp; }
Ok so my solution worked a lil something like this: First multiply everything and store it Second for every element in input array store into second array stored/element
![รวมมิตร ภาพนี้ก็ฮาเหมือนกันนะเนี้ย #4 SS2 [ พากย์นรก MEME.EXE ] | easy boy](http://i.ytimg.com/vi/kl86m9gnLt8/mqdefault.jpg)
![ถามตรงๆ กับ อาจตุพร ทำไม ประเทศไทย ใครเป็นนายก ก็โดนด่า พอออกเเล้วคนคิดถึง!!?? l [Nickynachat]](http://i.ytimg.com/vi/3YFLMXxBGAs/mqdefault.jpg)
I love how nick treats you like you know absolutely nothing; it helps so much; everyone else just speeds through the solution and I couldn't understand it; you're #1 for algo explanations, dude, gj
Can’t divide?... a * Math.pow(b, -1); 😎
check mate
res[i] = (int)(p * Math.pow(nums[i],-1)); fails for 3 of the test cases O.o. I'm really curious about how you would solve it doing this
Just to know won't this be the same as divide ,so can we do it
That's literally dividing dude.
Modern problems require modern solutions 🤣🤣
Dude you're so chill. Watching these simple explanations is relaxing.
no homo.
Great vid! Another problem with the simple division solution is you gotta watch out for division by 0 error (if the input array contains 0).
The input doesn't contain anything less than 1
@@MohammadIshfaqueJahanRafee i think it was the length of array not the input of array
Use try n except blocks
If it throws zero division error
Then try to catch that error via exception block......store the result as zero
If it contained 0, easiest thing would be to write every other answer as 0 and then put the value of the product at the 0 value's index
You can easily come by that. In the first loop calculate the product of all non-zero numbers and set a boolean wheater or not you have seen a zero. If you run across a second zero, you can imedially return an all zero-array of the of the orginial length, otherwise replace the zero with the product and all other values with zero. Otherwise do the "division". Python Code:
def productExceptSelf(inputArray):
seenZero=False
product=1
for i in inputArray:
if i==0:
if seenZero: return [0]*len(inputArray)
seenZero=True
else:
product*=i
outputArray=[]
for i in inputArray:
if seenZero:
outputArray.append(0 if i!=0 else product)
else:
outputArray.append(product//i)
The first time I did this I did it recursively. Basically pass in the current product * the current number to the recursive function. Then you can set the current answer to the current product (what was initially passed in) * whatever was returned from your recursive function. Then return the returned product * current number.
Division is also much more expensive operation than multiplication. So even if second algorithm looks more complex (O(3n) versus O(2n)) it will be much faster since there is no excessive usage of slow / operator. Time analysis gives us time complexity in regards to n. But it doesn't tell us how much time individual operations take. Something interesting to know... And btw, I got this question for internship interview in Microsoft Development Center in my country (Serbia)
I'll code both the variants. Let's see what's faster.
@@bhavyajain638 So??
I woke up and i fell on this video .
It's my first time seeing and interview qiestion and i
just did the code in c it worked,but i guest there are more stronger and effective algorithms .
Thanks for posting such question.
Hi, man I found your channel today and I love it so much! You are amazing man, you are helping a lot of beginners like me, thank you so much
Even if you do can not use division, it can still be done in O(n) with only one for loop going from 1 to n-2, computing left array and right array at the same time. For left array, the value at i-th position is a[i-1]*left[i-1], and for right array, the value is a[i+1]*right[i+1]. But the algo is very smart. Good job and nice video
this is how I did it in matlab:
a= [1,2,3,4];
out=[];
for i = 1:length(a)
b=a;
b(i)=[];
multi = prod(b);
out=[out,multi]
end
Better explanation than Techlead
+
Humble and Funny and probably more talented
..
This dude is the whole package
mine solution:
simplicity is a king :
def solution(arr):
out = []
mul = 1
for i in range(len(arr)):
mul *= arr[i]
for i in range(len(arr)):
out.append(int(mul/arr[i]))
return out
print(solution([1,3,7,5]))
if there is another way to get multiply of all members we can get ride off that first for loop 😊
For i in range(n):
For j in range(n):
If i=!J:
s=s*arr[i]
m.append(s)
print(m)
Initially, 😁 ,
I came up with this just after looking at the thumbnail (before watching) :
def pro(l):
p=1
for x in l:
p*=x
for i in range(len(l)):
k=l[i]
l[i]=p//k
return l
l=[1,2,3,4]
print(pro(l))
You're the coolest programmer I've ever seen on youtube.
You can multiply in the second loop so it will be 2n
Number of operations would still be the same, still 3n. First loop: n. Second loop: 2n, so the total is still 3n :) Comes out to being a simple question of which solution is more legible or error-prone.
That chrome tab, "make bottom taskbar disappear" 😂😂
Having not seen the solution in the video yet, my brute force approach would be to have two loops, the first loop goes through each element in the input array to keep track of the element we are skipping in the calculation. The next loop simply goes through the array again, this time we skip the element pointed to in the first loop, and simply get the product of every other element in the array, storing the result in a new array (we keep track of our location in this new array using the outer loop).
I believe this is O(N^2) complexity, so not sure if it would be an acceptable solution in an interview however, but this would be where I would start with this problem:
public static int[] productExcludingSelf(int[] input) {
int[] products = new int[input.length];
for(int i=0; i
Hey man! I also tried doing it this way but the output is way too different than what I expected it to be. I'm kind of new to programming so I didn't really go into complexity for this question and following the boilerplate code mentioned in the question. Can you pls tell me where I'm going wrong? Would be a great help. Here's my logic.
public static void prod(int[] arr)
{
for(int i=0; i
@@nayanyadav6919 hi man do not use this approach as you get it wrong when the particular element is repeated in the array. I will paste my sol in the below you can check it out you can do it by taking to loops and inputting the number of the second loop where both the loops run from 0 to the len(array)-1 and you can create two lists one outside the two loops and one inside the 1st loop and you will check that if the number in the 1st loop != number In the second loop in this way you can eliminate the element repetition and you will append
it with the 2nd list which is present inside and then at last you can append the second loop with the first loop in this way you can append only those numbers which are not same as the 1st loop number and at the end you can create another loop where it is in the form of a list inside the list and you can multiply the numbers in the end.
The solution in python:-
a=[2,2,3,4]
r=[]
for j in range(len(a)):
s=[]
for m in range(len(a)):
if j==m:
s=s
else:
s+=[m]
r+=[s]
for ch in r:
s=1
for m in ch:
s*=a[m]
print(s)
Index = int(input ("which Index you want?"))
C = 1
for I , j in enumerate(nums):
If I != index:
c*= j
Print(c)
...or use logarithm property: a/b = pow(x, logx(a) - logx(b)), where x is any base... and pay attention to zeros and signs :)
It would be computationally expensive compared to just looping 3 times. Imagine how that operation scales for an array of length 1000 or something.
@@freeshavaacadooo1095 1000? you've gotta be kidding me :D besides multiplication anyway will suffer for any large numbers due to overflow - from this point you'll find yourself solving quite another puzzle than pesky logarithm expensiveness :)
I noticed you had the same problem open at CodeSignal. However, if you tried to solve that one, you'd have probably seen that the challenge is a bit different. They do not guarantee that the product of all numbers in the input array fits any of the integer sizes in e.g. C++. It would be interesting to see a video on that one too
for x in array: array[x]=1, multiply, output[x]=result
That’s quadratic time
You can rotate the array every time abd gthan you can multiply everything that in the array to m-1 so every time you rotate it will be to the number you dont want to multiply in and than you can just to it but i dont thing its good for time complicity
A way of making it O(n) instead of O(2n) which the problem asks for is to put them into the same for loop and put them both in at the same time, however, you do have to add an if statement to check whether the item is already in the list, and if so, times it by the item already in the list, if not, just add it in. However, you do have to have to keep track of the current multiplier which means an extra two variables, but these are only ints. This is it in PHP:
function productExceptSelf($nums){
$length = count($nums);
$output_arr = array();
$left_current=1;
$right_current = 1;
$j=$length-2;
$output_arr[0]=1;
for($i=1;$i
O specifies a class/set of functions; accordingly, O(n) = O(2n) = O(an) for a in R* . Having multiple for loops does not violate the constraints (not to mention, 1. doing more work in a single loop isn’t all that different from having multiple separate for loops [in the sense that you would be doing, say, 2 units of work per iteration instead of 1], and 2. having simpler separated for loops can be more easily unrolled and optimized, so your solution is likely *slower* than having multiple separate for loops).
Also we can use division by subtraction method, since technically we are not allowed to use the division operator
At first I thought why u make video on such a simple question but at the end I realise why u did
same here bro xD
I don’t think you need the 3rd loop. You could do the output array calculation in the 2nd loop after getting the right_products.
It's same time and space complexity
@@MegaPremios how is it same time complexity? Just Going through the loop, doing nothing will take some time. Won't it?
I'm a beginner.
@@bhavyajain638 You either do 2 operations N times, or you do 1 operation 2*N times. If you are looking at lines of code execution, it's the same
@@MegaPremios yes I get it. Thanks
Define a function
Int divide(Divident, divisor):
c=1
while (Divident>1):
Divident-=divisor
c-=-1
return c
I think this should also work...
if divisor is 0 or negative it's an infinite loop
Division here is O(n) so the entire solution would be O(n^2)
In addition, the second solution only requires 2 loops instead of 3.
After all, it's just a more condensed/optimised version of the original solution.
To anyone who still says something like 'languages are all the same except different syntax' , this is litterally a one-liner in haskell (this legitimately took me 2 mins)
pes l = (product . (`delete`l)) l
Or in a less point-free style:
pes l = map (\x -> product (delete x l)) l
I was asked this exact question in a recent interview by Goldmann Sachs. First I used division, then the interviewer asked to do it without division. I followed up with precalculating suffix products and calculating prefix products on the go.
how'd the interview go?
let tab = [1, 2, 3, 4]
let output=[]
tab.forEach(val1 =>output.push(tab.filter(val2=>val2!==val1).reduce((a,b)=>a*b,1)))
console.log(output); // [ 24, 12, 8, 6 ]
When it comes to job interview coding questions what are they mainly looking for? It is mostly or heavily Algorithms and understand how they perform???
I have read a lot about this, so tldr; you are expected to 'get the job done' but talking your way trough is very important, since they can't tell what you are thinking; so you've got to talk! You have to try make it more like a friendly technical-conversation, rater than technical question and answer test :)
Can we also use recursion to the left, and right, then multiply them after ? Divide and conquer?
That was my first solution before watching his solution but I think it is O(n*log(n))
thank you so much for this amazing solution
Man, I came back here after 2 months and look you are a star now ! So happy for you buddy !
My solution would be (JS):
function productExceptSelf(input) {
var output = [];
for (var i = 0; i < input.length; i++) {
var product = 1;
for (var j = 0; j < input.length; j++) {
if (j != i) {
product *= input[j];
}
}
output.push(product)
}
return output;
}
Seems the least complicated to me, because while multiplying with left and right is true, its easier to say it multiplies with everything except the own index (j != k)
Amazing solution! Thank you
Nick - how is this explanation ? Its essentially the same as yours but condensed.
Take S = [2,3,4,5] as an example. The expected answer is P = [60, 40, 30, 24].
"DIAGRAM" :
"1"[3,4,5]. product = "1", 3,4,5.
[2][4,5]. product = 2,4,5.
[2,3][5]. product = 2,3,5.
[2,3,4]"1". product = 2,3,4, "1".
S = the given array, Ni = the i-th element of S,
Pi = product for Ni, Li = product of numbers on left of Ni, Ri = product of numbers on right of Ni.
Thus, Pi = Li * Ri, for each Ni. We also see it the above "diagram".
STEPS -
(1) First find only Li for each element in S ["1", {1 * 2}, {2 * 3} , {6 * 4}] == [1, 2, 6, 24]
(2) Next we find only Ri for each element in S [{20 * 3}, {5 * 4}, {5 * 1}, "1"] == [60, 20, 5, 1]
(3) Now, multiply the corresponding elements of Li & Ri to get Pi == [60, 40, 30,24].
Thus, step 3 gives us the answer we expected. Notice that we can combine steps 2,3 as discussed at 8:20 instead of doing them separately.
You Really Make Good Videos! It’s Just best whenever you explain those! Thank you for these and yeah, already subscribed 😁!
we can divide so we get to 2n (1. loop to multiple all elements to get product of all, 2. loop again to take elements and divide product)
but without division and with this solution it's 3n (left product , right product , result)
but why tho ... without division
A (surprisingly expressive) one-liner Haskell version of the first solution:
productExceptSelf :: [Int] -> [Int]
productExceptSelf nums = zipWith (*) (init $ scanl (*) 1 nums) (tail $ scanr (*) 1 nums)
Using the first approach If we cannot divide then we can instead of dividing by 2 we can multiply by 1/2 so generalizing it instead of dividing by n we will multiply by 1/n just a trick to get around this problem using the first approach.
This solution is correct only for small arrays. E.g. if all elements >= 2, it will overflow for lengths of 64+.
If it is not correct for n > 63, what is the point to have O(n), while O(n*n) is simpler and likely not slower in real CPU architecture?
Can you explain why will it break? And how does n^2 solution overcome it?
Before even watching the video, this is how I would do it (in C):
int input[4] = {1, 2, 3, 4}; // input array of the example
int output[4] = {1, 1, 1, 1}; // initialize output array to 1's (neutral element of multiplication)
for (int i = 0 ; i < 4 ; i++) {
// multiply the current position in the OUTPUT array with every value to the left of the current position in the INPUT array (except first one).
if (i != 0) {
for (int j = i-1 ; j > 0 ; j--) {
output[i] *= input[j];
}
}
// Do the same thing but to the right.
if (i != 3) {
for (int j = i+1 ; j < 4 ; j++) {
output[i] *= input[j];
}
}
}
Edit: I'll take it as a win
This left of it and right of it like key to solving half the array questions I have tried ... It's kind of like recursion so I like it but it always ends up taking a lot of space
const produce = arr => {
return arr.map((e, i, a) => {
const sub = [...a];
sub.splice(i, 1);
return sub.reduce((a, b) => a * b)
})
}
console.log(produce([1, 2, 3, 4]));
Love how you explain this stuff 😅
you know, what tool he use to explain the solution?
Thanks man, it is really helpful!
Im an electrical engineer. I can code but Im not familiar with any of the computer science jargon you used. I solved it with a nested for loop. What is time complexity and space complexity?
I solved it with a nested for loop. The first loop loops over the array, the second loop does the multiplying, and skips over the index of the current item. Less complicated and it allows you to make only 1 new array. Your indexes are tracked by the for loops and you only need to make 1 variable, the array.
Hey man! I also tried doing it this way but the output is way too different than what I expected it to be. I'm kind of new to programming so I didn't really go into complexity for this question and following the boilerplate code mentioned in the question. Can you pls tell me where I'm going wrong? Would be a great help. Here's my logic.
public static void prod(int[] arr)
{
for(int i=0; i
That's quadratic not linear
My go to solution was to have 2 for loops (1 is nested), *= a variable (initialized at 1). Only thing is that if the iteration variable of inner loop == interation variable of outer loop, continue through inner for loop. Store to temp, return temp, but I guess this is too long?
My code:
int[] allBut(int[] input){
int[] output = new int[input.length];
for(int i = 0; i < input.length; i++){
int product = 1;
for(int move = 0; move < input.length; move++){
if (move == i) continue;
product *= input[move];
}
output[i] = product;
}
return output;
}
My progress (3 functions for this one, last one is the Nick's version)
def func(arr):
ans = [0]*len(arr)
x = 1
for i in arr:
x *= i
for i, e in enumerate(arr):
ans[i] = x // e
return ans
def func2(arr):
ans = [0]*len(arr)
x = 1
for i in arr:
x *= i
cnt_global = 0
for i, e in enumerate(arr):
m = e
cpy = x
cnt = 0
while cpy >= m:
cnt += 1
cpy -= m
cnt_global += 1
ans[i] = cnt
# print(cnt_global)
return ans
def func3(arr):
length = len(arr)
ans = [0]*length
left = [1]*length
right = [1]*length
cnt = 0
x = 1
for i in range(length-1):
x *= arr[i]
left[i+1] = x
cnt += 1
x = 1
for i in range(length-1, 0, -1):
x *= arr[i]
right[i-1] = x
cnt += 1
for i in range(length):
ans[i] = left[i]*right[i]
cnt += 1
# print(cnt)
return ans
arr = [1, 2, 3, 4, 5]
print(func(arr))
print(func2(arr))
print(func3(arr))
input = [1,2,3,4]
# output = [24,12,8,6]
n = input
o = [ ]
y=1
for i in input:
for j in n:
if(i!=j):
y=y*j
o.append(y)
y=1
print(o)
# i have solved it by my self using python
I assume you wouldn’t be allowed to multiply by i^-1 each time right?
Amazing stuff mate as usual
we can get the product of every element in the array and then loop through the array one by one and divide that product with each element and store it in a new array of the same size
@Nick White I noticed that in your previous video you initalized a hashSet and went ahead without looking at the complexity of it but I thought creating a null hash table required time O(m)
First iterate a loop and multiply all elements of an array and store into result variable.
After that iterate same loop and divide result variable with ith element give ans for that position
It was asked not to use division
No division? How about this: Log(a/b) = log(a)-log(b); a=b*exp(log(a)-log(b)). We gotta deal with the negatives and zeroes additionally though, which is not a problem
log and exp are costy functions but this is a clever trick 👍🏽
I agree it's clever, but you can potentially lose precision and get the wrong result. Floating point operations are not good when solving integer problems.
hey im curious if i followed the rule , my step is to gather all number in inputarray and then remove one of the number depend on the i or how many time it loops (example if the second loop remove the number from index 1) and then multiply all the number within the array after that store it to outputrray
I knew what to do but I couldn't translate it into code :/
Thanks for the wonderful explanation.
you make problems look simple
Are these coding questions for Software roles? I have a CAD Engineer role interview with Apple. Can I expect similar questions?
Yo Nick I just wanted to say something really surprising ...
You're awesome bud
I got a idea as take initial array contain 1s as same size of input and then multiple all items of output array expect the one for we are calculating
Great explanation and technique.
I had a solution in my mind that can't we just loop through the array and multiply each element and store it. Then loop again and divide the stored value by every element and store it in output array.
In the problem they said "solve it without division"
@@_techwaves okay. Thanks for clarifying it for me.😊
@@SuperGilly123456789 ❤❤
If the numbers have a bounded range, you could do exactly that but use bitshifts and multiplication by the modular inverse (acquired via lookup table) to get around the division restriction. Then you could do it in-place.
@@LoganKearsley Okay. Thanks mate.
How about having a single for loop and each time making that particular index element as 1 and multiplying the whole array... Thus ending without division and O(n).
you'll multiply whole array n times (for each index) that leaves you with O(n^2).
This is N^2
Can't you do something like this:
total = e^(sum(input))
for i in range 0,len(input):
output[i] = ln (total - e^input[i])
hey nick! I have been watching your videos a lot recently. I am 16 and still in my sophomore year of high school. I am learning my first language (python) and i have gotten to OOP. Do you have any advice for my future (hopefully a SWE). Thanks!
Wouldn’t two pointers or two indexes take less time?
Yes it will take less time but the complexity remains the same.
Great as usual ✊
well explained bro
Hi Nick
Can you please create a playlist of all hard problems in Leetcode? I love the way you explain... keep it up
He did created, check out his page
You are doing great work bro. Keep it up!!! 😀😀
Nice solution
Wait what.
The division part is absolutely mental. There is no way that looping through all the elements n times will be faster than n divisions.
This is usually a phone screen interview question :) !!
To avoid division maybe we could use logarithmic approach
Only video where I understood the solution/technique
In Javascript:
1. Without Division : `function withOutDivision(ar) {
let leftProdArray = [1], rightProdArray = [1], outputArray = [];
for (let index = 1; index < ar.length; index++) {
leftProdArray.push(leftProdArray[index - 1] * ar[index - 1])
}
for (let index = ar.length - 2; index >= 0; index--) {
rightProdArray.unshift(rightProdArray[0] * ar[index + 1])
}
leftProdArray.forEach((value, index) => {
outputArray.push(value * rightProdArray[index])
});
return outputArray;
}`
OR
2. With division :
`function withDivision(ar) {
let outputArray = [],
product = 1;
ar.forEach((value) => {
product *= value
});
ar.forEach((value) => {
outputArray.push(product / value);
});
return outputArray;
}`
Bro u need to give special care to cases where element of array is 0
In division
let tab=[12,3,11,20,19,10]
let result = []
tab.forEach(val => {
return result.push(tab.filter(val2=>val2!==val).reduce((a,b)=>a*b))
}
Would we not want to use the length call and instead check to see if the end of the array was nil and do all of that if this was in C since it’s O(n). I mean it would increase runtime by only alittle, it would still be O(n) lol.
Its just like the question of calculating area Between two towers.
can't you just calculate the total multiplication and then divide by each element ?
easy way:
int a[]={2,3,4,5};
int i,j,m=1;
for(i=0;i
O(n*2)
We can also solve this by simply taking the except element to 0th index in single loop and splitting the list from 0th index and finding the product of elements of list from first index to end, so no notation of left and right required..🙌
In that case, you won't be able to solve it on O(n) complexity.
How about this solution (Python) using a sliding window?
import numpy as np
if len(arr) == 0:
raise Exception("Invalid array")
else:
products = []
for i in range(len(arr)):
product = np.prod(arr[:i] + arr[i + 1:])
products.append(product)
return products
That's O(n^2), you're looping over the whole array for each element.
Just multiply i in a cycle unless i is equal to index of the numbee on output
I'm gonna take a stab at 2:23, before you show your solution.
create a variable total_product, set it equal to the product of all numbers in nums.
go through nums and set output[i] to total_product / nums[i]
Edit: 3:10.... I see the problem here...
power of -1 then!
what about creating a duplicate of given array and swapping the element of whose product without self is to calculate with the first element then multiplying index 1 to 4 and storing it in result array on corresponding index... then assigning resetting the previous value of duplicate array again and do it for the next element till last element to ignore dividing? pretty easy question
Check ur complexity if it is o(n) than its right....
@@gorijalakiran7132 yeah it's O(n)
How about Divide and conquer like merge sort ?
time to create my own division function
public static void main(String[] args) {
int problemArray[] ={1,2,3,4},resultArray[] = new int[4];
int resultMultiplication=1;
for(int i =0;i
What advantage does the leftproduct and rightproduct arrays provide as opposed to calculating and multiplying the elements in the list to the left and right of that index in the loop itself?
Raahel Baig time complexity. If you calculate the product of elements to the left and right of every single index (which would be necessary to be able to use your implementation), you have a time complexity of O(n^2) which is too long for the problem
Thank you for ur videos. It helps us alot. Much appreciated!!
if array element cant be 0, then this solution is faster.
int[] input = {1, 2, 3, 4};
int[] output = new int[input.length];
double temp, result = 1;
for(Integer i : input)
result *= i;
for (int i = 0; i < input.length; i++) {
temp = result * Math.pow(input[i], -1);
output[i] = (int)temp;
}
Yet again, thanks for this.
I used 2 for loops
Ok so my solution worked a lil something like this:
First multiply everything and store it
Second for every element in input array store into second array stored/element
Welp I had the same solution as him...