2536. Increment Submatrices by One

Time: O(n² + q)

Space: O(n²)

Approach

2D difference array for range increments; apply prefix sums to reconstruct result.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Matrix

Matrix problems often involve BFS/DFS flood fill, dynamic programming on 2D grids, or spiral/diagonal traversal. For row × column DP, break it into 1D sub-problems column by column. Common pitfalls: boundary checks and modifying the input matrix in-place.

Prefix Sum

A prefix sum array pre-computes cumulative values so any range query is answered in O(1). The classic sum of range [l, r] = prefix[r+1] - prefix[l]. 2D prefix sums extend this to matrix sub-rectangle queries. Combine with a hash map for "subarray sum equals k" problems.

2536.cs

// Approach: 2D difference array for range increments; apply prefix sums to reconstruct result.
// Time: O(n² + q) Space: O(n²)

public class Solution
{
    public int[][] RangeAddQueries(int n, int[][] queries)
    {
        // Initialize n x n matrix with all zeros
        int[][] matrix = new int[n][];
        for (int i = 0; i < n; i++)
            matrix[i] = new int[n];

        // Apply difference array technique for 2D range updates
        // Mark the boundaries of each query rectangle
        foreach (var query in queries)
        {
            int row1 = query[0];
            int col1 = query[1];
            int row2 = query[2];
            int col2 = query[3];

            // Mark the top-left corner with +1
            matrix[row1][col1]++;

            // Mark the position below the bottom-right corner with -1
            if (row2 + 1 < n)
                matrix[row2 + 1][col1]--;

            // Mark the position to the right of the bottom-right corner with -1
            if (col2 + 1 < n)
                matrix[row1][col2 + 1]--;

            // Mark the diagonal position (row2+1, col2+1) with +1 to compensate
            if (row2 + 1 < n && col2 + 1 < n)
                matrix[row2 + 1][col2 + 1]++;
        }

        // Build the final matrix using 2D prefix sum
        for (int row = 0; row < n; row++)
        {
            for (int col = 0; col < n; col++)
            {
                // Add value from the cell above
                if (row > 0)
                    matrix[row][col] += matrix[row - 1][col];

                // Add value from the cell to the left
                if (col > 0)
                    matrix[row][col] += matrix[row][col - 1];

                // Subtract the diagonal cell (included twice) to avoid double counting
                if (row > 0 && col > 0)
                    matrix[row][col] -= matrix[row - 1][col - 1];
            }
        }

        return matrix;
    }
}

Was this solution helpful?