PROBLEM LINK:
Author: Satyabrat Panda
Tester: Pritish Priyatosh Nayak
Editorialist: Satyabrat Panda
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given a matrix, find out the maximum size square sub-matrix with same digit, i.e, sub-matrix filled with only 1s, 2s, 3s or 4s.
EXPLANATION:
The states of the dp are (r, c, val).
dp[r][c][val] represents the maximum size square sub-matrix filled with val and bottom-right vertex at grid (r, c).
Traversing the matrix in row-major order, at any cell (r, c) with value val, we’ve three options -
- Extend the square filled with val and bottom-right vertex at the cell just above the current cell, i.e (r - 1, c).
- Extend the square filled with val and bottom-right vertex at the cell just to the left the current cell, i.e (r , c - 1).
- Extend the square filled with val and bottom-right vertex at the cell just diagonally to the left of the current cell, i.e (r - 1, c - 1).
Take the minimum of the three values + 1.
The dp transistion looks like this :
dp[r][c][val] = 1 + min(dp[r - 1][c][va], dp[r][c - 1][val], dp[r - 1][c - 1][val])
where val = arr[r][c].