# Solving Leetcode Interviews in Seconds with AI: Count Submatrices With All Ones


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1504" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> Given an m x n binary matrix mat, return the number of submatrices that have all ones.   Example 1:   Input: mat = [[1,0,1],[1,1,0],[1,1,0]] Output: 13 Explanation:  There are 6 rectangles of side 1x1. There are 2 rectangles of side 1x2. There are 3 rectangles of side 2x1. There is 1 rectangle of side 2x2.  There is 1 rectangle of side 3x1. Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.  Example 2:   Input: mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]] Output: 24 Explanation:  There are 8 rectangles of side 1x1. There are 5 rectangles of side 1x2. There are 2 rectangles of side 1x3.  There are 4 rectangles of side 2x1. There are 2 rectangles of side 2x2.  There are 2 rectangles of side 3x1.  There is 1 rectangle of side 3x2.  Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.    Constraints:  1 <= m, n <= 150 mat[i][j] is either 0 or 1.  

	# Explanation
	Here's the breakdown of the solution:

*   **Dynamic Programming for Heights:** Use a DP table `heights` where `heights[i][j]` stores the consecutive number of 1s upwards from `mat[i][j]`. This avoids redundant recalculations.
*   **Iterate and Count:** Iterate through each cell of the matrix. For each cell, consider it as the bottom-right corner of a potential submatrix. Use the precomputed `heights` to efficiently determine how far left we can extend to form a valid submatrix, and accumulate the count.
*   **Minimum Height Approach:** When extending to the left, the height of the submatrix is limited by the minimum height encountered in the heights array along the current row.

*   **Runtime Complexity: O(m * n * n), Storage Complexity: O(m * n)**

	
	# Code
	```python
	def numSubmat(mat):
    """
    Calculates the number of submatrices with all ones in a binary matrix.

    Args:
        mat: A list of lists of integers, where each integer is either 0 or 1.

    Returns:
        The number of submatrices with all ones.
    """

    m = len(mat)
    n = len(mat[0])
    heights = [[0] * n for _ in range(m)]

    # Calculate heights array
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 1:
                heights[i][j] = (heights[i - 1][j] if i > 0 else 0) + 1

    count = 0
    for i in range(m):
        for j in range(n):
            min_height = float('inf')
            for k in range(j, -1, -1):
                min_height = min(min_height, heights[i][k])
                count += min_height

    return count
	```