Count the number of the cavity in the 2d matrix, a cavity is defined as all the surrounding numbers are greater than the mid number.
Examples:
Input : a = {{4, 5, 6}, {7, 1, 5}, {4, 5, 6}}
Output : 1Input : a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
Output : 1
Source: Ola Interview Experience Set 13
Below is the implementation of above approach.
C++
// C++ program find number of cavities in a matrix #include <bits/stdc++.h> using namespace std; const int MAX = 100; int countCavities( int a[][MAX], int n) { int A[n + 2][n + 2]; int coun = 0; // form another matrix with one extra layer of // boundary elements. // Boundary elements will contain max value. for ( int i = 0; i < n + 2; i++) { for ( int j = 0; j < n + 2; j++) { if ((i == 0) || (j == 0) || (i == n + 1) || (j == n + 1)) A[i][j] = INT_MAX; else A[i][j] = a[i - 1][j - 1]; } } // Check for cavities in the modified matrix for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { // check for all directions if ((A[i][j] < A[i - 1][j]) && (A[i][j] < A[i + 1][j]) && (A[i][j] < A[i][j - 1]) && (A[i][j] < A[i][j + 1]) && (A[i][j] < A[i - 1][j - 1]) && (A[i][j] < A[i + 1][j + 1]) && (A[i][j] < A[i - 1][j + 1]) && (A[i][j] < A[i + 1][j - 1])) coun++; } } return coun; } int main() { int a[][MAX] = { { 4, 5, 6 }, { 7, 1, 5 }, { 4, 5, 6 } }; int n = 3; cout << countCavities(a, n); return 0; } |
Java
// Java program find number of cavities in a matrix class GfG { static int MAX = 100 ; static int countCavities( int a[][], int n) { int A[][] = new int [n + 2 ][n + 2 ]; int coun = 0 ; // form another matrix with one extra layer of // boundary elements. // Boundary elements will contain max value. for ( int i = 0 ; i < n + 2 ; i++) { for ( int j = 0 ; j < n + 2 ; j++) { if ((i == 0 ) || (j == 0 ) || (i == n + 1 ) || (j == n + 1 )) A[i][j] = Integer.MAX_VALUE; else A[i][j] = a[i - 1 ][j - 1 ]; } } // Check for cavities in the modified matrix for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= n; j++) { // check for all directions if ((A[i][j] < A[i - 1 ][j]) && (A[i][j] < A[i + 1 ][j]) && (A[i][j] < A[i][j - 1 ]) && (A[i][j] < A[i][j + 1 ]) && (A[i][j] < A[i - 1 ][j - 1 ]) && (A[i][j] < A[i + 1 ][j + 1 ]) && (A[i][j] < A[i - 1 ][j + 1 ]) && (A[i][j] < A[i + 1 ][j - 1 ])) coun++; } } return coun; } public static void main(String[] args) { int a[][] = new int [][]{{ 4 , 5 , 6 }, { 7 , 1 , 5 }, { 4 , 5 , 6 }}; int n = 3 ; System.out.println(countCavities(a, n)); } } |
Python3
# Python program find number of cavities in a matrix import sys MAX = 100 def countCavities(a, n): A = [[ 0 for i in range (n + 2 )] for j in range (n + 2 )] count = 0 # form another matrix with one extra layer of # boundary elements. # Boundary elements will contain max value. for i in range (n + 2 ): for j in range (n + 2 ): if ((i = = 0 ) or (j = = 0 ) or (i = = n + 1 ) or (j = = n + 1 )): A[i][j] = sys.maxsize else : A[i][j] = a[i - 1 ][j - 1 ] # Check for cavities in the modified matrix for i in range ( 1 ,n): for j in range ( 1 ,n): # check for all directions if ((A[i][j] < A[i - 1 ][j]) and (A[i][j] < A[i + 1 ][j]) and (A[i][j] < A[i][j - 1 ]) and (A[i][j] < A[i][j + 1 ]) and (A[i][j] < A[i - 1 ][j - 1 ]) and (A[i][j] < A[i + 1 ][j + 1 ]) and (A[i][j] < A[i - 1 ][j + 1 ]) and (A[i][j] < A[i + 1 ][j - 1 ])): count + = 1 return count # driver program a = [ [ 4 , 5 , 6 ], [ 7 , 1 , 5 ], [ 4 , 5 , 6 ] ] n = 3 print (countCavities(a, n)) # This code is contributed by shinjanpatra |
C#
// C# program find number of cavities in a matrix using System; class GfG { static int MAX = 100; static int countCavities( int [,]a, int n) { int [,]A = new int [n + 2, n + 2]; int coun = 0; // form another matrix with one extra layer of // boundary elements. // Boundary elements will contain max value. for ( int i = 0; i < n + 2; i++) { for ( int j = 0; j < n + 2; j++) { if ((i == 0) || (j == 0) || (i == n + 1) || (j == n + 1)) A[i, j] = int .MaxValue; else A[i, j] = a[i - 1, j - 1]; } } // Check for cavities in the modified matrix for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { // check for all directions if ((A[i, j] < A[i - 1, j]) && (A[i, j] < A[i + 1, j]) && (A[i, j] < A[i, j - 1]) && (A[i, j] < A[i, j + 1]) && (A[i, j] < A[i - 1, j - 1]) && (A[i, j] < A[i + 1, j + 1]) && (A[i, j] < A[i - 1, j + 1]) && (A[i, j] < A[i + 1, j - 1])) coun++; } } return coun; } public static void Main(String[] args) { int [,]a = new int [,]{{ 4, 5, 6 }, { 7, 1, 5 }, { 4, 5, 6 }}; int n = 3; Console.WriteLine(countCavities(a, n)); } } // This code contributed by Rajput-Ji |
PHP
<?php // PHP program find number of cavities // in a matrix function countCavities( $a , $n ) { $A = array (); $coun = 0; // form another matrix with one extra // layer of boundary elements. // Boundary elements will contain // max value. for ( $i = 0; $i < $n + 2; $i ++) { for ( $j = 0; $j < $n + 2; $j ++) { if (( $i == 0) || ( $j == 0) || ( $i == $n + 1) || ( $j == $n + 1)) $A [ $i ][ $j ] = 100; else $A [ $i ][ $j ] = $a [ $i - 1][ $j - 1]; } } // Check for cavities in the modified matrix for ( $i = 1; $i <= $n ; $i ++) { for ( $j = 1; $j <= $n ; $j ++) { // check for all directions if (( $A [ $i ][ $j ] < $A [ $i - 1][ $j ]) && ( $A [ $i ][ $j ] < $A [ $i + 1][ $j ]) && ( $A [ $i ][ $j ] < $A [ $i ][ $j - 1]) && ( $A [ $i ][ $j ] < $A [ $i ][ $j + 1]) && ( $A [ $i ][ $j ] < $A [ $i - 1][ $j - 1]) && ( $A [ $i ][ $j ] < $A [ $i + 1][ $j + 1]) && ( $A [ $i ][ $j ] < $A [ $i - 1][ $j + 1]) && ( $A [ $i ][ $j ] < $A [ $i + 1][ $j - 1])) $coun ++; } } return $coun ; } // Driver Code $a = array ( array (4, 5, 6), array (7, 1, 5), array (4, 5, 6)); $n = 3; echo (countCavities( $a , $n )); // This code is contributed by Code_Mech |
Javascript
<script> // Javascript program find number of cavities in a matrix MAX = 100; function countCavities( a, n) { var A = new Array(n+2).fill(0).map(() => new Array(n+2).fill(0)); var coun = 0; // form another matrix with one extra layer of // boundary elements. // Boundary elements will contain max value. for ( var i = 0; i < n + 2; i++) { for ( var j = 0; j < n + 2; j++) { if ((i == 0) || (j == 0) || (i == n + 1) || (j == n + 1)) A[i][j] = Number.MAX_VALUE; else A[i][j] = a[i - 1][j - 1]; } } // Check for cavities in the modified matrix for ( var i = 1; i <= n; i++) { for ( var j = 1; j <= n; j++) { // check for all directions if ((A[i][j] < A[i - 1][j]) && (A[i][j] < A[i + 1][j]) && (A[i][j] < A[i][j - 1]) && (A[i][j] < A[i][j + 1]) && (A[i][j] < A[i - 1][j - 1]) && (A[i][j] < A[i + 1][j + 1]) && (A[i][j] < A[i - 1][j + 1]) && (A[i][j] < A[i + 1][j - 1])) coun++; } } return coun; } var a = [ [ 4, 5, 6 ],[ 7, 1, 5 ], [ 4, 5, 6 ] ]; var n = 3; document.write( countCavities(a, n)); // This code is contributed by SoumikMondal </script> |
1
Optimizations We can avoid use of extra space and extra conditions by following below steps.
- Explicitly check for four corner elements, remaining elements of first row, last row, first column and last column.
- Check for remaining elements using above logic.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!