What is the brute force approach and complexity for Count Square Submatrices with All Ones?

Try every top-left corner and every side, and check every cell of each square with time complexity O(M · N · min(M, N)³) and space complexity O(1).

What is the optimal approach and complexity for Count Square Submatrices with All Ones?

dp[r][c] = squares that end at (r, c); add every dp value to the total with optimal time complexity O(M · N) and space complexity O(N).

How do you identify the pattern for Count Square Submatrices with All Ones?

Look for key signals in the prompt: "square submatrices" indicates Squares again, so the same table as Maximal Square: a square grows one step at a time, limited by its three neighbours.; "how many" indicates The answer is a count, not a maximum. Add the values up instead of taking the largest one.; "all ones" indicates A `0` cell closes no square, so its dp value is 0..

Count Square Submatrices with All Ones

Medium·LeetCode #1277 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You get a grid of 0s and 1s. Count the square blocks inside the grid that are filled only with 1s.

Every size counts. A single 1 is a square of side 1. A 2 × 2 block of ones is a square of side 2, and it counts on top of the four single ones inside it.

Input

A grid matrix with m rows and n columns. Each cell is 0 or 1.

Output

The number of all-ones square blocks, counting every side length.

Example 1

Input: matrix = [[0,1,1,1], [1,1,1,1], [0,1,1,1]]

Output: 15

There are 10 squares of side 1, 4 squares of side 2 and 1 square of side 3. The total is 10 + 4 + 1 = 15.

Example 2

Input: matrix = [[1,0,1], [1,1,0], [1,1,0]]

Output: 7

There are 6 squares of side 1. There is 1 square of side 2, the block at rows 1–2 and columns 0–1. The total is 6 + 1 = 7.

Constraints

• 1 ≤ m, n ≤ 300
• Each cell is 0 or 1.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“square submatrices”

→ Squares again, so the same table as Maximal Square: a square grows one step at a time, limited by its three neighbours.

“how many”

→ The answer is a count, not a maximum. Add the values up instead of taking the largest one.

“all ones”

→ A `0` cell closes no square, so its dp value is 0.

Approach Complexity Ladder

Brute Force — check every squareO(M · N · min(M, N)³)O(1)

Try every top-left corner and every side, and check every cell of each square

Better — 2-D prefix sums check each square in O(1)O(M · N · min(M, N))O(M · N)

Count the ones in a square with a prefix-sum table; the square counts when the count is k × k

Optimal — one DP row and a running totalO(M · N)O(N)

dp[r][c] = squares that end at (r, c); add every dp value to the total

Brute Force Intuition

A square is fixed by its top-left corner and its side k. Try every corner and every side that fits. For each one, check every cell of the square. If all of them are 1, add one to the count.

Recognition rule for this sub-pattern:

dp[r][c] = largest square ending here = 1 + min(top, left, top-left).

Remember this · DP — Grid

Trigger

Move only right/down, count paths, minimum path cost, largest square of 1s.

Think

To reach cell (r, c), which cells could I have come from?

Key question

What does dp[r][c] mean, and what are the first row/column?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Grid translate into production architectures and low-level memory mechanics.

LLD Architecture