Loading problem...
You are given an m × n binary matrix consisting entirely of 0s and 1s. Your task is to determine the total count of all square-shaped submatrices within this grid that contain exclusively 1s (no zeros).
A square submatrix is defined as a contiguous rectangular region where the number of rows equals the number of columns. Valid square submatrices can range in size from 1×1 (a single cell containing 1) up to the largest possible square that fits within the matrix boundaries and contains only 1s.
Your objective is to count every such valid square submatrix across all possible sizes and positions within the grid, then return the total count.
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]15The grid contains multiple square submatrices filled entirely with 1s: • 10 squares of size 1×1: Each individual cell containing a 1 counts as a valid 1×1 square. • 4 squares of size 2×2: Located at positions (0,1), (0,2), (1,1), and (1,2) as their top-left corners. • 1 square of size 3×3: Spanning columns 1-3 across all three rows. Total count: 10 + 4 + 1 = 15
matrix = [[1,0,1],[1,1,0],[1,1,0]]7Breaking down the valid squares: • 6 squares of size 1×1: The cells at positions (0,0), (0,2), (1,0), (1,1), (2,0), and (2,1) each contain a 1. • 1 square of size 2×2: Located at bottom-left corner, spanning rows 1-2 and columns 0-1. Total count: 6 + 1 = 7
matrix = [[1,1],[1,1]]5A fully filled 2×2 matrix contains: • 4 squares of size 1×1: Each of the four cells. • 1 square of size 2×2: The entire matrix itself. Total count: 4 + 1 = 5
Constraints