221. Maximal Square | LeetCode Medium | Python Solution | 2D Array, Matrix, Dynamic Programming

Leetcode medium problem 221. Maximal Square, detailed explanation and solution in python language.

#leetcode #python #solution

Problem Statement:
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given a 2D matrix containing 0s and 1s. From this matrix, we need to find out the largest square containing only 1s and return the area of that square.
so what we will do is, we will traverse through the matrix one time, starting from the top left cell till the bottom right cell of the matrix.
and during the traversal, if the cell is containing the value 1, we will analyze whether this particular cell when combined with the previously analyzed neighboring cells can give a valid square.
for example, for this particular cell, we have discovered these 3 neighboring squares. among these 3 squares, this is the smallest square, and therefore it is limiting a bigger square formation. so we can conclude that among the 3 neighbors, the square with smaller side will decide the new squares size. also, if any of the neighboring cell value is 0, we cannot combine the current cell with neighboring cells, and therefore we can only have square of side 1.

so, since we need previously discovered square sizes for reference, we must create a separate empty matrix of same size for storing the maximum side of the square we have found out at each cell.
we will name this matrix 'squareSizes'.
so for each cell in the given matrix, we will have a corresponding cell in the new matrix for storing the size of square.
for example, for this particular cell, we know that the size of the square formed is 3. so we will store this information in the corresponding cell of our new matrix.
so by the end of the traversal, we know what is the maximum side of square present in the matrix.
and we know that the area of square is given as side x side.

Now lets start the coding.

here, what we are finding out is maximum square side.
so lets initialize this variable 'maxSquareSide' to 0.
and what we need to return is the area of largest square.
so we can return the square of the maximum side.

for traversing the matrix, we need to know the number of rows and columns.
so lets store it in these variables 'r' and 'c'.
also, during the traversal, we need to store the maximum square size discovered at each cell.
so lets create a new matrix of same size 'squareSizes' with all the cells initially filled with 0.

now we will go through each cell of the given matrix.
if the cell is containing value 1, we have got a square of side 1, and we will check whether there are any neighboring squares that can be added to this cell.
we know that the neighboring square with the smallest side is the limiting square. so we will write a function for getting the minimum neighboring square for the current cell.
This function will return the minimum of 3 neighbors.
also here we need to put a edge case check.
i.e., if we are currently in the first row or first column, at least one neighbor will always be outside the matrix, which will become the limiting value.
so we will return 0 in that case.

during each iteration, we will check whether we have found out a larger side. if so, we will update the 'maxSquareSide' variable.