Maximum perimeter of a square in a 2D grid
Given a matrix of integers mat[][] of size N * M. The task is to find the maximum perimeter of a square in the matrix. The perimeter of a square is defined as the sum of all the values lying on the sides of the square.
Examples:
Input: mat[][] = {
{-3, -2, 7},
{-4, 6, 0},
{-4, 8, 2}}
Output: 16
The maximum perimeter square is
{6, 0}
{8, 2}
Input: mat[][] = {
{1, 1, 0},
{1, 1, 1},
{0, 1, 1}}
Output: 6
Naive approach: A simple solution is to generate all the square that can be possible inside the given matrix mat[][] and then find their perimeter and take the maximum out of them.
Efficient approach:
- To find the perimeter of the square, the length of the sides should be known.
- Here the length is described as the sum of elements on that particular row and column.
- Two matrices of size N * M will be created and that will store the prefix sum of the rows of the original matrix and the prefix sum of the columns so that the length of sides can be calculated in constant time.
- There will be two nested loops one from 1 to N and the other from 1 to M to find the left corner of the square (Top-Left corner) and one loop will be min(N – i, M – j) that will tell us the size of the square and make sure that the index will not exceed the size of the matrix.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to calculate the prefix sum of the// rows and the columns of the given matrixvoid prefix_calculate(vector<vector<int> >& A, vector<vector<int> >& row, vector<vector<int> >& col){ // Number of rows and cols int n = (int)A.size(); int m = (int)A[0].size(); // First column of the row prefix array for (int i = 0; i < n; ++i) { row[i][0] = A[i][0]; } // Update the prefix sum for the rows for (int i = 0; i < n; ++i) { for (int j = 1; j < m; ++j) { row[i][j] = row[i][j - 1] + A[i][j]; } } // First row of the column prefix array for (int i = 0; i < m; ++i) { col[0][i] = A[0][i]; } // Update the prefix sum for the columns for (int i = 0; i < m; ++i) { for (int j = 1; j < n; ++j) { col[j][i] = A[j][i] + col[j - 1][i]; } }}// Function to return the perimeter// of the square having top-left corner// at (i, j) and size kint perimeter(int i, int j, int k, vector<vector<int> >& row, vector<vector<int> >& col, vector<vector<int> >& A){ // i and j represent the top left // corner of the square and // k is the size int row_s, col_s; // Get the upper row sum if (j == 0) row_s = 0; else row_s = row[i][j - 1]; // Get the left column sum if (i == 0) col_s = 0; else col_s = col[i - 1][j]; int upper_row = row[i][j + k] - row_s; int left_col = col[i + k][j] - col_s; // At the distance of k in // both direction if (j == 0) row_s = 0; else row_s = row[i + k][j - 1]; if (i == 0) col_s = 0; else col_s = col[i - 1][j + k]; int lower_row = row[i + k][j + k] - row_s; int right_col = col[i + k][j + k] - col_s; // The perimeter will be // sum of all the values int sum = upper_row + lower_row + left_col + right_col; // Since all the corners are // included twice, they need to // be subtract from the sum sum -= (A[i][j] + A[i + k][j] + A[i][j + k] + A[i + k][j + k]); return sum;}// Function to return the maximum perimeter// of a square in the given matrixint maxPerimeter(vector<vector<int> >& A){ // Number of rows and cols int n = (int)A.size(); int m = (int)A[0].size(); vector<vector<int> > row(n, vector<int>(m, 0)); vector<vector<int> > col(n, vector<int>(m, 0)); // Function call to calculate // the prefix sum of rows and cols prefix_calculate(A, row, col); // To store the maximum perimeter int maxPer = 0; // Nested loops to choose the top-left // corner of the square for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // Loop for the size of the square for (int k = 0; k < min(n - i, m - j); ++k) { // Get the perimeter of the current square int perimtr = perimeter(i, j, k, row, col, A); // Update the maximum perimeter so far maxPer = max(maxPer, perimtr); } } } return maxPer;}// Driver codeint main(){ vector<vector<int> > A = { { 1, 1, 0 }, { 1, 1, 1 }, { 0, 1, 1 } }; cout << maxPerimeter(A); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Function to calculate the prefix sum of the// rows and the columns of the given matrixstatic void prefix_calculate(int [][] A, int [][] row, int [][] col){ // Number of rows and cols int n = (int)A.length; int m = (int)A[0].length; // First column of the row prefix array for (int i = 0; i < n; ++i) { row[i][0] = A[i][0]; } // Update the prefix sum for the rows for (int i = 0; i < n; ++i) { for (int j = 1; j < m; ++j) { row[i][j] = row[i][j - 1] + A[i][j]; } } // First row of the column prefix array for (int i = 0; i < m; ++i) { col[0][i] = A[0][i]; } // Update the prefix sum for the columns for (int i = 0; i < m; ++i) { for (int j = 1; j < n; ++j) { col[j][i] = A[j][i] + col[j - 1][i]; } }}// Function to return the perimeter// of the square having top-left corner// at (i, j) and size kstatic int perimeter(int i, int j, int k, int [][] row, int [][] col, int [][] A){ // i and j represent the top left // corner of the square and // k is the size int row_s, col_s; // Get the upper row sum if (j == 0) row_s = 0; else row_s = row[i][j - 1]; // Get the left column sum if (i == 0) col_s = 0; else col_s = col[i - 1][j]; int upper_row = row[i][j + k] - row_s; int left_col = col[i + k][j] - col_s; // At the distance of k in // both direction if (j == 0) row_s = 0; else row_s = row[i + k][j - 1]; if (i == 0) col_s = 0; else col_s = col[i - 1][j + k]; int lower_row = row[i + k][j + k] - row_s; int right_col = col[i + k][j + k] - col_s; // The perimeter will be // sum of all the values int sum = upper_row + lower_row + left_col + right_col; // Since all the corners are // included twice, they need to // be subtract from the sum sum -= (A[i][j] + A[i + k][j] + A[i][j + k] + A[i + k][j + k]); return sum;}// Function to return the maximum perimeter// of a square in the given matrixstatic int maxPerimeter(int [][] A){ // Number of rows and cols int n = (int)A.length; int m = (int)A[0].length; int [][] row = new int[n][m]; int [][] col = new int[n][m]; // Function call to calculate // the prefix sum of rows and cols prefix_calculate(A, row, col); // To store the maximum perimeter int maxPer = 0; // Nested loops to choose the top-left // corner of the square for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // Loop for the size of the square for (int k = 0; k < Math.min(n - i, m - j); ++k) { // Get the perimeter of the current square int perimtr = perimeter(i, j, k, row, col, A); // Update the maximum perimeter so far maxPer = Math.max(maxPer, perimtr); } } } return maxPer;}// Driver codepublic static void main(String[] args){ int [][] A = { { 1, 1, 0 }, { 1, 1, 1 }, { 0, 1, 1 } }; System.out.print(maxPerimeter(A));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach# Function to calculate the prefix sum of the# rows and the columns of the given matrixdef prefix_calculate(A, row, col): # Number of rows and cols n = len(A) m = len(A[0]) # First column of the row prefix array for i in range(n): row[i][0] = A[i][0] # Update the prefix sum for the rows for i in range(n): for j in range(1, m): row[i][j] = row[i][j - 1]+ A[i][j] # First row of the column prefix array for i in range(m): col[0][i] = A[0][i] # Update the prefix sum for the columns for i in range(m): for j in range(1, m): col[j][i] = A[j][i] + col[j - 1][i]# Function to return the perimeter# of the square having top-left corner# at (i, j) and size kdef perimeter(i, j, k, row, col, A): # i and j represent the top left # corner of the square and # k is the size row_s, col_s = 0, 0 # Get the upper row sum if (j == 0): row_s = 0 else: row_s = row[i][j - 1] # Get the left column sum if (i == 0): col_s = 0 else: col_s = col[i - 1][j] upper_row = row[i][j + k] - row_s left_col = col[i + k][j] - col_s # At the distance of k in # both direction if (j == 0): row_s = 0 else: row_s = row[i + k][j - 1] if (i == 0): col_s = 0 else: col_s = col[i - 1][j + k] lower_row = row[i + k][j + k] - row_s right_col = col[i + k][j + k] - col_s # The perimeter will be # sum of all the values sum = upper_row + lower_row + \ left_col + right_col # Since all the corners are # included twice, they need to # be subtract from the sum sum -= (A[i][j] + A[i + k][j] + \ A[i][j + k] + A[i + k][j + k]) return sum# Function to return the maximum perimeter# of a square in the given matrixdef maxPerimeter(A): # Number of rows and cols n = len(A) m = len(A[0]) row = [[0 for i in range(m)] for i in range(n)] col = [[0 for i in range(m)] for i in range(n)] # Function call to calculate # the prefix sum of rows and cols prefix_calculate(A, row, col) # To store the maximum perimeter maxPer = 0 # Nested loops to choose the top-left # corner of the square for i in range(n): for j in range(m): # Loop for the size of the square for k in range(min(n - i, m - j)): # Get the perimeter of the current square perimtr = perimeter(i, j, k, row, col, A) # Update the maximum perimeter so far maxPer = max(maxPer, perimtr) return maxPer# Driver codeA = [[ 1, 1, 0 ], [ 1, 1, 1 ], [ 0, 1, 1 ]]print(maxPerimeter(A))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG{// Function to calculate the prefix sum of the// rows and the columns of the given matrixstatic void prefix_calculate(int [,] A, int [,] row, int [,] col){ // Number of rows and cols int n = (int)A.GetLength(0); int m = (int)A.GetLength(1); // First column of the row prefix array for (int i = 0; i < n; ++i) { row[i, 0] = A[i, 0]; } // Update the prefix sum for the rows for (int i = 0; i < n; ++i) { for (int j = 1; j < m; ++j) { row[i, j] = row[i, j - 1] + A[i, j]; } } // First row of the column prefix array for (int i = 0; i < m; ++i) { col[0, i] = A[0, i]; } // Update the prefix sum for the columns for (int i = 0; i < m; ++i) { for (int j = 1; j < n; ++j) { col[j, i] = A[j, i] + col[j - 1, i]; } }}// Function to return the perimeter// of the square having top-left corner// at (i, j) and size kstatic int perimeter(int i, int j, int k, int [,] row, int [,] col, int [,] A){ // i and j represent the top left // corner of the square and // k is the size int row_s, col_s; // Get the upper row sum if (j == 0) row_s = 0; else row_s = row[i, j - 1]; // Get the left column sum if (i == 0) col_s = 0; else col_s = col[i - 1, j]; int upper_row = row[i, j + k] - row_s; int left_col = col[i + k, j] - col_s; // At the distance of k in // both direction if (j == 0) row_s = 0; else row_s = row[i + k, j - 1]; if (i == 0) col_s = 0; else col_s = col[i - 1, j + k]; int lower_row = row[i + k, j + k] - row_s; int right_col = col[i + k, j + k] - col_s; // The perimeter will be // sum of all the values int sum = upper_row + lower_row + left_col + right_col; // Since all the corners are // included twice, they need to // be subtract from the sum sum -= (A[i, j] + A[i + k, j] + A[i, j + k] + A[i + k, j + k]); return sum;}// Function to return the maximum perimeter// of a square in the given matrixstatic int maxPerimeter(int [,] A){ // Number of rows and cols int n = (int)A.GetLength(0); int m = (int)A.GetLength(1); int [,] row = new int[n, m]; int [,] col = new int[n, m]; // Function call to calculate // the prefix sum of rows and cols prefix_calculate(A, row, col); // To store the maximum perimeter int maxPer = 0; // Nested loops to choose the top-left // corner of the square for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // Loop for the size of the square for (int k = 0; k < Math.Min(n - i, m - j); ++k) { // Get the perimeter of the current square int perimtr = perimeter(i, j, k, row, col, A); // Update the maximum perimeter so far maxPer = Math.Max(maxPer, perimtr); } } } return maxPer;}// Driver codepublic static void Main(String[] args){ int [,] A = {{ 1, 1, 0 }, { 1, 1, 1 }, { 0, 1, 1 }}; Console.Write(maxPerimeter(A));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript implementation of the approach// Function to calculate the prefix sum of the// rows and the columns of the given matrixfunction prefix_calculate(A, row, col){ // Number of rows and cols let n = A.length; let m = A[0].length; // First column of the row prefix array for (let i = 0; i < n; ++i) { row[i][0] = A[i][0]; } // Update the prefix sum for the rows for (let i = 0; i < n; ++i) { for (let j = 1; j < m; ++j) { row[i][j] = row[i][j - 1] + A[i][j]; } } // First row of the column prefix array for (let i = 0; i < m; ++i) { col[0][i] = A[0][i]; } // Update the prefix sum for the columns for (let i = 0; i < m; ++i) { for (let j = 1; j < n; ++j) { col[j][i] = A[j][i] + col[j - 1][i]; } }}// Function to return the perimeter// of the square having top-left corner// at (i, j) and size kfunction perimeter(i,j,k,row,col,A){ // i and j represent the top left // corner of the square and // k is the size let row_s, col_s; // Get the upper row sum if (j == 0) row_s = 0; else row_s = row[i][j - 1]; // Get the left column sum if (i == 0) col_s = 0; else col_s = col[i - 1][j]; let upper_row = row[i][j + k] - row_s; let left_col = col[i + k][j] - col_s; // At the distance of k in // both direction if (j == 0) row_s = 0; else row_s = row[i + k][j - 1]; if (i == 0) col_s = 0; else col_s = col[i - 1][j + k]; let lower_row = row[i + k][j + k] - row_s; let right_col = col[i + k][j + k] - col_s; // The perimeter will be // sum of all the values let sum = upper_row + lower_row + left_col + right_col; // Since all the corners are // included twice, they need to // be subtract from the sum sum -= (A[i][j] + A[i + k][j] + A[i][j + k] + A[i + k][j + k]); return sum;}// Function to return the maximum perimeter// of a square in the given matrixfunction maxPerimeter(A){ // Number of rows and cols let n = A.length; let m = A[0].length; let row = new Array(n); let col = new Array(n); for(let i=0;i<n;i++) { row[i]=new Array(m); col[i]=new Array(m); } // Function call to calculate // the prefix sum of rows and cols prefix_calculate(A, row, col); // To store the maximum perimeter let maxPer = 0; // Nested loops to choose the top-left // corner of the square for (let i = 0; i < n; ++i) { for (let j = 0; j < m; ++j) { // Loop for the size of the square for (let k = 0; k < Math.min(n - i, m - j); ++k) { // Get the perimeter of the current square let perimtr = perimeter(i, j, k, row, col, A); // Update the maximum perimeter so far maxPer = Math.max(maxPer, perimtr); } } } return maxPer;}// Driver codelet A = [[1, 1, 0 ],[1, 1, 1],[0, 1, 1]];document.write(maxPerimeter(A));// This code is contributed by unknown2108</script> |
Output:
6
Time Complexity: O(N * M * min(N, M))
Auxiliary Space: O(N*M)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
