Return All Boundary Elements of a Matrix in C++

boundary elements of a matrix

The boundary elements of a matrix are those elements that lie along its edges. A matrix is a two-dimensional array that can be of any given size. The boundary elements are those present on the edges of the matrix.

Problem Description

We are given a matrix of size m × n. We need to find the boundary elements of the matrix. Boundary elements are the elements present on the top and bottom rows and the first and last columns of the matrix.

Below are examples to understand the boundary traversal of a matrix:

Example

Input

1 2 3
4 5 6
7 8 9

Output

1 2 3
4   6
7 8 9

Explanation: All these elements lie along the boundary of the given matrix.

Input

1 2 3 4
5 6 7 8
9 10 11 12

Output

1 2 3 4
5       8
9 10 11 12

Explanation: All the elements of the matrix lie along its boundary.

Using Nested Loop Traversal Approach

In this approach, we use a nested loop to traverse the matrix. Suppose the matrix is of size m × n. We check for rows: if the row index is 0 or m - 1, these elements are boundary elements. Similarly, for columns, if the column index is 0 or n - 1, these elements are boundary elements. If the element is not in these rows or columns, it is not a boundary element and is not printed.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

void printBoundaryElements(const vector<vector<int>>& matrix, int rows, int cols) {
    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < cols; col++) {
            if (row == 0 || row == rows - 1 || col == 0 || col == cols - 1)
                cout << matrix[row][col] << " ";
            else
                cout << " ";
        }
        cout << "\n";
    }
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    int matrix_rows = matrix.size();
    int matrix_cols = matrix[0].size();

    cout << "Boundary elements of the matrix are:" << endl;
    printBoundaryElements(matrix, matrix_rows, matrix_cols);

    return 0;
}

Output

Boundary elements of the matrix are:
1 2 3 4 
5       8 
9       12 
13 14 15 16

Time Complexity: O(m × n), as we are traversing the matrix using a nested loop.

Space Complexity: O(1), constant space.

Optimized (Edge Traversal) Approach

If we want to return all boundary elements of the matrix, we can traverse both edge rows and columns separately. This reduces the time complexity to O(m + n) from O(m × n). We start by traversing the first row, then the last column, followed by the last row, and finally the first column.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

void printBoundaryElements(const vector<vector<int>>& matrix, int totalRows, int totalCols) {
    // Print the top row
    for (int col = 0; col < totalCols; col++) {
        cout << matrix[0][col] << " ";
    }

    // Print the right column
    for (int row = 1; row < totalRows; row++) {
        cout << matrix[row][totalCols - 1] << " ";
    }

    // Print the bottom row (if more than one row)
    if (totalRows > 1) {
        for (int col = totalCols - 2; col >= 0; col--) {
            cout << matrix[totalRows - 1][col] << " ";
        }
    }

    // Print the left column (if more than one column)
    if (totalCols > 1) {
        for (int row = totalRows - 2; row > 0; row--) {
            cout << matrix[row][0] << " ";
        }
    }

    cout << "\n";
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    int matrixRows = matrix.size();
    int matrixCols = matrix[0].size();

    cout << "Boundary elements of the matrix are:" << endl;
    printBoundaryElements(matrix, matrixRows, matrixCols);

    return 0;
}

Output

Boundary elements of the matrix are:
1 2 3 4 8 12 16 15 14 13 9 5

Time Complexity: O(m + n), as we are traversing rows and columns twice.

Space Complexity: O(1), constant space.