You have stated the reason why prefix sum is better than the naive approach, but not provided the reason why the algorithm must be learned. I know of 2 applications, line of sight analysis and creating cumulative images for image processing. What other applications make this relevant as more than just a test exercise?
Find this list on little bit of googling, I hope it help :) The uses of the all-prefix-sums operation are extensive. Here is a list of some of them: 1. To lexically compare strings of characters. For example, to determine that "strategy" should appear before "stratification" in a dictionary (see Problem 2). 1.1 Introduction 37 2. To add multi precision numbers. These are numbers that cannot be represented in a single machine word (see Problem 3). 3. To evaluate polynomials (see Problem 6). 4. To solve recurrences. For example, to solve the recurrences xi = aixi−1 + bixi−2 and xi = ai + bi/xi−1 (see Section 1.4). 5. To implement radix sort (see Section 1.3). 6. To implement quicksort (see Section 1). 7. To solve tridiagonal linear systems (see Problem 12). 8. To delete marked elements from an array (see Section 1.3). 9. To dynamically allocate processors (see Section 1.6). 10. To perform lexical analysis. For example, to parse a program into tokens. 11. To search for regular expressions. For example, to implement the UNIX grep program. 12. To implement some tree operations. For example, to find the depth of every vertex in a tree (see Chapter 3). 13. To label components in two dimensional images complete PDF can be find here- www.cs.cmu.edu/~guyb/papers/Ble93.pdf
If you are given a binary tree and a target value and you are asked to find the nodes that sum up to the target value. The brute force solution to this is O(N^2) because you are going to visit each node and on each node you are going to check of any of the previous nodes + visiting node is equal to the given target. So traversing tree = O(N) and finding if any previous node sum + current node = target is also O(N). But using Prefix sum this time complexity can be reduced to O(N).
2:59 why there is a outer loop since all queries have different input so to calculate sum for each query we have to run the for loop for each query all the for loop will be execute for n times in worst case for m queries so the complexity will be m*O(n) why it is O(m*n) ? Please clarify my doubts.
Hi Akash, I can see you have two separate queries so let me take it one by one. 1) some time you will get bunch of queries which you need to perform of n size input array. if you do one by one (which is fairly possible) but for each and individual query you need to process the array every time or at max O(n) time for n size array. but there is way to save the execution time by pre-processing the array only once (irrespective of query size). for example checkout this problem with multiple queries--> www.hackerrank.com/challenges/crush/problem 2) If we treat n as function complexity is O(n). similarly here m is a query size, if you treat it like a function then it will be O(m*n) or if you treat it as a scaler quantity then it will be m*O(n). but over all result will be same. because for each query you may end up process at max O(n).
Hello Coding Lover,
If you have any doubts , please let me know in comments.
Nice one most of the time i used traditional one 😅
Whenever you upload that video just notify me
Thanks Mayur.
Make sure you have subscribed and press the bell icon to get the notification instantly.
@@JavaAidTutorials all set 👍
@@mayurkadam cool (Y)
Easy explanation
Great job .
Glad you liked it
just prefect .. keep it on man
Thanks a lot!
Really a great video sir!! thanks a lot!
So nice of you
great introduction to the topic
sir please make full dsa course
awesome explanation
You have stated the reason why prefix sum is better than the naive approach, but not provided the reason why the algorithm must be learned. I know of 2 applications, line of sight analysis and creating cumulative images for image processing. What other applications make this relevant as more than just a test exercise?
Find this list on little bit of googling, I hope it help :)
The uses of the all-prefix-sums operation are extensive. Here is a list of some of them:
1. To lexically compare strings of characters. For example, to determine that "strategy" should appear before "stratification" in
a dictionary (see Problem 2).
1.1 Introduction 37
2. To add multi precision numbers. These are numbers that cannot
be represented in a single machine word (see Problem 3).
3. To evaluate polynomials (see Problem 6).
4. To solve recurrences. For example, to solve the recurrences
xi = aixi−1 + bixi−2 and xi = ai + bi/xi−1 (see Section 1.4).
5. To implement radix sort (see Section 1.3).
6. To implement quicksort (see Section 1).
7. To solve tridiagonal linear systems (see Problem 12).
8. To delete marked elements from an array (see Section 1.3).
9. To dynamically allocate processors (see Section 1.6).
10. To perform lexical analysis. For example, to parse a program into
tokens.
11. To search for regular expressions. For example, to implement the
UNIX grep program.
12. To implement some tree operations. For example, to find the depth
of every vertex in a tree (see Chapter 3).
13. To label components in two dimensional images
complete PDF can be find here-
www.cs.cmu.edu/~guyb/papers/Ble93.pdf
If you are given a binary tree and a target value and you are asked to find the nodes that sum up to the target value. The brute force solution to this is O(N^2) because you are going to visit each node and on each node you are going to check of any of the previous nodes + visiting node is equal to the given target. So traversing tree = O(N) and finding if any previous node sum + current node = target is also O(N). But using Prefix sum this time complexity can be reduced to O(N).
Thanks for the lesson. I think to be more precise the Prefix Sum Algorithm takes O(m+n) not just O(n).
its more or less the same
hello sir.. can you please make a video on the problem append and delete from hackerrank.
will upload stay tuned..!!
ok sir
thanks a lot
2:59 why there is a outer loop since all queries have different input so to calculate sum for each query we have to run the for loop for each query all the for loop will be execute for n times in worst case for m queries so the complexity will be m*O(n) why it is O(m*n) ?
Please clarify my doubts.
Hi Akash,
I can see you have two separate queries so let me take it one by one.
1) some time you will get bunch of queries which you need to perform of n size input array. if you do one by one (which is fairly possible) but for each and individual query you need to process the array every time or at max O(n) time for n size array.
but there is way to save the execution time by pre-processing the array only once (irrespective of query size).
for example checkout this problem with multiple queries--> www.hackerrank.com/challenges/crush/problem
2) If we treat n as function complexity is O(n). similarly here m is a query size, if you treat it like a function then it will be O(m*n) or if you treat it as a scaler quantity then it will be m*O(n). but over all result will be same. because for each query you may end up process at max O(n).
Thank you so much!!
Most welcome..:😊
Most welcome..:😊
Most welcome..:😊
Thank you for video 😋Fully watched till the end LIKE 👍hmm interesting video 👌♥️ enjoyed it please connect mee friends👌
Thank you :)
you can connect me on various social media, just have a look on video description
any motivation i am doing array from last 5 days and i am so bore from this
I am doing more than 5 year.. :) 😀
neeed code attachment plz
Are you talking about the slides? or something else