🧠 Solving LeetCode Until I Become Top 1% — Day `63`

🔹 Problem: 1277. Count Square Submatrices with All Ones

Difficulty: #Medium
Tags: #Array, #Matrix #DynamicProgramming

📝 Problem Summary

Dinsing the square matrix subarrays that consist entirely of 1s, return the number of square submatrices that have all their sides of equal length and contain only 1s.

🧠 My Thought Process

Brute Force Idea:
This is kind of a brute force problem where we can iterate through all possible submatrices and check if they are square and consist of all 1s. However, this would be inefficient.
Optimized Strategy:
This problem has a simple twist: we can use dynamic programming to keep track of the size of the largest square submatrix ending at each cell. The value at each cell will be the minimum of the values from the top, left, and top-left diagonal cells plus one if the current cell is 1.
- It's kinda hard to explain, but the idea is that if we have a square submatrix ending at (i, j), then the size of that square is determined by the minimum of the squares ending at (i-1, j), (i, j-1), and (i-1, j-1).
Algorithm Used:

[[Matrix]] [[dp]]

⚙️ Code Implementation (Python)

# Brief comment about the approach
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        m, n = len(matrix), len(matrix[0])
        res = 0

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1 and i > 0 and j > 0:
                    matrix[i][j] = min(
                        matrix[i-1][j],
                        matrix[i][j-1],
                        matrix[i-1][j-1]
                    ) + 1
                res += matrix[i][j]

        return res

⏱️ Time & Space Complexity

Time: O(m * n)
Space: O(1) - In-place modification of the input matrix

🧩 Key Takeaways

✅ What concept or trick did I learn? Dynamic programming can be used to efficiently count square submatrices by building on previously computed values.
💡 What made this problem tricky? Understanding how to use the minimum of neighboring cells to determine the size of the square submatrix was key.
💭 How will I recognize a similar problem in the future? Look for problems involving counting or finding submatrices, especially those that can be solved with dynamic programming.