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 locations [i, j-1], [i-1, j], [i-1, j-1]has to be ones. In order to have a submatrice of size 3, all the neighbours at locations [i, j-1], [i-1, j], [i-1, j-1] has to be submatrice of size 2.

With above analysis, we can find that the maximum size of submatrice we can get only depends on its direct neighbours at locations [i, j-1], [i-1, j], [i-1, j-1]. If the minimum submatrice of those neighbours is n, then the largest submatrice we can get at this position is n+1.

Now we can get the maximum size of submatrice at each position. To count the total submatrices, we can simply by aggregating all the size together. The reason behind it is simple. For example, if we can have a submatrice of size n at one position, then at this position, we can have n submatrices in total by move to left and to top, one for each size.

Code Implementation

Base on the analysis above, below is my implementation of the problem.