This is a second-to-none explanation! It took me a while to wrap my head around this! I'd be surprised if someone is going to be able to come up with this solution in an interview without having seen it before.
@@TechWithAshishKumar a little bit optimization on brute-force will bring TC to O(N^2). Check my code: int sumOddLengthSubarrays(vector& arr) { int finalAns = 0; for(int i=0;i
Great Explanation! Spent 3 hours trying to figure out the logic behind (i + 1) *( n - i) You cleared it in 6 minutes with that city example. Now I can finally sleep after 3 am : ...... )
That is a very good explanation. By the way, you can omit the check for odd by following a simple trick. Ex. if the number is ODD; 5 --> (5+1)/2 = 3 . and if it is EVEN; 8 --> (8+1)/2 = 4. Keep doing such nice videos.
Superb explanation. I'll have to re-watch it to really nail down the thought process. You have a great way of dissecting the problem and wrote clean code! Thanks for this.
Thank you for your video, it is a great explanation, for an interview I think I'd go for the N2 approach first and if I have time I'd go for this one as I find it harder to explain, by the way if anyone is doing it in JavaScript remember to use Math.floor when dividing.
It still isn't clear why multiply at time 5:30? The arrays starting at index i are different from arrays ending at index i so how does it make sense to multiply them?
The no of ways from A - > C analogy was explained in a brute force way. I couldn't understand why would we consider counting number of ways an element starts in a subarray and ends in a subarray? can you please explain?
+1 . he just jumped right into saying that the number of occurrences for a val to appear in all possible sub-arrays is the number where val appear at start * val appear at end . but i want the reasoning as well , this is more like an observation of how to related the total count of occurrences of val in all sub-arrays to some kind of formula which is frustrating to me
@@saeedjinat9173 This is my understanding (it's a bit late if you have come up with any new ideas, i am happy to learn) The idea is to multiply the number of occurrences of each number in all the odd-length subarrays. The question is how to do that. In this video, the sub-problem is "How to count a number's occurrence in all possible subarrays". He divides the subarrays into two parts: Start with a number and End with a number (yes, think about it) For instance: how can we count how many numbers surrounding '3' 1 2 3 4 5 Instead of doing brute force, like counting layers: 2 4 -> 1 5 We count by sides: left: 1 2 (ends with 3), right: (start with 3) 4 5 -> sum them up: 4 Dividing that way won't make the two-part overlap, making it easier for calculating (just sum or multiply them up).
Really great observation and problem solving approach for this question! How did you come up with this intuition at the first place? And why does Leetcode marks it as Easy lol! :D
One quick question is, how could we prove that subarr start * subarr end = the occurence of that number in the array. I felt confused at that part. The graph you drew kinda make sense, but its still a bit abstract for me to understand.
Thanks! I think it's marked easy because the brute force solution that runs in O(n^3) works. There is a sliding window solution that runs in O(n^2) too. They could easily have the same question but with a larger input to force a more creative solution and then mark it as medium.
Thank you! That is the hardest part of the problem to understand. If you think about that city example of how many paths there are from A to C going through city B, then pretend city B is the index we are interested in. If there are A subarrays ending where we are at (B), and C subarrays beginning where we are at (B), then the total times B appears in subarrays is A*C. Here's an example: arr = [4,8,5,6,1] Let's look at how many total subarrays index 2 (value 5) is in. Index 2 will be our B. There are 3 subarrays that end with 5: [4,8,5] [8,5] and [5]. We'll call these 3 subarrays A. There are 3 subarrays that start with 5: [5] [5,6] and [5,6,1]. These 3 subarrays will be C. Looking at the first subarray in A [4,8,5], we can add every combination in C to it. [4,8,5] with [5] gives [4,8,5] [4,8,5] with [5,6] gives [4,8,5,6] [4,8,5] with [5,6,1] gives [4,8,5,6,1] Notice how all 3 subarrays of C were added to 1 of the subarrays of A? This is possible because they can be connected with B. Repeat the process for the second subarray in A [8,5]. Add every subarray in C to the second subarray in A. [8,5] with [5] gives [8,5] [8,5] with [5,6] gives [8,5,6] [8,5] with [5,6,1] gives [8,5,6,1] 3 more subarrays were created with B as the connecting index. Repeat once more for [5] (the last subarray in A). [5] with [5] gives [5] [5] with [5,6] gives [5,6] [5] with [5,6,1] gives [5,6,1] The grand total subarrays here was 3*3 = 9. I recommend drawing out an example because I find that helps it click more for me.
I beg to differ on the formula for calculating number of sub arrays!!!! Number of subarrays=n-i while the total number of element occurrences=(n-i) *(i+1).
This is a second-to-none explanation! It took me a while to wrap my head around this! I'd be surprised if someone is going to be able to come up with this solution in an interview without having seen it before.
it's 5 am IST morning now I can sleep, Thanks
Leetcode rates this as an easy problem, man. When I looked at this solution's formula in the discussion without watching this video, I was so lost
The brute force solution is accepted and is easy. The O(N) Solution is straight up HARD
@@mandy1339 brute force is o(n^3). Very bad one
+1
@@TechWithAshishKumar a little bit optimization on brute-force will bring TC to O(N^2).
Check my code:
int sumOddLengthSubarrays(vector& arr) {
int finalAns = 0;
for(int i=0;i
You can use a prefix sum array and change brute force method to O(n^2)
Great Explanation!
Spent 3 hours trying to figure out the logic behind (i + 1) *( n - i)
You cleared it in 6 minutes with that city example.
Now I can finally sleep after 3 am : ...... )
That is a very good explanation. By the way, you can omit the check for odd by following a simple trick.
Ex. if the number is ODD; 5 --> (5+1)/2 = 3 . and if it is EVEN; 8 --> (8+1)/2 = 4.
Keep doing such nice videos.
Thanks for the nice comment! You are correct, the "round up" division by 2 also works for this and even makes the code shorter.
The explanation is amazing man. Couldn't have asked for more.
Boom! Marvelous question and marvelous explanation.
This is amazing. You did a REALL GOOD job explaining it and exemplifying it wherever necessary. THANK YOU.
Wow! this is a wonderful explanation. Thanks a ton! It would be great if you do more of this kind of leetcode solution
It was a great explanation, I derived sum of all even length subarrays based on this intuition. Thanks a ton dude !!
Such a great explanation! It’s so clear ❤❤❤❤
Extremely perfect explanation 🎉
Superb explanation. I'll have to re-watch it to really nail down the thought process. You have a great way of dissecting the problem and wrote clean code! Thanks for this.
Ain't no way I'm coming up with that in an interview.
Wow. Just wow. Your channel is super underrated and I hope you grow way bigger because it's definitely well deserved
Amazing explanation! Many thanks! Keep doing what you're doing.
Nice Explanation
Really great explanation Nate! Was able to figure out the brute force solution but this one is really elegant
Explanation was Fire 🔥🔥🔥
Grate explanation!!!! I got it on the middle of video👍
Please continue posting....your way of solving problem is really helpful
This solution is just more than perfect!
I am just wondering how deep you went finding it!!!
This is an incredible explanation brother !!! Keep it up.
Phenomenal,
Hoping to see more videos from you
Thanks a lot
Thanks for explaining thought process behind the solution.
Your videos are indeed amazing . Please keep uploading...
Really well explained man. Lots of thanks you saved much of my time.
Thank you for your video, it is a great explanation, for an interview I think I'd go for the N2 approach first and if I have time I'd go for this one as I find it harder to explain, by the way if anyone is doing it in JavaScript remember to use Math.floor when dividing.
This is mind-blowing. Thanks.
I can't thank you enough. 🙌
Simple and easy explanation, Great!
Fantastic explanation!
I appreciate your efforts.
Really very good clarification of complex concept.
subscribed :)
best solution for beginners thank you 😄
Thanks for this clear explanation. Goog Job ;)
Thank You. The explanation was very good.
It still isn't clear why multiply at time 5:30? The arrays starting at index i are different from arrays ending at index i so how does it make sense to multiply them?
Really great explanation❤
Why do we use paths to represent (n-i) and (i+1) as opposed to just adding them?
Bruh this is very helpful. Thank you.
Thanks a lot bro:-) Much needed, deserves subscription:)
could not get any better than this
thanks a lot. your video helped me so much in understanding this solution.
thanks for saving my day. 😊
Amazing explanation. Thank you.
at minute 7:22 how is the answer 4 you said (1,2) ( 1,2,3) (1,2,3,4) shouldnt it be 3 ? or we add (1) so it becomes 4 ?
Great explanation Thank you 😊👍
bro, you are the best
That's really a great explanation..thanks
Great Explanation bro!!!!!!!😁😁😁😁
excellent solution
really good explanation
i did not understand the even and odd part ..could someone explain plz..after the total how did he get the odd ones
thank you for the solution and video.
Kudos to the amazing explanation. But still wondering how did you come up with this solution.
The no of ways from A - > C analogy was explained in a brute force way. I couldn't understand why would we consider counting number of ways an element starts in a subarray and ends in a subarray? can you please explain?
+1 . he just jumped right into saying that the number of occurrences for a val to appear in all possible sub-arrays is the number where val appear at start * val appear at end . but i want the reasoning as well , this is more like an observation of how to related the total count of occurrences of val in all sub-arrays to some kind of formula which is frustrating to me
@@saeedjinat9173 This is my understanding (it's a bit late if you have come up with any new ideas, i am happy to learn)
The idea is to multiply the number of occurrences of each number in all the odd-length subarrays. The question is how to do that. In this video, the sub-problem is "How to count a number's occurrence in all possible subarrays". He divides the subarrays into two parts: Start with a number and End with a number (yes, think about it)
For instance: how can we count how many numbers surrounding '3'
1 2 3 4 5
Instead of doing brute force, like counting layers: 2 4 -> 1 5
We count by sides: left: 1 2 (ends with 3), right: (start with 3) 4 5 -> sum them up: 4
Dividing that way won't make the two-part overlap, making it easier for calculating (just sum or multiply them up).
Thank you. Very well explained.
Wonderfull Thank you so much!
Excellent video
This is genius!
Really great observation and problem solving approach for this question! How did you come up with this intuition at the first place? And why does Leetcode marks it as Easy lol! :D
Deserver to be subscribed but don't understand one thing why the hell leetcode call it easy problem
awesome bro
Awesome !!
Great video
How did you come up with the solution? seems like its not any pattern?
Great explanation, thanks
awesome explanation
just awsm!! explanation.....btw why did you stopped making contents?
One quick question is, how could we prove that subarr start * subarr end = the occurence of that number in the array. I felt confused at that part. The graph you drew kinda make sense, but its still a bit abstract for me to understand.
He explained in reply to another comment.
yea it is a bit complicated.....think about it for some while....watch the video again from that part...you'll get it.
Can you explain your thought process on solving these kind of problems, Its really hard to get an proper idea about a better solution.
yess
Amazing video
Great Video! But not sure why it's marked as Easy on LeetCode..
Thanks! I think it's marked easy because the brute force solution that runs in O(n^3) works. There is a sliding window solution that runs in O(n^2) too. They could easily have the same question but with a larger input to force a more creative solution and then mark it as medium.
we can simply divide (total+1)/2 simple there is no need to put if statement
why is half of the subarrays be odd size and the half be even size?
i don't understand why you skip it tho. it doesn't sound trivial to me.
Hi, great video!
Your method is very interesting although it`s kinda hard to understand, why total number of subbarays = start * finish.
Thank you! That is the hardest part of the problem to understand. If you think about that city example of how many paths there are from A to C going through city B, then pretend city B is the index we are interested in.
If there are A subarrays ending where we are at (B), and C subarrays beginning where we are at (B), then the total times B appears in subarrays is A*C.
Here's an example: arr = [4,8,5,6,1]
Let's look at how many total subarrays index 2 (value 5) is in. Index 2 will be our B.
There are 3 subarrays that end with 5: [4,8,5] [8,5] and [5]. We'll call these 3 subarrays A.
There are 3 subarrays that start with 5: [5] [5,6] and [5,6,1]. These 3 subarrays will be C.
Looking at the first subarray in A [4,8,5], we can add every combination in C to it.
[4,8,5] with [5] gives [4,8,5]
[4,8,5] with [5,6] gives [4,8,5,6]
[4,8,5] with [5,6,1] gives [4,8,5,6,1]
Notice how all 3 subarrays of C were added to 1 of the subarrays of A? This is possible because they can be connected with B.
Repeat the process for the second subarray in A [8,5]. Add every subarray in C to the second subarray in A.
[8,5] with [5] gives [8,5]
[8,5] with [5,6] gives [8,5,6]
[8,5] with [5,6,1] gives [8,5,6,1]
3 more subarrays were created with B as the connecting index.
Repeat once more for [5] (the last subarray in A).
[5] with [5] gives [5]
[5] with [5,6] gives [5,6]
[5] with [5,6,1] gives [5,6,1]
The grand total subarrays here was 3*3 = 9.
I recommend drawing out an example because I find that helps it click more for me.
@@natesantti906 thank you for clarification. It really helped me understand solution much better!
Keep up the good work!
@@natesantti906 thanks a lot, I finally understand
@@natesantti906 Thanks a lot this was very intuitive
@@natesantti906 thank you for clear explanation! OMG!
thanks!
I beg to differ on the formula for calculating number of sub arrays!!!! Number of subarrays=n-i while the total number of element occurrences=(n-i) *(i+1).
Great explanation, it's not in any way easy question.
wow
Great explanation