Boundary elements of a Matrix
1. Printing Boundary Elements of a Matrix:
Given a matrix of size n x m. Print the boundary elements of the matrix. Boundary elements are those elements that are not surrounded by elements in all four directions, i.e. elements in the first row, first column, last row, and last column
Examples:
Input: 1 2 3 4
5 6 7 8
1 2 3 4
5 6 7 8Output :
1 2 3 4
5 8
1 4
5 6 7 8Input:
1 2 3
5 6 7
1 2 3Output:
1 2 3
5 7
1 2 3
Approach: To solve the problem follow the below idea:
The idea is simple. Traverse the matrix and check for every element if that element lies on the boundary or not, if yes then print the element else print space character
Follow the given steps to solve the problem:
- Traverse the array from start to end
- Assign the outer loop to point to the row and the inner row to traverse the elements of row
- If the element lies in the boundary of matrix, then print the element, i.e. if the element lies in 1st row, 1st column, last row, last column
- If the element is not a boundary element print a blank space
Below is the implementation of the above approach:
C++
// C++ program to print boundary element of // matrix. #include <bits/stdc++.h> using namespace std; const int MAX = 100; void printBoundary( int a[][MAX], int m, int n) { for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { if (i == 0 || j == 0 || i == m - 1 || j == n - 1) cout << a[i][j] << " " ; else cout << " " << " " ; } cout << "\n" ; } } // Driver code int main() { int a[4][MAX] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 1, 2, 3, 4 }, { 5, 6, 7, 8 } }; // Function call printBoundary(a, 4, 4); return 0; } |
Java
// JAVA Code for Boundary elements of a Matrix import java.io.*; public class GFG { public static void printBoundary( int a[][], int m, int n) { for ( int i = 0 ; i < m; i++) { for ( int j = 0 ; j < n; j++) { if (i == 0 ) System.out.print(a[i][j] + " " ); else if (i == m - 1 ) System.out.print(a[i][j] + " " ); else if (j == 0 ) System.out.print(a[i][j] + " " ); else if (j == n - 1 ) System.out.print(a[i][j] + " " ); else System.out.print( " " ); } System.out.println( "" ); } } /* Driver code */ public static void main(String[] args) { int a[][] = { { 1 , 2 , 3 , 4 }, { 5 , 6 , 7 , 8 }, { 1 , 2 , 3 , 4 }, { 5 , 6 , 7 , 8 } }; // Function call printBoundary(a, 4 , 4 ); } } // This code is contributed by Arnav Kr. Mandal. |
Python
# Python program to print boundary element # of the matrix. MAX = 100 def printBoundary(a, m, n): for i in range (m): for j in range (n): if (i = = 0 ): print a[i][j], elif (i = = m - 1 ): print a[i][j], elif (j = = 0 ): print a[i][j], elif (j = = n - 1 ): print a[i][j], else : print " " , print # Driver code if __name__ = = "__main__" : a = [[ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ], [ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ]] # Function call printBoundary(a, 4 , 4 ) # This code is contributed by Sachin Bisht |
C#
// C# Code for Boundary // elements of a Matrix using System; class GFG { public static void printBoundary( int [, ] a, int m, int n) { for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { if (i == 0) Console.Write(a[i, j] + " " ); else if (i == m - 1) Console.Write(a[i, j] + " " ); else if (j == 0) Console.Write(a[i, j] + " " ); else if (j == n - 1) Console.Write(a[i, j] + " " ); else Console.Write( " " ); } Console.WriteLine( " " ); } } // Driver Code static public void Main() { int [, ] a = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 1, 2, 3, 4 }, { 5, 6, 7, 8 } }; // Function call printBoundary(a, 4, 4); } } // This code is contributed by ajit |
Javascript
<script> // JavaScript Code for Boundary // elements of a Matrix function printBoundary(a, m, n) { for ( var i = 0; i < m; i++) { for ( var j = 0; j < n; j++) { if (i == 0) document.write(a[i][j] + '\xa0' ); else if (i == m - 1) document.write(a[i][j] + '\xa0' ); else if (j == 0) document.write(a[i][j] + '\xa0' ); else if (j == n - 1) document.write(a[i][j] + '\xa0' ); else document.write( "\xa0\xa0\xa0" ); } document.write( "\xa0<br>" ); } } // Driver Code var a = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ]]; printBoundary(a, 4, 4); </script> |
PHP
<?php // PHP program to print // boundary element of // matrix. $MAX = 100; function printBoundary( $a , $m , $n ) { global $MAX ; for ( $i = 0; $i < $m ; $i ++) { for ( $j = 0; $j < $n ; $j ++) { if ( $i == 0) echo $a [ $i ][ $j ], " " ; else if ( $i == $m - 1) echo $a [ $i ][ $j ], " " ; else if ( $j == 0) echo $a [ $i ][ $j ], " " ; else if ( $j == $n - 1) echo $a [ $i ][ $j ], " " ; else echo " " , " " ; } echo "\n" ; } } // Driver code $a = array ( array ( 1, 2, 3, 4 ), array ( 5, 6, 7, 8 ), array ( 1, 2, 3, 4 ), array ( 5, 6, 7, 8 )); // Function call printBoundary( $a , 4, 4); // This code is contributed // by akt_mit ?> |
1 2 3 4 5 8 1 4 5 6 7 8
Time Complexity: O(N2), where N is the size of the array.
Auxiliary Space: O(1)
Second approach(efficient approach for printing boundary elements in matrix):
If we traverse only through boundary elements , rather than traversing the whole array , then we can reduce its quadratic time complexity to linear complexity.
Steps to implement above approach :
- Traverse only the first row and print elements.
- Traverse only the last column and print elements.
- Traverse only the last row and print elements.
- Traverse only the first column and print elements.
Implementation of above approach :
C++
#include <iostream> #include <vector> using namespace std; // function to print boundary elements vector< int > boundaryTraversal(vector<vector< int > > mi, int n, int m) { vector< int > ans; // print boundary elements if (n==1){ for ( int i=0;i<m;i++) ans.push_back(mi[0][i]); return ans; } if (m==1){ for ( int i=0;i<n;i++) ans.push_back(mi[i][0]); return ans; } for ( int i=0;i<m;i++){ ans.push_back(mi[0][i]); } for ( int i=1;i<n;i++){ ans.push_back(mi[i][m-1]); } for ( int i=m-2;i>=0;i--){ ans.push_back(mi[n-1][i]); } for ( int i=n-2;i>0;i--){ ans.push_back(mi[i][0]); } return ans; } int main() { // test case example int n = 4, m = 4; vector<vector< int >> matrix = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16} }; // function call vector< int > result = boundaryTraversal(matrix, n, m); // Print the non-boundary elements cout << "Boundary Traversal: " ; for ( int i = 0; i < result.size(); i++) { cout << result[i] << " " ; } cout << endl; return 0; } |
Java
import java.util.ArrayList; import java.util.List; public class BoundaryTraversal { // Function to print boundary elements public static List<Integer> boundaryTraversal( int [][] matrix, int n, int m) { List<Integer> ans = new ArrayList<>(); // Print boundary elements if (n == 1 ) { for ( int i = 0 ; i < m; i++) ans.add(matrix[ 0 ][i]); return ans; } if (m == 1 ) { for ( int i = 0 ; i < n; i++) ans.add(matrix[i][ 0 ]); return ans; } // Traverse the matrix in a clockwise manner for ( int i = 0 ; i < m; i++) { ans.add(matrix[ 0 ][i]); } for ( int i = 1 ; i < n; i++) { ans.add(matrix[i][m - 1 ]); } for ( int i = m - 2 ; i >= 0 ; i--) { ans.add(matrix[n - 1 ][i]); } for ( int i = n - 2 ; i > 0 ; i--) { ans.add(matrix[i][ 0 ]); } return ans; } public static void main(String[] args) { // Test case example int n = 4 , m = 4 ; int [][] matrix = { { 1 , 2 , 3 , 4 }, { 5 , 6 , 7 , 8 }, { 9 , 10 , 11 , 12 }, { 13 , 14 , 15 , 16 } }; // Function call List<Integer> result = boundaryTraversal(matrix, n, m); // Print the boundary elements System.out.print( "Boundary Traversal: " ); for ( int i = 0 ; i < result.size(); i++) { System.out.print(result.get(i) + " " ); } System.out.println(); } } |
Python3
def boundaryTraversal(matrix, n, m): ans = [] # print boundary elements if n = = 1 : ans.extend(matrix[ 0 ]) return ans if m = = 1 : for i in range (n): ans.append(matrix[i][ 0 ]) return ans for i in range (m): ans.append(matrix[ 0 ][i]) for i in range ( 1 , n): ans.append(matrix[i][m - 1 ]) for i in range (m - 2 , - 1 , - 1 ): ans.append(matrix[n - 1 ][i]) for i in range (n - 2 , 0 , - 1 ): ans.append(matrix[i][ 0 ]) return ans # test case example n, m = 4 , 4 matrix = [ [ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ], [ 9 , 10 , 11 , 12 ], [ 13 , 14 , 15 , 16 ] ] # function call result = boundaryTraversal(matrix, n, m) # Print the non-boundary elements print ( "Boundary Traversal:" , end = " " ) for elem in result: print (elem, end = " " ) print () |
C#
using System; using System.Collections.Generic; class Program { // Function to print boundary elements static List< int > BoundaryTraversal( int [][] matrix, int n, int m) { List< int > ans = new List< int >(); // Print boundary elements if (n == 1) { for ( int i = 0; i < m; i++) ans.Add(matrix[0][i]); return ans; } if (m == 1) { for ( int i = 0; i < n; i++) ans.Add(matrix[i][0]); return ans; } for ( int i = 0; i < m; i++) { ans.Add(matrix[0][i]); } for ( int i = 1; i < n; i++) { ans.Add(matrix[i][m - 1]); } for ( int i = m - 2; i >= 0; i--) { ans.Add(matrix[n - 1][i]); } for ( int i = n - 2; i > 0; i--) { ans.Add(matrix[i][0]); } return ans; } static void Main() { // Test case example int n = 4, m = 4; int [][] matrix = new int [][] { new int [] { 1, 2, 3, 4 }, new int [] { 5, 6, 7, 8 }, new int [] { 9, 10, 11, 12 }, new int [] { 13, 14, 15, 16 } }; // Function call List< int > result = BoundaryTraversal(matrix, n, m); // Print the boundary elements Console.Write( "Boundary Traversal: " ); foreach ( int value in result) { Console.Write(value + " " ); } Console.WriteLine(); } } |
Javascript
function boundaryTraversal(matrix) { const ans = []; // print boundary elements const n = matrix.length; const m = matrix[0].length; if (n === 1) { for (let i = 0; i < m; i++) { ans.push(matrix[0][i]); } return ans; } if (m === 1) { for (let i = 0; i < n; i++) { ans.push(matrix[i][0]); } return ans; } for (let i = 0; i < m; i++) { ans.push(matrix[0][i]); } for (let i = 1; i < n; i++) { ans.push(matrix[i][m - 1]); } for (let i = m - 2; i >= 0; i--) { ans.push(matrix[n - 1][i]); } for (let i = n - 2; i > 0; i--) { ans.push(matrix[i][0]); } return ans; } // test case example const n = 4, m = 4; const matrix = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16] ]; // function call const result = boundaryTraversal(matrix); // Print the non-boundary elements console.log( "Boundary Traversal: " + result.join( " " )); |
Boundary Traversal: 1 2 3 4 8 12 16 15 14 13 9 5
Time Complexity: O(N+M)
Auxiliary Space: O(1)
2. Finding sum of boundary elements:
Given a matrix of size n x m. Find the sum of boundary elements of the matrix. Boundary elements are those elements which are not surrounded by elements in all four directions, i.e. elements in the first row, first column, last row, and last column
Examples:
Input: 1 2 3 4
5 6 7 8
1 2 3 4
5 6 7 8Output: 54
Explanation: The boundary elements of the matrix1 2 3 4
5 8
1 4
5 6 7 8Sum = 1+2+3+4+5+8+1+4+5+6+7+8 = 54
Input: 1 2 3
5 6 7
1 2 3Output: 24
Explanation: The boundary elements of the matrix1 2 3
5 7
1 2 3Sum = 1+2+3+5+7+1+2+3 = 24
To solve the problem follow the below idea:
The idea is simple. Traverse the matrix and check for every element if that element lies on the boundary or not, if yes then add them to get the sum of all the boundary elements
Follow the given steps to solve the problem:
- Create a variable to store the sum and Traverse the array from start to end
- Assign the outer loop to point to the row and the inner row to traverse the elements of the row
- If the element lies in the boundary of the matrix then add the element to the sum, i.e. if the element lies in the 1st row, 1st column, last row, and last column
- Print the sum
Below is the implementation of the above approach:
C++
// C++ program to find sum of boundary elements // of matrix. #include <bits/stdc++.h> using namespace std; const int MAX = 100; int getBoundarySum( int a[][MAX], int m, int n) { long long int sum = 0; for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { if (i == 0) sum += a[i][j]; else if (i == m - 1) sum += a[i][j]; else if (j == 0) sum += a[i][j]; else if (j == n - 1) sum += a[i][j]; } } return sum; } // Driver code int main() { int a[][MAX] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 1, 2, 3, 4 }, { 5, 6, 7, 8 } }; // Function call long long int sum = getBoundarySum(a, 4, 4); cout << "Sum of boundary elements is " << sum; return 0; } |
Java
// JAVA Code for Finding sum of boundary elements import java.io.*; public class GFG { public static long getBoundarySum( int a[][], int m, int n) { long sum = 0 ; for ( int i = 0 ; i < m; i++) { for ( int j = 0 ; j < n; j++) { if (i == 0 ) sum += a[i][j]; else if (i == m - 1 ) sum += a[i][j]; else if (j == 0 ) sum += a[i][j]; else if (j == n - 1 ) sum += a[i][j]; } } return sum; } /* Driver code */ public static void main(String[] args) { int a[][] = { { 1 , 2 , 3 , 4 }, { 5 , 6 , 7 , 8 }, { 1 , 2 , 3 , 4 }, { 5 , 6 , 7 , 8 } }; long sum = getBoundarySum(a, 4 , 4 ); // Function call System.out.println( "Sum of boundary elements" + " is " + sum); } } // This code is contributed by Arnav Kr. Mandal. |
Python
# Python program to print boundary element # of the matrix. MAX = 100 def printBoundary(a, m, n): sum = 0 for i in range (m): for j in range (n): if (i = = 0 ): sum + = a[i][j] elif (i = = m - 1 ): sum + = a[i][j] elif (j = = 0 ): sum + = a[i][j] elif (j = = n - 1 ): sum + = a[i][j] return sum # Driver code if __name__ = = "__main__" : a = [[ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ], [ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ]] # Function call sum = printBoundary(a, 4 , 4 ) print "Sum of boundary elements is" , sum # This code is contributed by Sachin Bisht |
C#
// C# Code for Finding sum // of boundary elements using System; class GFG { public static long getBoundarySum( int [, ] a, int m, int n) { long sum = 0; for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { if (i == 0) sum += a[i, j]; else if (i == m - 1) sum += a[i, j]; else if (j == 0) sum += a[i, j]; else if (j == n - 1) sum += a[i, j]; } } return sum; } // Driver Code static public void Main() { int [, ] a = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 1, 2, 3, 4 }, { 5, 6, 7, 8 } }; // Function call long sum = getBoundarySum(a, 4, 4); Console.WriteLine( "Sum of boundary" + " elements is " + sum); } } // This code is contributed by ajit |
Javascript
<script> // Javascript code for finding sum // of boundary elements function getBoundarySum(a, m, n) { let sum = 0; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (i == 0) sum += a[i][j]; else if (i == m - 1) sum += a[i][j]; else if (j == 0) sum += a[i][j]; else if (j == n - 1) sum += a[i][j]; } } return sum; } // Driver code let a = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ] ]; let sum = getBoundarySum(a, 4, 4); document.write( "Sum of boundary elements" + " is " + sum); // This code is contributed by rameshtravel07 </script> |
PHP
<?php // PHP program to find // sum of boundary // elements of matrix. function getBoundarySum( $a , $m , $n ) { $sum = 0; for ( $i = 0; $i < $m ; $i ++) { for ( $j = 0; $j < $n ; $j ++) { if ( $i == 0) $sum += $a [ $i ][ $j ]; else if ( $i == $m - 1) $sum += $a [ $i ][ $j ]; else if ( $j == 0) $sum += $a [ $i ][ $j ]; else if ( $j == $n - 1) $sum += $a [ $i ][ $j ]; } } return $sum ; } // Driver code $a = array ( array (1, 2, 3, 4), array (5, 6, 7, 8), array (1, 2, 3, 4), array (5, 6, 7, 8)); // Function call $sum = getBoundarySum( $a , 4, 4); echo "Sum of boundary elements is " , $sum ; // This code is contributed by ajit ?> |
Sum of boundary elements is 54
Time Complexity: O(N2), where N is the size of the array
Auxiliary Space: O(1)
If you like w3wiki and would like to contribute, you can also write an article using write.w3wiki.net or mail your article to review-team@w3wiki.net. See your article appearing on the w3wiki main page and help other Beginner.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Contact Us