Simple Matrix Practice

Lesson Overview

Welcome to this lesson covering Simple Matrix Operations . This is where we traverse the arena of two-dimensional data structures, commonly known as matrices. Matrices play an instrumental role in many domains of programming, such as machine learning, computer vision, and game development, making it important for you to understand how to effectively manipulate and traverse through them.

Matrix Review

In C++, matrices are often represented using an std::vector of std::vector s. This allows for dynamic resizing and easy manipulation. For example, a 3x3 matrix can be declared and initialized as follows: C++ std::vector<std::vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; You can access elements of the matrix using indices of the row and column. For example, matrix[1][2] would access the element in the second row and third column, which is 6.

Matrix Traversal Review

We can access the number of rows of a matrix using matrix.size() . The number of columns can be determined by the size of any inner std::vector, such as matrix[0].size() . Traversing a matrix usually involves nested loops. The outer loop normally iterates over the rows, and the inner loop iterates over the columns. Let's take a look at this code that simply prints each element of a matrix. C++ for (int i = 0; i < matrix.size(); i++) {for (int j = 0; j < matrix[i].size(); j++) {std::cout << matrix[i][j] << " ";} std::cout << std::endl;} Let's break this code down: Outer Loop This loop iterates over the rows of the matrix. matrix.size() returns the number of rows in the matrix. The variable i is the row index, starting at 0 and incrementing by 1 until it reaches the total number of rows. C++ for (int i = 0; i < matrix.size(); i++) {Inner Loop This loop iterates over the columns of the current row (i). matrix[i].size() returns the number of columns in the i -th row of the matrix. The variable j is the column index, starting at 0 and incrementing by 1 until it reaches the total number of columns in the current row. C++ for (int j = 0; j < matrix[i].size(); j++) {Accessing Elements matrix[i][j] accesses the element located at the i -th row and j -th column of the matrix. std::cout << matrix[i][j] << " " prints the accessed element followed by a space " " . C++ std::cout << matrix[i][j] << " "; Printing Newline We print a newline character, moving the console cursor to the next line. C++ std::cout << std::endl; In summary, the outer loop iterates through each row, while the inner loop iterates through each column of the current row, printing each element followed by a space. After printing all elements in a row, it prints a newline character to start the next row on a new line.

Join the 1M+ learners on CodeSignal

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

Matrix Search

With this foundation in matrix traversals, let's tackle a common coding interview question. Given a sorted matrix where each row and column is sorted in ascending order, we have to search for a particular target value. One approach is traversing the entire matrix until we find the target value. However, this requires us to potentially search the entire matrix. Let's optimize our approach.

Since the matrix is sorted both row-wise and column-wise, we can leverage this property for an efficient search. Start from the top-right corner of the matrix:

If the current element equals the target, you've found the value.
If the current element is greater than the target, move left (one column back).
If the current element is less than the target, move down (one row forward).

Continue these steps until you either find the target or exhaust the search space. This method ensures that each step narrows down the potential search area efficiently.

Here's how you can implement this in C++:

C++

#include <iostream>
#include <vector>

bool searchMatrix(const std::vector<std::vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) {
        return false;
    }

    int rows = matrix.size();
    int cols = matrix[0].size();

    int row = 0;
    int col = cols - 1;

    while (row < rows && col >= 0) {
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] > target) {
            col--; // move left
        } else {
            row++; // move down
        }
    }

    return false; // target not found
}

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 4, 7, 11, 15},
        {2, 5, 8, 12, 19},
        {3, 6, 9, 16, 22},
        {10, 13, 14, 17, 24},
        {18, 21, 23, 26, 30}
    };
    int target = 5;

    if (searchMatrix(matrix, target)) {
        std::cout << "Target found in the matrix.\n";
    } else {
        std::cout << "Target not found in the matrix.\n";
    }

    return 0;
}

Code Breakdown

Let's break down the code step by step:

Function Definition

This line defines the function searchMatrix that returns a bool. The first parameter is a constant reference to an std::vector that contains std::vector<int>. The second is the target value we are searching for.

C++

bool searchMatrix(const std::vector<std::vector<int>>& matrix, int target)

Check for Empty Matrix

This check ensures that if the matrix is empty or the first row is empty, the function immediately returns false, as there is no element to search.

C++

if (matrix.empty() || matrix[0].empty()) {
    return false;
}

Determine Dimensions of the Matrix

This step fetches the number of rows and columns in the matrix to use in boundary conditions.

C++

int rows = matrix.size();
int cols = matrix[0].size();

Set Initial Position

Initialize the starting point to the top-right corner of the matrix. row is initialized to 0 and col to the last column index cols - 1.

C++

int row = 0;
int col = cols - 1;

Start Matrix Traversal

The while loop runs as long as row is less than the number of rows and col is non-negative.

C++

while (row < rows && col >= 0) {

Comparison and Movement

If the current element matrix[row][col] is equal to the target, the function returns true.
If the current element is greater than the target, move left by decrementing col because all elements to the left are smaller.
If the current element is less than the target, move down by incrementing row because all elements below are larger.

C++

while (row < rows && col >= 0) {
    if (matrix[row][col] == target) {
        return true;
    } else if (matrix[row][col] > target) {
        col--; // move left
    } else {
        row++; // move down
    }
}

Return Statement

If the loop completes and the target is not found, the function returns false.

C++

return false; // target not found

In summary, the searchMatrix function searches for a target value within a two-dimensional matrix where each row and column is sorted in ascending order. By starting from the top-right corner and leveraging the sorted properties, it efficiently narrows the search space by moving left or down based on comparisons.