[FEATURE] Maximal Square (Square with Max area consisting of all 1's in a binary matrix) | Dynamic Programming | C++ #1621
Description
Detailed description
I am proposing to add the problem to find maximum area square with all 1's in a binary matrix in C++ language
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.
Input: matrix = [["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]]
Output: 4
Input: matrix = [["0","1"],
["1","0"]]
Output: 1
Context
This problem statement is a good example of Dynamic Programming. It has been asked to me in interview and coding tests for different companies. This question will help the users to understand how to use DP on 2D matrix and also help them to prepare for coding tests, etc
Possible implementation
It can be implemented using Dynamic Programming in O(N * M) Time and O(N * M) Space Complexity where N = number of rows and M = number of columns.
Additional information
Clean Code
Commented Code
Sample test case explained