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.

In C++, matrices are often represented using an std::vector of std::vectors. This allows for dynamic resizing and easy manipulation. For example, a 3x3 matrix can be declared and initialized as follows:

C++
Copy to clipboard
1std::vector<std::vector<int>> matrix = {
2    {1, 2, 3},
3    {4, 5, 6},
4    {7, 8, 9}
5};

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.

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++
Copy to clipboard
1for (int i = 0; i < matrix.size(); i++) {
2    for (int j = 0; j < matrix[i].size(); j++) {
3        std::cout << matrix[i][j] << " ";
4    }
5    std::cout << std::endl;
6}

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++
Copy to clipboard
1for (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++
Copy to clipboard
1for (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++
Copy to clipboard
1std::cout << matrix[i][j] << " ";

Printing Newline

• We print a newline character, moving the console cursor to the next line.

C++
Copy to clipboard
1std::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.

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++
Copy to clipboard
1#include <iostream>
2#include <vector>
3
4bool searchMatrix(const std::vector<std::vector<int>>& matrix, int target) {
5    if (matrix.empty() || matrix[0].empty()) {
6        return false;
7    }
8
9    int rows = matrix.size();
10    int cols = matrix[0].size();
11
12    int row = 0;
13    int col = cols - 1;
14
15    while (row < rows && col >= 0) {
16        if (matrix[row][col] == target) {
17            return true;
18        } else if (matrix[row][col] > target) {
19            col--; // move left
20        } else {
21            row++; // move down
22        }
23    }
24
25    return false; // target not found
26}
27
28int main() {
29    std::vector<std::vector<int>> matrix = {
30        {1, 4, 7, 11, 15},
31        {2, 5, 8, 12, 19},
32        {3, 6, 9, 16, 22},
33        {10, 13, 14, 17, 24},
34        {18, 21, 23, 26, 30}
35    };
36    int target = 5;
37
38    if (searchMatrix(matrix, target)) {
39        std::cout << "Target found in the matrix.\n";
40    } else {
41        std::cout << "Target not found in the matrix.\n";
42    }
43
44    return 0;
45}

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++
Copy to clipboard
1bool 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++
Copy to clipboard
1if (matrix.empty() || matrix[0].empty()) {
2    return false;
3}

Determine Dimensions of the Matrix

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

C++
Copy to clipboard
1int rows = matrix.size();
2int 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++
Copy to clipboard
1int row = 0;
2int 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++
Copy to clipboard
1while (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++
Copy to clipboard
1while (row < rows && col >= 0) {
2    if (matrix[row][col] == target) {
3        return true;
4    } else if (matrix[row][col] > target) {
5        col--; // move left
6    } else {
7        row++; // move down
8    }
9}

Return Statement

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

C++
Copy to clipboard
1return 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.

Once you've absorbed the fundamental concepts of matrices and their operations, we're all set to dive into the practice exercises. We cannot stress enough the importance of practice when it comes to programming. Remember, our goal here is not to brute-force our way through problems, but to build a solid understanding of matrix concepts, improve problem-solving skills, and write code that is not only correct but also efficient and elegant.