2D Prefix Sum and Submatrix Sum Queries

A 2-dimensional prefix sum is a powerful algorithmic technique used in computer science and mathematics to preprocess a given 2D grid or matrix, enabling efficient querying of summed values over rectangular subregions. In essence, it is an extension of the 1-dimensional prefix sum to two dimensions. This method involves constructing an auxiliary matrix of the same dimensions as the original, where each cell (i, j) contains the sum of all elements in the rectangular region formed by the top-left corner (0, 0) and the current position (i, j). Once this preprocessing is complete, the sum of any rectangular subregion can be calculated with only four array lookups and three arithmetic operations, significantly reducing the time complexity of repeated queries.
💻 Practice: profound.academy/algorithms-d...
📚 Full DSA Course: profound.academy/algorithms-d...
🎓 Teach with Profound Academy: profound.academy/teach
profound.academy
/ profound.academy.inc
/ profound.academy.inc
/ profound-academy-inc
Chapters:
0:00 2D Prefix Sum and Submatrix Sum Queries Problem Statement
0:19 Example Matrix
0:39 2D Prefix Sum
0:57 Submatrix Sum Query
2:05 Trick of Padding the Array With Zeros
2:29 2D Prefix Sum Array Calculation
3:26 Hands-on Practice on Profound Academy
3:37 Algorithm in Action
4:41 Time and Memory Complexity
#PrefixSum #Algorithm #DataStructures #2dPrefixSum #Algorithms #ProblemSolving #AlgorithmicInterview #InterviewPreparation #DataStructuresInterview #InterviewQuestions #TechInterview #TechInterviews #DSA #GoogleInterview #FAANG #Algorithms

[@karenmirakyan1610]

Well explained, waiting for other videos 👍

[@user-vz7wd9fh3c]

Perfect illustration

[@helloomkar]

Perfect explanation and viz needed for this concept. Glad i came to your video🎉🎉

[@HaykTarkhanyan]

Awesome, keep it up

[@florinseiler3764]

Awesome video! Helped a lot

[@DK-ox7ze]

What's the logic behind calculating prefix sum for each cell? What's the intuition behind the formula you used?

[@shashankbj3804]

You should watch it again its in the video..