#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/prefix-sum/range-sum-query-2d-immutable-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/prefix-sum/range-sum-query-2d-immutable-implementation

Repovive

LeetCode 304 Range Sum Query 2D - Immutable - Implementation - Prefix Sum | Pattern 22: LeetCode Interview Patterns | Repovive

Repovive.

Pattern 22: LeetCode Interview Patterns24 sections · 736 units32h total

Open in Course

LeetCode 304 Range Sum Query 2D - Immutable - Implementation

The approach

Build 2D prefix sums in constructor. Answer queries with inclusion-exclusion.

class NumMatrix: function init(matrix): m, n = len(matrix), len(matrix[0]) self.prefix = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m): for j in range(n): self.prefix[i+1][j+1] = (matrix[i][j] + self.prefix[i][j+1] + self.prefix[i+1][j] - self.prefix[i][j])

function sumRegion(r1, c1, r2, c2):
    return (self.prefix[r2+1][c2+1]
        - self.prefix[r1][c2+1]
        - self.prefix[r2+1][c1]
        + self.prefix[r1][c1])

$O(mn)$ preprocessing, $O(1)$ per query, $O(mn)$ space.