Given a square matrix of odd order N. The task is to find the side-length of the largest square formed in the matrix. A square in matrix is said to be formed if all elements on its perimeter is same and its centre is centre of matrix. Centre of matrix is also a square with side length 1.
Examples:Â
Input : matrix[][] = {2, 3, 0,
0, 2, 0,
0, 1, 1}
Output : 1
Input : matrix[][] = {2, 2, 2,
2, 1, 2,
2, 2, 2}
Output : 3
The centre of any odd order matrix is element with index i = j = n/2. Now, for finding largest square in matrix, check all surrounding elements from centre which are at same distance. For a square which is i-unit away from centre check all the element which are in the n/2-i and n/2+i row and column also difference of n/2 and either of index of element does-not exceed i. Please find the format of a square with different possible side length in below example.Â
x x x x x x y y y x x y c y x x y y y x x x x x x
Points to care about :Â
- As centre element is also a form of square minimum possible side length is 1.
- Longest square can be with all elements present in 1st row and 1 column, hence maximum possible side-length isÂ
Algorithm :Â
- Iterate over i=0 to n/2
- iterate over column i to n-i-1 for row i and n-i-1 bothÂ
and vice-versa and check whether all elements are same or not.- If yes then length of square is n-2*i.
- Else go for next iteration
Below is the implementation of the above approach:
C++
// C++ program to find max possible side-length// of a square in a given matrixÂ
#include <bits/stdc++.h>#define n 5using namespace std;Â
// Function to return side-length of squareint largestSideLen(int matrix[][n]){Â Â Â Â int result = 1;Â
    // Traverse the matrix    for (int i = 0; i < n / 2; i++) {Â
        int element = matrix[i][i];        int isSquare = 1;Â
        for (int j = i; j < n - i; j++) {            // for row i            if (matrix[i][j] != element)                isSquare = 0;            // for row n-i-1            if (matrix[n - i - 1][j] != element)                isSquare = 0;            // for column i            if (matrix[j][i] != element)                isSquare = 0;            // for column n-i-1            if (matrix[j][n - i - 1] != element)                isSquare = 0;        }Â
        if (isSquare)            return n - 2 * i;    }Â
    // Return result    return result;}Â
// Driver programint main(){    int matrix[n][n] = { 1, 1, 1, 1, 1,                         1, 2, 2, 2, 1,                         1, 2, 1, 2, 1,                         1, 2, 2, 2, 1,                         1, 1, 1, 1, 1 };Â
    cout << largestSideLen(matrix);Â
    return 0;} |
Java
// Java program to find max possible side-length// of a square in a given matrixÂ
import java.io.*;Â
class GFG {static int n = 5;Â Â Â Â // Function to return side-length of squarestatic int largestSideLen(int matrix[][]){Â Â Â Â int result = 1;Â
    // Traverse the matrix    for (int i = 0; i < (n / 2); i++) {Â
        int element = matrix[i][i];        int isSquare = 1;Â
        for (int j = i; j < n - i; j++) {            // for row i            if (matrix[i][j] != element)                isSquare = 0;            // for row n-i-1            if (matrix[n - i - 1][j] != element)                isSquare = 0;            // for column i            if (matrix[j][i] != element)                isSquare = 0;            // for column n-i-1            if (matrix[j][n - i - 1] != element)                isSquare = 0;        }Â
        if (isSquare > 0)            return n - (2 * i);    }Â
    // Return result    return result;}Â
// Driver program         public static void main (String[] args) {        int matrix[][] = {{ 1, 1, 1, 1, 1},                        {1, 2, 2, 2, 1},                        {1, 2, 1, 2, 1},                        {1, 2, 2, 2, 1},                        {1, 1, 1, 1, 1 }};Â
    System.out.println (largestSideLen(matrix));                      }} |
Python3
# Python 3 program to find max possible # side-length of a square in a given matrixÂ
n = 5Â
# Function to return side-length of squaredef largestSideLen(matrix):Â Â Â Â result = 1Â
    # Traverse the matrix    for i in range(int(n / 2)):        element = matrix[i][i]        isSquare = 1Â
        for j in range(i, n - i):                         # for row i            if (matrix[i][j] != element):                isSquare = 0                             # for row n-i-1            if (matrix[n - i - 1][j] != element):                isSquare = 0                             # for column i            if (matrix[j][i] != element):                isSquare = 0                             # for column n-i-1            if (matrix[j][n - i - 1] != element):                isSquare = 0Â
        if (isSquare):            return n - 2 * iÂ
    # Return result    return resultÂ
