Approaches To Problem Solving : Applying Dynamic Programming on 2-D Matrices
Problem : Given a two-dimensional matrix of integers containing 1s and 0s, return the total number of square submatrices with all 1s.
Let us consider the following example to get a clearer idea of this problem,
Let us consider a brute force solution first.
Approach #1: We can try to break down the entire matrix into submatrices. A brute force solution will lead us to creating all the submatrices that are possible for the given matrix and then checking all of them one by one for the calculation of our answer. We can define two steps to our solution as :-
Step 1: We generate all the submatrices possible from the given matrix. There are a total of N * M * N * M submatrices for an N * M matrix.
Step 2: We check each submatrix one by one to find out if all the elements in that submatrix are 1s or not. If we find no 0-element in our submatrix, we add 1 to our answer and keep repeating this process for all such submatrices.
The time complexity for this solution is ~O(N⁶), where N is the number of rows or columns and assuming that rows and columns can be of interchangeable range of sizes.
We can reduce this time complexity a lot, by trying to store answers for submatrices and using these stored values for finding answers for the remaining submatrices of the given matrix.
Approach #2: After spending some time with pen and paper, trying to understand how we can frame our dynamic programming solution, we find out that we can use a given cell in this matrix to figure out if a square submatrix containing all 1s ends at this cell or not. By “ends at this cell”, we mean that this cell being considered, is the bottom-rightmost corner cell of some submatrix.
Since we are only concerned about the square submatrices, one important observation is that for any bottom-rightmost cell, there are only three cells which need to be considered when determining if this cell being considered contributes to some square submatrix containing all 1s or not.
Whenever we consider some cell defined by (i, j), where i represents the ith row and j represents the jth column, we check for the largest dimension of matrices ending at (i — 1, j), (i — 1, j — 1) and (i, j — 1). These three values tell us the maximum dimensions for the submatrices ending at the cells mentioned above. One interesting observation is that if the current cell being considered is 1, then adding 1 to the minimum of the three values found above will tell us the maximum dimension of the square matrix containing all 1s, ending at the current cell.
We can define our transition as,
For all (i, j), 1 ≤ i ≤ N and 1 ≤ j ≤ M, if matrix[i][j] = 1,
maxDimension[i][j] = 1 + min({maxDimension[i — 1][j], maxDimension[i — 1][j — 1], maxDimension[i][j — 1})
The “maxDimension” matrix for the given input matrix can be built as,
It seems obvious now, that only the row and the column on which we currently are, contribute to the state of our dynamic programming.
All that is left is to traverse over this “maxDimension” matrix and add up all the values in the matrix. Why? Because, if the maximum dimension of some submatrix containing all 1s, for a cell in a matrix is say ‘X’, then it will contribute to all square submatrices 1, 2,…,X.
We need to take care of the cells that are out of bound (which serves as the base case for our dynamic programming) and we have our answer.
The time complexity for the above solution is ~O(N * M).
This proves to be a huge improvement over the brute force solution proposed solution!!
In our next article, one of the problems that we are going to discuss is given below,
Problem: Given a list of integers, arr. Consider a tree where arr represents the values of its leaves in an inorder traversal. All internal nodes have 2 children each and their value is equal to the product of the largest leaf value of its left subtree and the largest leaf value of its right subtree. Find the tree with the minimum sum of its values and return the sum.
We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Matrices and Dynamic Programming further!
We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.
For hugs and bugs, please comment down below. Till then.. Happy Coding!
This is the 13th article of the “Approaches To Problem Solving” series.
More such posts can be found at :-
