2D Difference Array

Time: O(n*m)

Space: O(n*m)

Intuition

Apply range updates on a 2D matrix efficiently. Difference array lets you add value to submatrix in O(1) then reconstruct in O(m*n).

Algorithm

1For update (r1,c1,r2,c2,val): diff[r1][c1]+=val, diff[r1][c2+1]-=val, diff[r2+1][c1]-=val, diff[r2+1][c2+1]+=val.
2Reconstruct: prefix sum row-wise then column-wise.

Common Pitfalls

•2D extension of 1D difference array. Four corners of the rectangle update. O(1) per update, O(m*n) to reconstruct.

2D Difference Array.java

Java

// Approach: 2D difference array to apply range updates in O(1).
// Reconstruct final matrix by computing 2D prefix sums.
// Time: O(n*m) Space: O(n*m)
import java.util.*;

class Solution {
    public ArrayList<ArrayList<Integer>> applyDiff2D(int[][] mat, int[][] opr) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

        for (int n = 0; n < opr.length; n++) {
            int num = opr[n][0];
            int istart = opr[n][1];
            int jstart = opr[n][2];
            int iend = opr[n][3];
            int jend = opr[n][4];
            for (int i = istart; i <= iend; i++) {
                for (int j = jstart; j <= jend; j++)
                    mat[i][j] += num;
            }
        }
        for (int i = 0; i < mat.length; i++) {
            ArrayList<Integer> ans = new ArrayList<Integer>();
            for (int j = 0; j < mat[0].length; j++)
                ans.add(mat[i][j]);
            res.add(ans);
        }

        return res;
    }
}

Was this solution helpful?