Diagonal Matrix Traversal - C++ Solution

1. Introduction

In this blog post, we will explore an interesting matrix traversal problem - extracting all diagonal elements of a matrix with a positive slope. Diagonal traversal of matrices is a fundamental operation in various applications, including digital image processing and data analysis.

Problem

The task is to traverse an M × N integer matrix and return all its diagonal elements, each diagonal having a positive slope.

2. Solution Steps

1. Understand that diagonals with a positive slope move from the bottom left to the top right of the matrix.

2. Iterate over each element of the matrix and extract the diagonals one by one.

3. Store each diagonal in a separate vector.

4. Handle the boundaries of the matrix to avoid index out-of-range errors.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> diagonalTraversal(const vector<vector<int>>& matrix) {
    int M = matrix.size(), N = matrix[0].size();
    vector<vector<int>> result(M + N - 1);

    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            result[i + j].push_back(matrix[i][j]);
        }
    }

    return result;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3, 4, 5},
        {2, 3, 4, 5, 6},
        {3, 4, 5, 6, 7},
        {4, 5, 6, 7, 8},
        {5, 6, 7, 8, 9}
    };

    vector<vector<int>> diagonals = diagonalTraversal(matrix);

    // Output the diagonal elements
    for (const auto& diag : diagonals) {
        for (int val : diag) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

Output:

1
2 2
3 3 3
4 4 4 4
5 5 5 5 5
6 6 6 6
7 7 7
8 8
9

Explanation:

The function diagonalTraversal iterates over each cell of the given matrix and adds elements to their corresponding diagonals in the result vector. Each diagonal is represented by the sum of the row and column indices of its elements. For instance, the diagonal containing the element at (0,0) is represented by 0+0, and the one containing elements at (1,0) and (0,1) is represented by 1. The output arrays represent the diagonals of the matrix, starting from the bottom left and moving to the top right.