What is the brute force approach and complexity for Range Sum Query 2D – Immutable?

Keep the grid; each query loops over every cell in the rectangle with time complexity O(R · C) and space complexity O(m · n).

What is the optimal approach and complexity for Range Sum Query 2D – Immutable?

Corner-block totals in an (m+1)×(n+1) table; each query is 4 lookups with optimal time complexity O(1) and space complexity O(m · n).

Range Sum Query 2D – Immutable

Q: How do you identify the pattern for Range Sum Query 2D – Immutable?

Look for key signals in the prompt: "grid never changes" indicates Totals computed once stay correct → precompute.; "many rectangle-sum queries" indicates Spend O(m · n) once so each query is O(1).; "sum of a rectangle" indicates 2D range sum = combination of blocks that start at (0, 0).; "O(1) per query" indicates A prefix per row (O(rows)) is not enough — you need the full 2D table..

Medium·LeetCode #304 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given a 2D grid of integers matrix that never changes. After that, you will be asked many questions of the form "what is the sum of every cell inside this rectangle?" A rectangle is given by its top-left corner (row1, col1) and its bottom-right corner (row2, col2), both included.

Write a class NumMatrix:

NumMatrix(vector<vector<int>>& matrix) receives the grid once.
int sumRegion(int row1, int col1, int row2, int col2) returns the sum of matrix[r][c] for all row1 ≤ r ≤ row2 and col1 ≤ c ≤ col2.

Each query must run in O(1) time.

Input

The grid matrix (given once, to the constructor), followed by many calls sumRegion(row1, col1, row2, col2).

Output

For each sumRegion call, the sum of all cells inside that rectangle.

Example 1

Input: 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]] sumRegion(2,1,4,3), sumRegion(1,1,2,2), sumRegion(1,2,2,4)

Output: 8, 11, 12

Rows 2–4, columns 1–3: (2+0+1) + (1+0+1) + (0+3+0) = 8. Rows 1–2, columns 1–2: 6+3+2+0 = 11. Rows 1–2, columns 2–4: 3+2+1+0+1+5 = 12.

Constraints

• 1 ≤ m, n ≤ 200 (m rows, n columns)
• −10^4 ≤ matrix[i][j] ≤ 10^4
• 0 ≤ row1 ≤ row2 < m and 0 ≤ col1 ≤ col2 < n
• At most 10^4 calls to sumRegion
• The largest total is 200 · 200 · 10^4 = 4·10^8, so `int` is enough.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“grid never changes”

→ Totals computed once stay correct → precompute.

“many rectangle-sum queries”

→ Spend O(m · n) once so each query is O(1).

“sum of a rectangle”

→ 2D range sum = combination of blocks that start at (0, 0).

“O(1) per query”

→ A prefix per row (O(rows)) is not enough — you need the full 2D table.

Approach Complexity Ladder

Brute Force — add every cell of the rectangleO(R · C)O(m · n)

Keep the grid; each query loops over every cell in the rectangle

Better — one 1D prefix per rowO(R)O(m · n)

Prefix sum for every row; a query adds one O(1) row-sum per row

Optimal — 2D prefix sum (inclusion–exclusion)O(1)O(m · n)

Corner-block totals in an (m+1)×(n+1) table; each query is 4 lookups

Brute Force Intuition

Store the grid. For each query, loop over the rows row1..row2 and, inside, the columns col1..col2, and add every cell.

Recognition rule for this sub-pattern:

Many range-sum questions on data that never changes. Build prefix once, answer each query in O(1).

Remember this · Prefix Sum

Trigger

Range sums, "subarray sum equals K" (especially with negatives), equal counts, divisible by K.

Think

If I knew the total up to every index, would the answer become a difference of two totals?

Key question

Which earlier prefix value am I looking for when I stand at index i?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Prefix Sum translate into production architectures and low-level memory mechanics.

LLD Architecture