Leetcode Problem 2536. Increment Submatrices by One

2536. Increment Submatrices by One

Leetcode Solutions

Prefix Sum Approach

  1. Initialize a matrix mat of size n x n with all zeros.
  2. Iterate over each query [row1, col1, row2, col2]: a. Increment mat[row1][col1] by 1 (top-left corner). b. Decrement mat[row1][col2 + 1] by 1 if col2 + 1 < n (just outside the right edge). c. Decrement mat[row2 + 1][col1] by 1 if row2 + 1 < n (just outside the bottom edge). d. Increment mat[row2 + 1][col2 + 1] by 1 if both row2 + 1 < n and col2 + 1 < n (bottom-right corner outside the submatrix).
  3. Calculate the prefix sum row-wise.
  4. Calculate the prefix sum column-wise.
  5. Return the final matrix mat.
UML Thumbnail

Brute Force Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...