Given a 2D square matrix of size N X N, the task is to count the number of mountains in the matrix.
An element in a matrix is said to be a mountain when all the surrounding elements (in all 8 directions) are smaller than the given element.
Examples:
Input: matrix =
{ { 4, 5, 6 },
{ 2, 1, 3 },
{ 7, 8, 9 } }
Output: 1
Explanation
Only mountain element = 9.
All the neighbouring elements
1, 3 and 8 are smaller than 9.
Input: matrix =
{ { 7, 8, 9 },
{ 1, 2, 3 },
{ 4, 5, 6 } }
Output: 2
Explanation
Mountain elements = 6 (2, 3 and 5)
and 9 (8, 2, and 3)
Approach: The idea is to iterate through the matrix and at the same time check neighbouring elements in all possible 8 directions. If the element is greater than all of them then increment the counter variable. Finally, return the counter.
- Create an auxiliary array of size (N + 2) X (N + 2).
- Fill all the border elements with INT_MIN value
- In the remaining array space of N X N, copy the original matrix
- Now check if an element is greater than the elements in all the 8 directions.
- Count the number of such elements and print it.
For example:
If matrix =
{ { 7, 8, 9 },
{ 1, 2, 3 },
{ 4, 5, 6 } }
The auxiliary array would be
{ { 0, 0, 0, 0, 0 },
{ 0, 7, 8, 9, 0 },
{ 0, 1, 2, 3, 0 },
{ 0, 4, 5, 6, 0 },
{ 0, 0, 0, 0, 0 } }
Below is the implementation of above approach :
C++
// C++ program find the count of// mountains in a given Matrix#include <bits/stdc++.h>using namespace std;const int MAX = 100;// Function to count number of mountains// in a given matrix of size nint countMountains(int a[][MAX], int n){ int A[n + 2][n + 2]; int count = 0; // form another matrix with one extra // layer of border elements. Border // elements will contain INT_MIN 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)) { // For border elements, // set value as INT_MIN A[i][j] = INT_MIN; } else { // For rest elements, just copy // it into new matrix A[i][j] = a[i - 1][j - 1]; } } } // Check for mountains 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])) { count++; } } } return count;}// Driver codeint main(){ int a[][MAX] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int n = 3; cout << countMountains(a, n); return 0;} |
Java
// Java program find the count of// mountains in a given Matriximport java.util.*;class GFG{ static int MAX = 100; // Function to count number of mountains// in a given matrix of size nstatic int countMountains(int a[][], int n){ int [][]A = new int[n + 2][n + 2]; int count = 0; // form another matrix with one extra // layer of border elements. Border // elements will contain Integer.MIN_VALUE 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)) { // For border elements, // set value as Integer.MIN_VALUE A[i][j] = Integer.MIN_VALUE; } else { // For rest elements, just copy // it into new matrix A[i][j] = a[i - 1][j - 1]; } } } // Check for mountains 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])) { count++; } } } return count;} // Driver codepublic static void main(String[] args){ int a[][] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int n = 3; System.out.print(countMountains(a, n));}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program find the count of# mountains in a given MatrixMAX = 100# Function to count number of mountains# in a given matrix of size ndef countMountains(a, n): A = [[0 for i in range(n+2)] for i in range(n+2)] count = 0 # form another matrix with one extra # layer of border elements. Border # elements will contain INT_MIN 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)): # For border elements, # set value as INT_MIN A[i][j] = float('-inf') else: # For rest elements, just copy # it into new matrix A[i][j] = a[i - 1][j - 1] # Check for mountains in the modified matrix for i in range(n + 1): for j in range(n + 1): 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 = count + 1 return count# Driver codea = [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]n = 3print(countMountains(a, n))# This code is contributed by Sanjit_Prasad |
C#
// C# program find the count of // mountains in a given Matrix using System;class GFG{ static int MAX = 100; // Function to count number of mountains // in a given matrix of size n static int countMountains(int [,]a, int n) { int [,]A = new int[n + 2,n + 2]; int count = 0; // form another matrix with one extra // layer of border elements. Border // elements will contain Integer.MIN_VALUE 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)) { // For border elements, // set value as Integer.MIN_VALUE A[i,j] = int.MinValue; } else { // For rest elements, just copy // it into new matrix A[i,j] = a[i - 1,j - 1]; } } } // Check for mountains 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])) { count++; } } } return count; } // Driver code public static void Main(string[] args) { int [,]a = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int n = 3; Console.WriteLine(countMountains(a, n)); } } // This code is contributed by AnkitRai01 |
Javascript
<script>//Javascript program find the count of// mountains in a given Matrix// Function to count number of mountains// in a given matrix of size nfunction countMountains(a, n){ var A= new Array(n+2).fill(0).map(() => new Array(n+2).fill(0)); var count = 0; // form another matrix with one extra // layer of border elements. Border // elements will contain INT_MIN 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)) { // For border elements, // set value as INT_MIN A[i][j] = Number.MIN_VALUE; } else { // For rest elements, just copy // it into new matrix A[i][j] = a[i - 1][j - 1]; } } } // Check for mountains 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])) { count++; } } } return count;}var a = [[ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ];var n = 3; document.write( countMountains(a, n));//This code is contributed by SoumikMondal</script> |
Output:
1
Performance Analysis:
- Time Complexity: In the above approach, we are doing two iterations. First one is on (N + 2) X (N + 2) elements to create the auxiliary matrix. Second one on N X N elements to find actual mountain element, so the time complexity is O(N X N).
- Auxiliary Space Complexity: In the above approach, we are using an auxiliary matrix of size (N + 2) X (N + 2), so Auxiliary space complexity is O(N *N).
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!
