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…