# 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].