Find K for KxK Square of Same Value in C++

Suppose we have a 2d matrix, we have to find the largest k × k submatrix where all of its elements are containing the same value, then find the value of k.

So, if the input is like

then the output will be 3, as there is a 3 × 3 square matrix of value 5.

To solve this, we will follow these steps −

• n := row count of matrix

• m := column count of matrix

• Define one 2D array dp of size (n x m) and fill with 1

• ret := 1

• for initialize i := n - 1, when i >= 0, update (decrease i by 1), do −

  • for initialize j := m - 1, when j >= 0, update (decrease j by 1), do −

    • val := inf

    • if i + 1 < n and v[i + 1, j] is same as v[i, j], then −

      • val := minimum of dp[i + 1, j] and val

    • Otherwise

      • val := 0

    • if j + 1 < m and v[i, j + 1] is same as v[i, j], then −

      • val := minimum of dp[i, j + 1] and val

    • Otherwise

      • val := 0

    • if i + 1 < n and j + 1 < m and v[i + 1, j + 1] is same as v[i, j], then −

      • val := minimum of dp[i + 1, j + 1] and val

    • Otherwise

      • val := 0

    • if val is same as inf, then −

      • Ignore following part, skip to the next iteration

    • dp[i, j] := dp[i, j] + val

      • ret := maximum of ret and dp[i, j]

• return ret

Example 

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<vector<int>>& v) {
      int n = v.size();
      int m = v[0].size();
      vector<vector<int>> dp(n, vector<int>(m, 1));
      int ret = 1;
      for (int i = n - 1; i >= 0; i--) {
         for (int j = m - 1; j >= 0; j--) {
            int val = INT_MAX;
            if (i + 1 < n && v[i + 1][j] == v[i][j]) {
               val = min(dp[i + 1][j], val);
            }
            else {
               val = 0;
            }
            if (j + 1 < m && v[i][j + 1] == v[i][j]) {
               val = min(dp[i][j + 1], val);
            }
            else {
               val = 0;
            }
            if (i + 1 < n && j + 1 < m && v[i + 1][j + 1] == v[i][j]) {
               val = min(dp[i + 1][j + 1], val);
            }
            else {
               val = 0;
            }
            if (val == INT_MAX)
               continue;
               dp[i][j] += val;
               ret = max(ret, dp[i][j]);
            }
         }
         return ret;
      }
};
int solve(vector<vector<int>>& matrix) {
   return (new Solution())->solve(matrix);
}
int main(){
   vector<vector<int>> matrix = {
      {1, 1, 8, 3},
      {1, 5, 5, 5},
      {2, 5, 5, 5},
      {4, 5, 5, 5}
   };
   cout << solve(matrix);
}

Input

{ {1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5,
5} };

Output

3