Google / Amazon Interview Question — LeetCode 1292 — Y Tech

In this post, we are going to discuss leetcode 1292 — Maximum Side Length of a Square with Sum Less than or Equal to Threshold, which is asked in Google, and Amazon interviews.

Problem Analysis

Given a m x n matrix mat and an integer threshold, return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4 
Output: 2 
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1 
Output: 0

This is a matrix question, where we need to maintain a memory map.

My Thinking Process

This is a standard matrix problem, where we only need to get the sum of values in a square. Usually for this type of questions, we need to keep a memory map.

The common logic to solve this type of question is:

1. Build and maintain a memory map in a matrix memo, where memo[i][j]would be the sum of all the values from the rectangle 0,0 to i,j from the given matrix.
2. Loop through the memory map, and assume we are at position r,c. We can simply get the sum of values of size k…