# Matrix Boundary Traversal

Problem Statement: Given a matrix, print only the boundary elements of the matrix. Boundary elements are the ones that are in the top and bottom rows and the first and last columns.

```Example:
Input:
arr = {{1,2,3,4},
{5,6,7,8},
{4,3,2,1},
{8,7,6,5}}
Output:
1 2 3 4
5     8
4     1
8 7 6 5

Explanation:
Only the boundary elements are printed, other elements are ignored.```

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

### Intuition:

Each element can be found by 2 indexes(say i,j), boundary elements are those which have either one of the indexes 0 or maximum value.

### Approach: • As usual we traverse through the matrix using a nested loop.
• If i is either 0 or m-1 (matrix has m rows), then that element is definitely a boundary element.
• Or if j is either 0 or n-1 (matrix has n columns), then that element is also a boundary element. We can print the element.
• If neither of the above conditions satisfy, then it is not a boundary element. We print space instead.

Code:

## C++ Code

``````#include<bits/stdc++.h>

using namespace std;

void printMatrixBoundBF(vector < vector < int >> arr, int m, int n) {

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
cout << arr[i][j] << " ";
else
cout << "  ";
cout << "\n";
}

}

int main() {

vector<vector<int>> arr{
{1,2,3,4},
{5,6,7,8},
{4,3,2,1},
{8,7,6,5}
};
int m = arr.size(), n = arr.size();
cout << "The boundary elements are:" << endl;
printMatrixBoundBF(arr, m, n);
return 0;
}``````

Output:

The boundary elements are:
1 2 3 4
5 8
4 1
8 7 6 5

Time Complexity: O(m*n) time taken to traverse the matrix.

Space Complexity: O(1), we are not using any extra space.

## Java Code

``````import java.util.*;

public class Solution {

public static void main(String[] args) {
int[][] arr = {
{1,2,3,4},
{5,6,7,8},
{4,3,2,1},
{8,7,6,5}
};
int m = arr.length, n = arr.length;
System.out.println("The boundary elements are:");
printMatrixBoundBF(arr, m, n);
}

public static void printMatrixBoundBF(int[][] arr, int m, int n) {

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
System.out.print(arr[i][j] + " ");
else
System.out.print("  ");
System.out.println();
}

}

}``````

Output:

The boundary elements are:
1 2 3 4
5 8
4 1
8 7 6 5

Time Complexity: O(m*n) time taken to traverse the matrix.

Space Complexity: O(1), we are not using any extra space.

### Intuition:

If we are worried about only the boundary elements, that is we don’t want the output to have matrix representation, then we can only traverse the first and last rows and columns.

### Approach:

• This method is so simple and time efficient. We first traverse the first row, with fixing row index as 0.
• Then we traverse the last column, by fixing columns index as n-1.
• Then we traverse the last row, by fixing the row index as m-1.
• Then we traverse the first column, by fixing column index as 0.
• By this way, we can avoid traversing the whole matrix to find the boundary elements.

Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;

void printMatrixBoundOptimal(vector < vector < int >> arr, int m,
int n) {

for (int i = 0; i < n; i++)
cout << arr[i] << " ";

for (int i = 1; i < m; i++)
cout << arr[i][n - 1] << " ";

if (m > 1)
for (int i = n - 2; i >= 0; i--)
cout << arr[m - 1][i] << " ";

if (n > 1)
for (int i = m - 2; i >= 1; i--)
cout << arr[i] << " ";

}

int main() {

vector<vector<int>> arr{{1,2,3,4},
{5,6,7,8},
{4,3,2,1},
{8,7,6,5}};
int m = arr.size(), n = arr.size();
cout << "The boundary elements are:" << endl;
printMatrixBoundOptimal(arr, m, n);
return 0;
}``````

Output:

The boundary elements are:
1 2 3 4 8 1 5 6 7 8 4 5

Time Complexity: O(2m + 2n) ~ O(m+n), as a whole we traverse 2 rows and 2 columns, so the overall time complexity is (m+n).

Space Complexity: O(1), we are not using any extra space.

## Java Code

``````import java.util.*;

public class Solution {

public static void main(String[] args) {
int[][] arr = {
{1,2,3,4},
{5,6,7,8},
{4,3,2,1},
{8,7,6,5}
};
int m = arr.length, n = arr.length;
System.out.println("The boundary elements are:");
printMatrixBoundBF(arr, m, n);
}

public static void printMatrixBoundBF(int[][] arr, int m, int n) {

for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");

for (int i = 1; i < m; i++)
System.out.print(arr[i][n - 1] + " ");

if (m > 1)
for (int i = n - 2; i >= 0; i--)
System.out.print(arr[m - 1][i] + " ");

if (n > 1)
for (int i = m - 2; i >= 1; i--)
System.out.print(arr[i] + " ");

}

}``````

Output:

The boundary elements are:
1 2 3 4 8 1 5 6 7 8 4 5

Time Complexity: O(2m + 2n) ~ O(m+n), as a whole we traverse 2 rows and 2 columns, so the overall time complexity is (m+n).

Space Complexity: O(1), we are not using any extra space.