Traversing a 2D Matrix in C++ | CodeSignal Learn

Traversing a 2D Matrix in C++ | CodeSignal Learn

Introduction

Hello, fellow coder! Are you excited to dive into a new, intriguing coding challenge? In this lesson, we're going to explore special traversals of matrices. Using the C++ programming language, we'll find our way through a matrix by climbing up and down the columns, zigzagging as we go. Sound exciting? Buckle up, then, and get ready!

Task Statement

3 \times 4

Solution Building: Step 1

The first step towards a solution is understanding the dimensions of the matrix with which we're working. We can do this using C++'s member functions such as size(). Let's set up our function and identify the matrix size: C++#include <vector> #include <iostream> std::vector<int> column_traverse(const std::vector<std::vector<int>>& matrix) { int rows = matrix.size(); int cols = matrix[0].size(); }

Solution Building: Step 2

Now that we're aware of the matrix dimensions, we should establish the starting point (bottom-right) and the direction of travel (upward initially). Additionally, we'll need a vector to keep track of the cells we've visited in order: C++#include <vector> #include <iostream> std::vector<int> column_traverse(const std::vector<std::vector<int>>& matrix) { int rows = matrix.size(); int cols = matrix[0].size(); std::string direction = "up"; int row = rows - 1; int col = cols - 1; std::vector<int> output; }

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Solution Building: Step 3

It's time to go exploring! We'll now implement a while loop to traverse the matrix. This loop will continue until we have covered all the cells in the matrix. As we "visit" each cell, we'll add the value in the cell to our vector. #include <vector> #include <iostream> std::vector<int> column_traverse(const std::vector<std::vector<int>>& matrix) { int rows = matrix.size(); int cols = matrix[0].size(); std::string direction = "up"; int row = rows - 1; int col = cols - 1; std::vector<int> output; while (output.size() < rows * cols) { output.push_back(matrix[row][col]); if (direction == "up") { if (row - 1 < 0) { direction = "down"; col -= 1; } else { row -= 1; } } else { if (row + 1 == rows) { direction = "up"; col -= 1; } else { row += 1; } } } return output; } That's it, we've completed the function! This C++ function will return the output vector, which gives us the order of traversal through the matrix.

C++

#include <vector>
#include <iostream>

std::vector<int> column_traverse(const std::vector<std::vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    std::string direction = "up";
    int row = rows - 1;
    int col = cols - 1;
    std::vector<int> output;

    while (output.size() < rows * cols) {
        output.push_back(matrix[row][col]);

        if (direction == "up") {
            if (row - 1 < 0) {
                direction = "down";
                col -= 1;
            } else {
                row -= 1;
            }
        } else {
            if (row + 1 == rows) {
                direction = "up";
                col -= 1;
            } else {
                row += 1;
            }
        }
    }

    return output;
}

Let's explore one more way of traversal. We can leverage the utility of C++'s for-loop to traverse a 2D matrix in reverse order. This flexibility can also create a sequence that decrements.

To achieve this, we use a for-loop with decrementing indices.

Consider our familiar $3 \times 4$ matrix:

C++

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

Using decrementing loops, the reverse traverse pattern would produce this list: {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}.

Here's how we can implement this reverse traversal:

C++

#include <vector>
#include <iostream>

std::vector<int> reverse_traverse(const std::vector<std::vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    std::vector<int> output;

    for (int row = rows - 1; row >= 0; --row) {
        for (int col = cols - 1; col >= 0; --col) {
            output.push_back(matrix[row][col]);
        }
    }

    return output;
}

In this function, we start the loop for row from rows - 1 and run it to 0, decrementing it at each step. Similarly, our nested loop for col starts from cols - 1 and goes to 0. This allows us to start from the bottom-right corner and traverse leftward, then upward, covering the entire matrix in reverse order.

As you gain proficiency in matrix traversal in C++, you'll discover the many creative ways to utilize C++'s flexible syntax. The more you experiment with different traversal methods, the better you become! Happy practicing!