Google / Amazon / Meta / Microsoft Interview Question — LeetCode 1277

In this post, we are going to discuss leetcode 1277 — Count Square Submatrices with All Ones, which is asked in Google, Amazon, Meta, and Microsoft interviews.

Problem Analysis

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] 
Output: 15 
Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = [ [1,0,1], [1,1,0], [1,1,0] ] 
Output: 7 
Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7.

This is a math problem, which we can solve it just by considering all the scenarios.

My Thinking Process

The main difficult part is to count the number of submatrices with size larger than 1. Let us consider the following case:

[1,1,1]   
[1,1,1]   
[1,1,1]

In the above example, we have 14 submatrices, with 9 of them having size of 1, 4 of them having size of 2, and 1 of them having size of 1.

Let us first assume we can only form submatrices by moving to left, and to top. In order to get the submatrice of size 2, all the neighbours at…