C++ Multi-Dimensional Arrays Problems: Sums, Diagonals, Transpose and Search

6
0

Multi-Dimensional Arrays: Problem Solving

Matrix problems become easier when the required result is connected to a specific traversal order or coordinate pattern. Row operations keep the row fixed, column operations keep the column fixed, diagonal operations derive coordinates from a single index, and matrix search examines cells until the target is found. These patterns turn apparently different problems into small variations of nested-loop traversal.

Problem 1: Calculate the Sum of Every Row

Given a matrix, calculate the sum of the elements in each row. Consider the following 2 × 3 matrix:

{{1, 2, 3}, {4, 5, 6}}

  • The sum of row 0 is 1 + 2 + 3 = 6.

  • The sum of row 1 is 4 + 5 + 6 = 15.

Row-Wise Accumulation

The outer loop selects one row at a time. A sum accumulator must be initialized to 0 inside the outer loop because each row needs a fresh sum. The inner loop then visits every column in the selected row and adds matrix[row][column] to the accumulator.

Placing sum = 0 outside the outer loop would produce a running total across all rows. For this example, the first result would still be 6, but the second would incorrectly become 21 instead of 15.

#include <iostream>
using namespace std;
constexpr int MAX_COLUMNS = 100;
void printRowSums(const int matrix[][MAX_COLUMNS], int rows, int columns) {
for (int row = 0; row < rows; row++) {
int sum = 0;
for (int column = 0; column < columns; column++) {
sum += matrix[row][column];
}
cout << "Sum of row " << row << " = " << sum << '\n';
}
}
int main() {
int matrix[][MAX_COLUMNS] = {
{1, 2, 3},
{4, 5, 6}
};
printRowSums(matrix, 2, 3);
return 0;
}

Every cell is visited exactly once, so the time complexity is O(rows × columns). Only one accumulator is required, giving O(1) auxiliary space when the sums are printed immediately.

Why a Local Built-In Array Cannot Be Returned

If the problem requires all row sums to be returned, it may seem natural to create a local array such as int sums[MAX_ROWS] inside a function and return it. A built-in array cannot be returned by value, and returning a pointer to that local array would be unsafe because the array's lifetime ends when the function returns.

Common valid alternatives are to let the caller provide an output array, allocate storage dynamically, or return a dynamic container such as vector<int>. When vectors are introduced, a row-sum function can store one result per row and return that vector safely. Until then, directly printing the sums or filling caller-owned storage demonstrates the traversal without creating a lifetime error.

Problem 2: Calculate the Sum of Every Column

For the same matrix, column sums are:

  • Column 0: 1 + 4 = 5.

  • Column 1: 2 + 5 = 7.

  • Column 2: 3 + 6 = 9.

The traversal order is reversed from the row-sum problem. The outer loop selects and fixes a column. The inner loop then visits every row in that column. As before, the accumulator must be reset inside the outer loop so that every column receives an independent total.

#include <iostream>
using namespace std;
constexpr int MAX_COLUMNS = 100;
void printColumnSums(const int matrix[][MAX_COLUMNS], int rows, int columns) {
for (int column = 0; column < columns; column++) {
int sum = 0;
for (int row = 0; row < rows; row++) {
sum += matrix[row][column];
}
cout << "Sum of column " << column << " = " << sum << '\n';
}
}
int main() {
int matrix[][MAX_COLUMNS] = {
{1, 2, 3},
{4, 5, 6}
};
printColumnSums(matrix, 2, 3);
return 0;
}

This solution also visits every cell once. Its time complexity is O(rows × columns), and its auxiliary space complexity is O(1) when each result is printed immediately.

Problem 3: Sum the Main and Secondary Diagonals

Given a square matrix, calculate the sum of its main diagonal and secondary diagonal. A square matrix has the same number of rows and columns, so an n × n matrix uses n for both dimensions.

Consider:

{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}

Main Diagonal Pattern

The main diagonal travels from the top-left corner to the bottom-right corner. Its coordinates are:

  • (0, 0), containing 1.

  • (1, 1), containing 5.

  • (2, 2), containing 9.

The row and column indexes are equal at every position. Therefore, a loop from i = 0 to i = n - 1 can accumulate matrix[i][i]. The sum is 1 + 5 + 9 = 15.

Secondary Diagonal Pattern

The secondary diagonal travels from the top-right corner to the bottom-left corner. Its coordinates are:

  • (0, 2), containing 3.

  • (1, 1), containing 5.

  • (2, 0), containing 7.

The row index increases from 0 to n - 1, while the column index decreases from n - 1 to 0. These movements happen in parallel rather than through nested loops. The sum is 3 + 5 + 7 = 15.

#include <iostream>
using namespace std;
constexpr int MAX_SIZE = 100;
int mainDiagonalSum(const int matrix[][MAX_SIZE], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += matrix[i][i];
}
return sum;
}
int secondaryDiagonalSum(const int matrix[][MAX_SIZE], int n) {
int sum = 0;
for (int i = 0, j = n - 1; i < n; i++, j--) {
sum += matrix[i][j];
}
return sum;
}
int main() {
int matrix[][MAX_SIZE] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
cout << "Main diagonal sum: " << mainDiagonalSum(matrix, 3) << '\n';
cout << "Secondary diagonal sum: " << secondaryDiagonalSum(matrix, 3) << '\n';
return 0;
}

