2D Prefix Sum¶
Table of Contents¶
- 304. Range Sum Query 2D - Immutable (Medium)
- 1314. Matrix Block Sum (Medium)
- 3070. Count Submatrices with Top-Left Element and Sum Less Than k (Medium)
- 1738. Find Kth Largest XOR Coordinate Value (Medium)
- 3212. Count Submatrices With Equal Frequency of X and Y (Medium)
- 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold (Medium)
- 221. Maximal Square (Medium)
- 1277. Count Square Submatrices with All Ones (Medium)
- 1504. Count Submatrices With All Ones (Medium)
- 1074. Number of Submatrices That Sum to Target (Hard)
- 3148. Maximum Difference Score in a Grid (Medium)
304. Range Sum Query 2D - Immutable¶
from typing import List
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
m, n = len(matrix), len(matrix[0])
if m == 0 or n == 0:
return None
self.sum = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
self.sum[i][j] = (
matrix[i - 1][j - 1]
+ self.sum[i - 1][j]
+ self.sum[i][j - 1]
- self.sum[i - 1][j - 1] # to avoid double counting
)
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return (
self.sum[row2 + 1][col2 + 1]
- self.sum[row1][col2 + 1]
- self.sum[row2 + 1][col1]
+ self.sum[row1][col1]
)
matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5],
]
obj = NumMatrix(matrix)
assert obj.sumRegion(2, 1, 4, 3) == 8
assert obj.sumRegion(1, 1, 2, 2) == 11
assert obj.sumRegion(1, 2, 2, 4) == 12
print("PASSED")
1314. Matrix Block Sum¶
3070. Count Submatrices with Top-Left Element and Sum Less Than k¶
1738. Find Kth Largest XOR Coordinate Value¶
-
Tags: Array, Divide And Conquer, Bit Manipulation, Sorting, Heap Priority Queue, Matrix, Prefix Sum, Quickselect