In many grid-based problems, we are asked to perform multiple updates on rectangular submatrices of a 2D array. A direct approach would be to iterate over each cell within the rectangle for every update, which leads to a time complexity of O(k × n × m) for k updates too slow for large inputs.
To handle such cases efficiently, we use a technique called the 2D Difference Array. It is an extension of the 1D difference array, designed for grids. Instead of updating every cell in a submatrix individually, we update just four corners in a helper matrix. Later, we reconstruct the final values using prefix sums.
This allows each range update to be applied in constant time, and the final matrix to be computed in O(n × m) time.
Table of Content
How 2D Difference Array Works
To update a submatrix from (r1, c1) to (r2, c2) with a value v, we use a helper matrix diff[][] instead of updating every cell.
We perform these 4 operations in constant time:
Try it on GfG Practice
diff[r1][c1] += v;
diff[r2 + 1][c1] -= v;
diff[r1][c2 + 1] -= v;
diff[r2 + 1][c2 + 1] += v;
Then, we compute prefix sums over diff[][] to get the final matrix. Only the target submatrix reflects the added value fast and efficient.
Example:
Given a 2D integer matrix mat[][] and a list of operations opr[][]. Each operation is represented as a list of the form [v, r1, c1, r2, c2], where:
- v is the value to be added,
- (r1, c1) is the top-left coordinate of a submatrix, and
- (r2, c2) is the bottom-right coordinate of the submatrix (both inclusive).
Return the final matrix after all operations.
Step By Step Implementations:
- Create a diff[][] matrix of size n × m initialized with zeros. This matrix will store increment/decrement markers to indicate where the effect of v should begin or end.
- For each query [v, r1, c1, r2, c2], perform the following 4 operations:
=> diff[r1][c1] += v;
=> diff[r1][c2 + 1] -= v; (if c1 + 1 is less than n)
=> diff[r2 + 1][c1] -= v; ( if r2 + 1 is less than m)
=> diff[r2 + 1][c2 + 1] += v; ( r2 + 1 is less than n and c1 + 1 is less than m ) - Take row wise prefix sum i.e, for each i => diff[i][j] += diff[i][j-1]
- Take column wise prefix sum i.e, for each j => diff[i][j] += diff[i-1][j]
- Now apply the net updates from diff back to the original matrix (i.e., mat[i][j] += diff[i][j]).
Illustrations:
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> applyDiff2D(vector<vector<int>>& mat,
vector<vector<int>>& opr) {
int n = mat.size();
int m = mat[0].size();
// diff matrix of size n x m
vector<vector<int>> diff(n, vector<int>(m, 0));
// apply all operations using 4-point updates
for (auto& q : opr) {
int v = q[0];
int r1 = q[1], c1 = q[2], r2 = q[3], c2 = q[4];
// top-left -> add
diff[r1][c1] += v;
// top-right -> subtract
if (c2 + 1 < m) diff[r1][c2 + 1] -= v;
// bottom-left -> subtract
if (r2 + 1 < n) diff[r2 + 1][c1] -= v;
// bottim-right -> add
if (r2 + 1 < n && c2 + 1 < m) diff[r2 + 1][c2 + 1] += v;
}
// row-wise prefix sum
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
diff[i][j] += diff[i][j - 1];
}
}
// column-wise prefix sum
for (int j = 0; j < m; j++) {
for (int i = 1; i < n; i++) {
diff[i][j] += diff[i - 1][j];
}
}
// apply diff to original matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
mat[i][j] += diff[i][j];
}
}
return mat;
}
int main() {
vector<vector<int>> mat = {
{1, 2, 3},
{1, 1, 0},
{4, -2, 2}
};
vector<vector<int>> opr = {
{2, 0, 0, 1, 1},
{-1, 1, 0, 2, 2}
};
vector<vector<int>> res = applyDiff2D(mat, opr);
for (auto& row : mat) {
for (int val : row) cout << val << " ";
cout << endl;
}
return 0;
}
class GfG {
public static int[][] applyDiff2D(int[][] arr, int[][] opr) {
int n = arr.length;
int m = arr[0].length;
// diff matrix of size n x m
int[][] diff = new int[n][m];
// apply all operations using 4-point updates
for (int[] q : opr) {
int v = q[0];
int r1 = q[1], c1 = q[2], r2 = q[3], c2 = q[4];
// top-left -> add
diff[r1][c1] += v;
// top-right -> subtract
if (c2 + 1 < m) diff[r1][c2 + 1] -= v;
// bottom-left -> subtract
if (r2 + 1 < n) diff[r2 + 1][c1] -= v;
// bottom-right -> add
if (r2 + 1 < n && c2 + 1 < m) diff[r2 + 1][c2 + 1] += v;
}
// row-wise prefix sum
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
diff[i][j] += diff[i][j - 1];
}
}
// column-wise prefix sum
for (int j = 0; j < m; j++) {
for (int i = 1; i < n; i++) {
diff[i][j] += diff[i - 1][j];
}
}
// apply diff to original matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] += diff[i][j];
}
}
return arr;
}
public static void main(String[] args) {
int[][] arr = {
{1, 2, 3},
{1, 1, 0},
{4, -2, 2}
};
int[][] opr = {
{2, 0, 0, 1, 1},
{-1, 1, 0, 2, 2}
};
int[][] res = applyDiff2D(arr, opr);
for (int[] row : arr) {
for (int val : row) System.out.print(val + " ");
System.out.println();
}
}
}
def applyDiff2D(mat, opr):
n = len(mat)
m = len(mat[0])
# diff matrix of size n x m
diff = [[0] * m for _ in range(n)]
# apply all operations using 4-point updates
for q in opr:
v, r1, c1, r2, c2 = q
# top-left -> add
diff[r1][c1] += v
# top-right -> subtract
if c2 + 1 < m:
diff[r1][c2 + 1] -= v
# bottom-left -> subtract
if r2 + 1 < n:
diff[r2 + 1][c1] -= v
# bottom-right -> add
if r2 + 1 < n and c2 + 1 < m:
diff[r2 + 1][c2 + 1] += v
# row-wise prefix sum
for i in range(n):
for j in range(1, m):
diff[i][j] += diff[i][j - 1]
# column-wise prefix sum
for j in range(m):
for i in range(1, n):
diff[i][j] += diff[i - 1][j]
# apply diff to original matrix
for i in range(n):
for j in range(m):
mat[i][j] += diff[i][j]
return mat
if __name__ == "__main__":
mat = [
[1, 2, 3],
[1, 1, 0],
[4, -2, 2]
]
opr = [
[2, 0, 0, 1, 1],
[-1, 1, 0, 2, 2]
]
res = applyDiff2D(mat, opr)
for row in mat:
print(" ".join(map(str, row)))
using System;
class GfG {
public static int[][] applyDiff2D(int[][] mat, int[][] opr) {
int n = mat.Length;
int m = mat[0].Length;
// diff matrix of size n x m
int[][] diff = new int[n][];
for (int i = 0; i < n; i++) diff[i] = new int[m];
// apply all operations using 4-point updates
foreach (var q in opr) {
int v = q[0];
int r1 = q[1], c1 = q[2], r2 = q[3], c2 = q[4];
// top-left -> add
diff[r1][c1] += v;
// top-right -> subtract
if (c2 + 1 < m) diff[r1][c2 + 1] -= v;
// bottom-left -> subtract
if (r2 + 1 < n) diff[r2 + 1][c1] -= v;
// bottom-right -> add
if (r2 + 1 < n && c2 + 1 < m) diff[r2 + 1][c2 + 1] += v;
}
// row-wise prefix sum
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
diff[i][j] += diff[i][j - 1];
}
}
// column-wise prefix sum
for (int j = 0; j < m; j++) {
for (int i = 1; i < n; i++) {
diff[i][j] += diff[i - 1][j];
}
}
// apply diff to original matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
mat[i][j] += diff[i][j];
}
}
return mat;
}
static void Main() {
int[][] mat = new int[][] {
new int[] {1, 2, 3},
new int[] {1, 1, 0},
new int[] {4, -2, 2}
};
int[][] opr = new int[][] {
new int[] {2, 0, 0, 1, 1},
new int[] {-1, 1, 0, 2, 2}
};
int[][] res = applyDiff2D(mat, opr);
foreach (var row in res) {
foreach (var val in row)
Console.Write(val + " ");
Console.WriteLine();
}
}
}
function applyDiff2D(mat, opr) {
let n = mat.length;
let m = mat[0].length;
// diff matrix of size n x m
let diff = Array.from({ length: n }, () => Array(m).fill(0));
// apply all operations using 4-point updates
for (let q of opr) {
let v = q[0];
let r1 = q[1], c1 = q[2], r2 = q[3], c2 = q[4];
// top-left -> add
diff[r1][c1] += v;
// top-right -> subtract
if (c2 + 1 < m) diff[r1][c2 + 1] -= v;
// bottom-left -> subtract
if (r2 + 1 < n) diff[r2 + 1][c1] -= v;
// bottom-right -> add
if (r2 + 1 < n && c2 + 1 < m) diff[r2 + 1][c2 + 1] += v;
}
// row-wise prefix sum
for (let i = 0; i < n; i++) {
for (let j = 1; j < m; j++) {
diff[i][j] += diff[i][j - 1];
}
}
// column-wise prefix sum
for (let j = 0; j < m; j++) {
for (let i = 1; i < n; i++) {
diff[i][j] += diff[i - 1][j];
}
}
// apply diff to original matrix
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
mat[i][j] += diff[i][j];
}
}
return mat;
}
// Driver Code
let mat = [
[1, 2, 3],
[1, 1, 0],
[4, -2, 2]
];
let opr = [
[2, 0, 0, 1, 1],
[-1, 1, 0, 2, 2]
];
let res = applyDiff2D(mat, opr);
for (let row of mat) {
console.log(row.join(" "));
}
Output
3 4 3 2 2 -1 3 -3 1
Time Complexity
- Each update: O(1)
- Final matrix construction: O(n × m)
Auxiliary Space
- Difference matrix diff[][]: O(n × m) (extra space used for marking updates)
- Final matrix mat[][]: uses existing space or same input
Applications of 2D Difference Arrays
The 2D difference array is a powerful technique for efficiently handling repeated updates to rectangular regions within a matrix. It’s particularly useful in scenarios like:
- Updating submatrices in grid-based simulations
- Adjusting brightness in image regions
- Modifying terrain in game maps
- Batch editing in spreadsheet-like data
Instead of looping through every cell in each rectangle which is inefficient on large grids the 2D difference array lets you apply each update in O(1) time by marking only the rectangle’s boundaries. Once all updates are recorded, the final matrix is computed in O(n × m) time using prefix sums, making it ideal for high-performance, large-scale matrix operations.
Why the 2D Difference Array Technique Works
Let’s analyze the effect:
- We add v at the top-left corner of the rectangle.
- We subtract v right after the right column, and one row below the bottom.
- We add v back at the bottom-right overflow point (to counteract the two subtractions).
This ensures that:
- When we compute prefix sums row-wise and column-wise, each cell in the range [r1..r2][c1..c2] gets +v added exactly once.
- All other cells remain unaffected.