# Driver Codeif __name__ == '__main__':    matrix = [[1, 1, 1, 1, 1],              [1, 2, 2, 2, 1],              [1, 2, 1, 2, 1],              [1, 2, 2, 2, 1],              [1, 1, 1, 1, 1]]Â
    print(largestSideLen(matrix))Â
# This code is contributed by# Surendra_Gangwar |
C#
// C#Â program to find max possible side-length// of a square in a given matrixusing System;Â
public class GFG{Â Â Â Â static int n = 5;Â Â Â Â // Function to return side-length of squarestatic int largestSideLen(int [,]matrix){Â Â Â Â int result = 1;Â
    // Traverse the matrix    for (int i = 0; i < (n / 2); i++) {Â
        int element = matrix[i,i];        int isSquare = 1;Â
        for (int j = i; j < n - i; j++) {            // for row i            if (matrix[i,j] != element)                isSquare = 0;            // for row n-i-1            if (matrix[n - i - 1,j] != element)                isSquare = 0;            // for column i            if (matrix[j,i] != element)                isSquare = 0;            // for column n-i-1            if (matrix[j,n - i - 1] != element)                isSquare = 0;        }Â
        if (isSquare > 0)            return n - (2 * i);    }Â
    // Return result    return result;}Â
// Driver program              static public void Main (){        int [,]matrix = {{ 1, 1, 1, 1, 1},                        {1, 2, 2, 2, 1},                        {1, 2, 1, 2, 1},                        {1, 2, 2, 2, 1},                        {1, 1, 1, 1, 1 }};Â
           Console.WriteLine(largestSideLen(matrix));             }} |
PHP
<?php// PHP program to find max possible// side-length of a square in a given matrix Â
// Function to return side-length of square function largestSideLen($matrix) { Â Â Â Â $n = 5; Â Â Â Â $result = 1; Â
    // Traverse the matrix     for ($i = 0; $i < ($n / 2); $i++)    { Â
        $element = $matrix[$i][$i];         $isSquare = 1; Â
        for ($j = $i; $j < ($n - $i); $j++)         {             // for row i             if ($matrix[$i][$j] != $element)                 $isSquare = 0;                              // for row n-i-1             if ($matrix[$n - $i - 1][$j] != $element)                 $isSquare = 0;                              // for column i             if ($matrix[$j][$i] != $element)                 $isSquare = 0;                              // for column n-i-1             if ($matrix[$j][$n - $i - 1] != $element)                 $isSquare = 0;         } Â
        if ($isSquare)             return ($n - 2 * $i);     } Â
    // Return result     return $result; } Â
// Driver Code $matrix = array( 1, 1, 1, 1, 1, Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 1, 2, 2, 2, 1, Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 1, 2, 1, 2, 1, Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 1, 2, 2, 2, 1, Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â 1, 1, 1, 1, 1 ); Â
echo largestSideLen($matrix); Â
// This code is contributed by Sachin?> |
Javascript
<script>Â
// Javascript program to find max // possible side-length// of a square in a given matrixÂ
const n = 5;Â
// Function to return // side-length of squarefunction largestSideLen(matrix){Â Â Â Â let result = 1;Â
    // Traverse the matrix    for (let i = 0; i < parseInt(n / 2); i++)     {Â
        let element = matrix[i][i];        let isSquare = 1;Â
        for (let j = i; j < n - i; j++) {            // for row i            if (matrix[i][j] != element)                isSquare = 0;            // for row n-i-1            if (matrix[n - i - 1][j] != element)                isSquare = 0;            // for column i            if (matrix[j][i] != element)                isSquare = 0;            // for column n-i-1            if (matrix[j][n - i - 1] != element)                isSquare = 0;        }Â
        if (isSquare)            return n - 2 * i;    }Â
    // Return result    return result;}Â
// Driver program    let matrix = [ [1, 1, 1, 1, 1],                   [1, 2, 2, 2, 1],                   [1, 2, 1, 2, 1],                   [1, 2, 2, 2, 1],                   [1, 1, 1, 1, 1 ]];Â
    document.write(largestSideLen(matrix));Â
</script> |
Output
5
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
