## Problem statement

We need to find the maximal square from the given matrix and return its area. Before getting to the problem statement, let us understand the fundamentals of the square.

So, a square is a shape that has four straight sides of the same length and four angles of 90 degrees (right angles). And for the matrix, a square can be defined as the equal no. of rows and columns.

A **maximal square** is that square that holds the maximum and equal no. of rows and columns in the given matrix.

Now that you have understood the meaning of the question let us have a look at the problem statement:-

**Given a binary matrix with 0â€™s and 1â€™s, find out the maximum size square sub-matrix with all 1â€™s and return its area.**

**Example 1:-**

Input: matrix = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]

Output: 4

**Explanation**: Since the maximal square is of size 2, output(area) = side x side = 2 x 2 = 4.

**Example 2**:-

Input: matrix = [[1,1,1,1],[0,1,1,1],[1,1,1,1],[1,1,1,0]]

Output: 9

**Explanation**: Since the maximal square is of size 3, output(area) = side x side = 3 x 3 = 9.

**Example 3:**

Input: matrix = [[0,1],[1,0]]

Output: 1

**Explanation**: Since the maximal square is of size 1, output(area) = side x side = 1 x 1 = 1.

**Example 4:**

Input :matrix = [ ]

Output: 0

**Explanation**: Since the matrix is empty and hence no square is possible, output(area) = 0.

__It is recommended to try the stated problem on your own before moving to the solution.__

As previously said, the problem we are facing can be handled utilising the dynamic programming technique; thus, before we go into the approach, let us first clarify what dynamic programming is.

## What is Dynamic Programming?

The picture above conveys a great deal about Dynamic Programming. So, is it a good idea to keep doing things for which you already have an answer? A coder would beg to differ. That is the essence of Dynamic Programming. Always remember the solutions to sub-problems you've already solved.

To be more specific, A problem must be broken down into a succession of overlapping sub-problems, and solutions to bigger and larger sub-problems must be built up. You've encountered a DP problem if you're given a problem that can be broken down into smaller sub-problems, and these smaller subproblems can be broken down into more smaller ones - and you figure out that there are some overlapping subproblems.

- Dynamic Programming's main notion is to prevent repeating work by remembering partial outcomes, and this concept is used in various real-world scenarios.

- Dynamic Programming is a sophisticated technique that allows you to solve various problems in O(n^2) or O(n^3) time when a naÃ¯ve approach requires exponential time.

Since now we have gained the idea behind dynamic programming, let us try to think in the same way to solve the given problem.