Each diagonal contains exactly n cells, so each function runs in O(n) time and uses O(1) auxiliary space. A nested n × n traversal is unnecessary because the coordinate pattern identifies the required cells directly.

In an odd-sized matrix, the center cell belongs to both diagonals. The two functions intentionally include it in both individual sums. If a different problem asks for the sum of all unique cells belonging to either diagonal, the center must be subtracted once after adding both diagonal sums.

Problem 4: Transpose a Matrix

The transpose of a matrix is created by converting rows into columns. Every element at coordinate (i, j) in the original matrix moves to coordinate (j, i) in the transpose.

For the 2 × 3 matrix:

{{1, 2, 3}, {4, 5, 6}}

The transpose is the following 3 × 2 matrix:

{{1, 4}, {2, 5}, {3, 6}}

Coordinate Transformation

  • (0, 0) becomes (0, 0).

  • (0, 1) becomes (1, 0).

  • (0, 2) becomes (2, 0).

  • (1, 0) becomes (0, 1).

  • (1, 1) becomes (1, 1).

  • (1, 2) becomes (2, 1).

If the original matrix contains n rows and m columns, its transpose contains m rows and n columns. A separate matrix is therefore required for a general rectangular matrix because the dimensions change.

#include <iostream>
using namespace std;
constexpr int MAX_SIZE = 100;
int main() {
int matrix[MAX_SIZE][MAX_SIZE];
int transpose[MAX_SIZE][MAX_SIZE];
int rows, columns;
cin >> rows >> columns;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
cin >> matrix[i][j];
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
transpose[j][i] = matrix[i][j];
}
}
for (int i = 0; i < columns; i++) {
for (int j = 0; j < rows; j++) {
cout << transpose[i][j] << ' ';
}
cout << '\n';
}
return 0;
}

The construction loop traverses the original dimensions, while the output loop traverses the swapped dimensions. Every cell is copied once, so the time complexity is O(rows × columns). The transpose requires O(rows × columns) auxiliary space in this general rectangular solution.

Problem 5: Search for a Target in a Matrix

Given a matrix and a target value, return the row and column of the target's first occurrence during row-wise traversal. If the value is absent, return {-1, -1}.

Consider:

{{1, 4, 7}, {2, 5, 8}}

  • Searching for 5 returns {1, 1}.

  • Searching for 7 returns {0, 2}.

  • Searching for 15 returns {-1, -1}.

Row-Wise Linear Search

The search follows the same order as row-wise traversal: complete row 0, then row 1, and continue until all rows have been checked. When matrix[i][j] == target, returning {i, j} immediately terminates the function. This guarantees the first occurrence in row-wise order.

If every cell is examined and no comparison succeeds, execution reaches the final return {-1, -1};. A C++ pair<int, int> stores the two coordinates as one return value. Its components are accessed through first and second.

#include <iostream>
#include <utility>
using namespace std;
constexpr int MAX_COLUMNS = 100;
pair<int, int> searchMatrix(const int matrix[][MAX_COLUMNS], int rows, int columns, int target) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (matrix[i][j] == target) {
return {i, j};
}
}
}
return {-1, -1};
}
int main() {
int matrix[][MAX_COLUMNS] = {
{1, 4, 7},
{2, 5, 8}
};
pair<int, int> found = searchMatrix(matrix, 2, 3, 5);
pair<int, int> absent = searchMatrix(matrix, 2, 3, 15);
cout << found.first << ' ' << found.second << '\n';
cout << absent.first << ' ' << absent.second << '\n';
return 0;
}

In the worst case, the target is absent or appears in the final cell, so the algorithm visits the entire matrix. Its worst-case time complexity is O(rows × columns), and its auxiliary space complexity is O(1). An early match can terminate the function much sooner.

Problem-Solving Patterns

  • Row aggregation: Keep the row fixed, reset the accumulator, and traverse all columns.

  • Column aggregation: Keep the column fixed, reset the accumulator, and traverse all rows.

  • Main diagonal: Use equal row and column indexes, represented by matrix[i][i].

  • Secondary diagonal: Increase the row index while decreasing the column index.

  • Transpose: Move every value from (i, j) to (j, i) and interchange the dimensions.

  • Matrix search: Traverse in the required order and return as soon as the first match appears.

Summary

Multi-dimensional array problems are primarily exercises in choosing the correct coordinate pattern. Row and column sums differ only in which loop remains fixed. Diagonal sums replace a complete nested traversal with direct index relationships. Transposition swaps coordinates and dimensions, while matrix search combines row-wise traversal with early termination. Recognizing these patterns produces simpler code and avoids unnecessary work.

C++

Read Similar Blogs

C++

Recursion Problem Solving II: Array Traversal, Sorting Check and Reversal

Recursion Problem Solving - II Arrays are naturally suited to recursive processing because an array range can be divided into a current element and a smaller remaining range. A recursive function c...

9
C++

Recursion Problem Solving I: Power, Digit Sum and Number Reversal

Recursion Problem Solving - I Recursive problem solving begins by defining exactly what a function should return. The current problem is then expressed in terms of the same function applied to a sm...

9
C++

Recursion in C++ Explained: Base Cases, Call Stack and Recursive Functions

Recursion Foundation and Call Flow Recursion is a problem-solving technique in which a function calls itself with a smaller version of the original problem. Each call handles one part of the work a...

9
Comments0