filmov
tv
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.
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
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
0:05:12
2D Prefix Sum and Submatrix Sum Queries
0:13:54
Maximum Sum Rectangular Submatrix in Matrix dynamic programming/2D kadane
0:08:09
Prefix Sum Array Explained
0:30:01
Number of Submatrices that Sum to Target - Leetcode 1074 - Python
0:18:32
USACO - How to do a 2D Prefix Sum in any language (C++, Python, Java, etc)
0:13:14
Prefix sum 2D array
0:08:09
The Theory Behind 2D Prefix Sums - Part 1
0:13:17
Range Sum Query 2D - Immutable - Leetcode 304 - Python
0:14:56
Generalization of Prefix Sum Concept to 1-D, 2-D Arrays and Trees
0:12:15
Submatrix Sum Queries | GeeksforGeeks
0:15:39
Range Sum Query 2D | Leetcode #304
0:17:02
Prefix Sum Differ Array 2D
0:10:43
Maximum Sum Rectangle | Extended Kadane's Algorithm | Dynamic Programming | DSA-One Course #93
0:20:51
Prefix Sums - Problems, Code in C++ & Python
0:07:43
Submatrix Sum - Problem Statement, Brute Force and Intuition
0:21:18
2D Prefix Sum Interview Pattern | 221 Maximal Square
0:11:13
8. Prefix Sum Array | 1D | 2D | Dynamic Programming
0:11:59
2D Prefix Sums | Weekly Contest 328 | Increment Submatrices by One
0:11:43
Prefix Sums 2d
0:19:40
Prefix Sum 1D and 2D Array Algorithm
0:16:36
Sum of all Submatrices
0:10:02
2D-Prefix Sum Algorithm | Competitive Programming Course | Episode 2
0:54:13
Max 1D & 2D Range Sum - Dynamic Programming
0:49:29
1074. Number of Submatrices That Sum to Target | Prefix Sums | Brute - Better - Optimal
Комментарии