Leetcode Problem 1504. Count Submatrices With All Ones

1504. Count Submatrices With All Ones

Leetcode Solutions

Histogram and Monotonic Stack Approach

  1. Initialize a variable res to store the total number of submatrices with all ones.
  2. Create an array height to store the histogram heights for each column.
  3. Iterate over each row of the matrix: a. Update the height array for the current row. b. Initialize a stack to keep track of indices of non-decreasing heights. c. Iterate over each column in the current row: i. While the stack is not empty and the current height is less than the height at the top of the stack, pop from the stack. ii. Calculate the number of submatrices using the current height and the widths determined by the stack. iii. Push the current index and the cumulative number of submatrices onto the stack. d. Add the cumulative number of submatrices to res.
  4. Return res as the final result.
UML Thumbnail

Dynamic Programming Approach

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...