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, 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

    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