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.
Solution 1:
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[0].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[0].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.
Solution 2:
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[0][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][0] << " ";
}
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[0].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[0].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[0][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][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.
Special thanks to Prathap P for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article