Prefix Sum Algorithm | Prefix Sum Array Implementation | EP2

Prefix sum algorithm is mainly used for range query and the complexity of prefix sum algorithm is O(n).
This video explains the working of prefix sum algorithm.
This is the second part of the video and please watch the first part (why you must learn prefix sum algorithm) before watching this.

✅ Why you must learn prefix sum algorithm part one link : https://youtu.be/scD312I7kkE

 Subscribe for more and hit the bell  icon to get video updates:
https://www.youtube.com/channel/UCx1hbK753l3WhwXP5r93eYA?sub_confirmation=1

 Like us on Facebook: https://www.facebook.com/HackerRankSolutionTutorials

Share this video with a YouTuber friend: https://youtu.be/pVS3yhlzrlQ

✚ Join our community ►

 Coding interview preparation group: https://www.facebook.com/groups/codingip
 Telegram link: https://t.me/hackerranksolutions


✅ Recommended playlists ►

 All hackerrank solutions: https://www.youtube.com/watch?v=oz_yowFTrgs&list=PLSIpQf0NbcCltzNFrOJkQ4J4AAjW3TSmA

 Let’s Connect ►

Git Hub: https://github.com/kanahaiya
Twitter: https://twitter.com/Kanahaiyagupta
Linked in: https://www.linkedin.com/in/kanahaiya-gupta
Facebook: https://www.facebook.com/coolkanahaiya
Instagram: https://www.instagram.com/coolkanahaiya




#JAVAAID #HackerRankSolutions #HackerRankTutorials #implementation #prefixsum #HackerRank #JavaAidTutorials #Programming #DataStructures #algorithms #coding #competitiveprogramming #JavaAidTutorials #Java #codinginterview #problemsolving #KanahaiyaGupta #hackerrankchallenges

1. Prefix sum It is a simple yet powerful technique that allows to perform fast calculation on the sum of elements in a given range (called contiguous segments of array).

2. Prefix sum It is a simple yet powerful technique that allows to perform fast calculation on the sum of elements in a given range (called contiguous segments of array). 6 3 -2 4 -1 -5 Example - A[ ] =

3. Prefix sum It is a simple yet powerful technique that allows to perform fast calculation on the sum of elements in a given range (called contiguous segments of array). 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 A[ ] =

4. Prefix sum It is a simple yet powerful technique that allows to perform fast calculation on the sum of elements in a given range (called contiguous segments of array). 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] =

5. Prefix sum 6 3 -2 4 -1 -5 0 1 2 3 4 5 6 6 9 -2 4 -1 -5 6 9 7 4 -1 -5 6 9 7 11 -1 -5 6 9 7 11 10 -5 6 9 7 11 10 10 5 6 9 7 11 10 10 -5 Example - i = A[ ] =

6. Prefix sum 6 3 -2 4 -1 -5 0 1 2 3 4 5 6 6 9 -2 4 -1 -5 6 9 7 4 -1 -5 6 9 7 11 -1 -5 6 9 7 11 10 -5 6 9 7 11 10 10 5 6 9 7 11 10 10 -5 for( int i= 1 ; i< 7 ; i++ ){ A[i] = A[i]+A[i-1]; } n Example - i = A[ ] =

7. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] = i = 0 1 2 3 4 5 6

8. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = i = 0 1 2 3 4 5 6

9. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = i = 0 1 2 3 4 5 6

10. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = Ans : 10 (=A[4]) O (1) i = 0 1 2 3 4 5 6

11. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = Ans : 10 (=A[4]) O (1) Calculate the sum between range [ 0, 6 ] ? i = 0 1 2 3 4 5 6

12. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = Ans : 10 (=A[4]) O (1) Calculate the sum between range [ 0, 6 ] ? i = 0 1 2 3 4 5 6

13. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = Ans : 10 (=A[4]) O (1) Calculate the sum between range [ 0, 6 ] ? Ans : 5 (=A[6]) O (1) i = 0 1 2 3 4 5 6

14. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = Ans : 10 (=A[4]) O (1) Calculate the sum between range [ 0, 6 ] ? Ans : 5 (=A[6]) O (1) Calculate the sum between range [ 2, 6 ] ? i = 0 1 2 3 4 5 6

15. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = Ans : 10 (=A[4]) O (1) Calculate the sum between range [ 0, 6 ] ? Ans : 5 (=A[6]) O (1) Calculate the sum between range [ 2, 6 ] ? sum between range [ 0, 6 ] i = 0 1 2 3 4 5 6

16. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = Ans : 10 (=A[4]) O (1) Calculate the sum between range [ 0, 6 ] ? Ans : 5 (=A[6]) O (1) Calculate the sum between range [ 2, 6 ] ? sum between range [ 0, 6 ] sum between range [ 0, 6 ] = sum between range [ 2, 6 ] sum between range [ 0, 1 ] + i = 0 1 2 3 4 5 6

17. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = Ans : 10 (=A[4]) O (1) Calculate the sum between range [ 0, 6 ] ? Ans : 5 (=A[6]) O (1) Calculate the sum between range [ 2, 6 ] ? sum between range [ 0, 6 ] sum between range [ 0, 6 ] = sum between range [ 2, 6 ] sum between range [ 0, 1 ] + A[ 6 ] = A[ 1 ] + sum between range [ 2, 6 ] A[ 6 ] - A[ 1 ] = sum between range [ 2, 6 ] i = 0 1 2 3 4 5 6

18. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = Ans : 10 (=A[4]) O (1) Calculate the sum between range [ 0, 6 ] ? Ans : 5 (=A[6]) O (1) Calculate the sum between range [ 2, 6 ] ? sum between range [ 0, 6 ] sum between range [ 0, 6 ] = sum between range [ 2, 6 ] sum between range [ 0, 1 ] + A[ 6 ] = A[ 1 ] + sum between range [ 2, 6 ] A[ 6 ] - A[ 1 ] = sum between range [ 2, 6 ] sum between range [ 2, 6 ] = A[ 6 ] - A[ 1 ] i = 0 1 2 3 4 5 6

19. Prefix sum 6 3 -2 4 -1 -5 Example - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - Calculate the sum between range [ 0, 4 ] ? A[ ] = A[ ] = Ans : 10 (=A[4]) O (1) Calculate the sum between range [ 0, 6 ] ? Ans : 5 (=A[6]) O (1) Calculate the sum between range [ 2, 6 ] ? sum between range [ 0, 6 ] sum between range [ 0, 6 ] = sum between range [ 2, 6 ] sum between range [ 0, 1 ] + A[ 6 ] = A[ 1 ] + sum between range [ 2, 6 ] A[ 6 ] - A[ 1 ] = sum between range [ 2, 6 ] sum between range [ 2, 6 ] = A[ 6 ] - A[ 1 ] sum between range [ 2, 6 ] = 5 - 9 sum between range [ 2, 6 ] = - 4 i = 0 1 2 3 4 5 6

20. Prefix sum 6 3 -2 4 -1 -5 Generalization - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] = i = 0 1 2 3 4 5 6

21. Prefix sum 6 3 -2 4 -1 -5 Generalization - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] = i = 0 1 2 3 4 5 6 A[ 2 , 6 ]

22. Prefix sum 6 3 -2 4 -1 -5 Generalization - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] = i = 0 1 2 3 4 5 6 A[ 6 ] A[ 2 , 6 ]

23. Prefix sum 6 3 -2 4 -1 -5 Generalization - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] = i = 0 1 2 3 4 5 6 A[ 1 ] A[ 6 ] A[ 1 ] A[ 2 , 6 ]

24. Prefix sum 6 3 -2 4 -1 -5 Generalization - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] = i = 0 1 2 3 4 5 6 A[ 2 , 6 ] = A[ 6 ] - A[ 1 ] A[ 6 ] A[ 1 ] A[ 2 , 6 ]

25. Prefix sum 6 3 -2 4 -1 -5 Generalization - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] = i = 0 1 2 3 4 5 6 To calculate the sum between range [ I , j ] A[ 2 , 6 ] = A[ 6 ] - A[ 1 ] A[ 6 ] A[ 1 ] A[ 2 , 6 ]

26. Prefix sum 6 3 -2 4 -1 -5 Generalization - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] = i = 0 1 2 3 4 5 6 Formula - To calculate the sum between range [ I , j ] A[ 2 , 6 ] = A[ 6 ] - A[ 1 ] A[i, j] = A[j] - A[i - 1 ] A[ 6 ] A[ 1 ] A[ 2 , 6 ]

27. Prefix sum 6 3 -2 4 -1 -5 Generalization - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] = i = 0 1 2 3 4 5 6 Formula - To calculate the sum between range [ I , j ] A[ 2 , 6 ] = A[ 6 ] - A[ 1 ] Calculate the sum between range [ 3, 5 ] ? A[i, j] = A[j] - A[i - 1 ] A[ 6 ] A[ 1 ] A[ 2 , 6 ]

28. Prefix sum 6 3 -2 4 -1 -5 Generalization - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] = i = 0 1 2 3 4 5 6 Formula - To calculate the sum between range [ I , j ] A[ 2 , 6 ] = A[ 6 ] - A[ 1 ] Calculate the sum between range [ 3, 5 ] ? A[ 3, 5 ] = A[ 5 ] - A[ 3 - 1 ] A[ 3, 5 ] = A[ 5 ] - A[ 2 ] A[ 3, 5 ] = 10 - 7 A[ 3, 5 ] = 3 A[i, j] = A[j] - A[i - 1 ] A[ 6 ] A[ 1 ] A[ 2 , 6 ]

29. Prefix sum 6 3 -2 4 -1 -5 Generalization - i = 0 1 2 3 4 5 6 6 9 7 11 10 10 5 Prefix Sum Array - A[ ] = A[ ] = i = 0 1 2 3 4 5 6 A[ 6 ] A[ 1 ] A[ 2 , 6 ] Formula - To calculate the sum between range [ I , j ] A[ 2 , 6 ] = A[ 6 ] - A[ 1 ] Calculate the sum between range [ 3, 5 ] ? A[ 3, 5 ] = A[ 5 ] - A[ 3 - 1 ] A[ 3, 5 ] = A[ 5 ] - A[ 2 ] A[ 3, 5 ] = 10 - 7 A[ 3, 5 ] = 3 O(1) A[i, j] = A[j] - A[i - 1 ]

30. To calculate prefix sum array of n size array Time complexity - O(n) Analysis of Algorithm - Time taken to perform range sum query is - Time complexity - O(1)

31. Analysis of Algorithm - Total time taken to pre process the n size array and to perform range query is - Time complexity - + O(1) O(n) ~ O(n) To calculate prefix sum array of n size array Time complexity - O(n) Time taken to perform range sum query is - Time complexity - O(1)

32. It takes O(n) time to calculate prefix sum array of n size array. Key takeaway from this lesson - It takes O(1) time to perform range sum query on n size array.

33. Here is the link to video tutorial :- https://youtu.be/pVS3yhlzrlQ