Premium Video

This video is available to premium subscribers only

Unlock Full Access

Think about the last time you opened Google Maps, edited a photo, or played a game like chess. All these applications work with data organized in rows and columns.

A digital image, for example, is made up of millions of pixels arranged in a grid. A chessboard has eight rows and eight columns. And a spreadsheet can contain thousands of rows and columns of data.

In programming, one of the simplest ways to represent this kind of information is using a two-dimensional array, commonly called a matrix.

In this chapter, we'll understand what a matrix is and how it works, how to create a matrix, access and update its elements, and traverse it in different ways. We'll also explore common matrix operations, their time complexities, and some important patterns you'll encounter in coding interviews.

A matrix is a collection of elements organized into rows and columns.

You can think of it as an extension of a regular one-dimensional array. A one-dimensional array stores elements in a single sequence. But what if we want to organize data in two dimensions?

Let's take an example. Suppose an online store wants to track the number of orders received from three different regions over four days. We could represent this information using a matrix.

Each row represents a region, and each column represents a day:

The first row contains the orders from the North region. The second row contains orders from the South region. And the third row contains orders from the West region.

This gives us a matrix with three rows and four columns. We call it a 3 x 4 matrix. The first number represents the number of rows, and the second represents the number of columns.

We'll use this orders matrix throughout the chapter.

In most programming languages, we can represent a matrix using a two-dimensional array.

Conceptually, you can think of it as a collection of arrays, where each inner array represents a row. For our online store example, we'd have three rows, each containing four numbers. Together, they form a two-dimensional structure:

Notice how we get the dimensions. The number of rows is the length of the outer array. The number of columns is the length of any row, so we read it from the first one. Most matrix code starts with these two lines.

A matrix doesn't necessarily have the same number of rows and columns. A matrix with equal numbers of rows and columns is called a square matrix. Otherwise, it's a rectangular matrix. Our orders matrix is rectangular: it has 3 rows and 4 columns.

Since each row is its own array, some languages also allow rows of different lengths. These are called jagged arrays. In most matrix problems, though, we work with rectangular grids where every row has the same number of columns.

Every element is identified using two indices: a row index and a column index.

In most programming languages, array indexing starts from zero. So the first element is at row 0, column 0. The next element in the same row is at row 0, column 1. And the first element of the second row is at row 1, column 0.

Here are the indices of every cell in our orders matrix:

Now, suppose we want to find the number of orders received from the South region on the third day. South is the second row, so its row index is 1. The third day is the third column, so its column index is 2.

We access the element at row 1, column 2. And that gives us the value 125:

The important thing to remember is that the row index comes first, followed by the column index.

Just like a regular array, we can also update individual elements in a matrix.

Suppose the order count for the North region on the second day increases from 150 to 160. We simply access the element at row 0, column 1, and replace its value with 160:

That's it. We don't need to search through the matrix or visit any other elements.

As long as we know the row and column indices, we can access or update an element directly. Both operations take constant time, or O(1). This is one of the biggest advantages of using arrays to represent a matrix.

From here on, the orders matrix holds 160 at orders[0][1].

We can also create a new matrix by specifying the number of rows and columns.

For example, suppose we want to create a grid with five rows and six columns. We allocate space for those thirty elements.

Depending on the programming language and how the matrix is created, the elements may be initialized with default values, or we may need to initialize them ourselves:

Java, C#, and Go give every cell a default value of 0. In C++, Rust, Python, and JavaScript, we set the starting value ourselves.

Be careful with shortcuts like [[0] * 6] * 5 in Python or new Array(5).fill(new Array(6).fill(0)) in JavaScript. They create one row and put five references to it in the outer array. Changing grid[0][0] would then change the first cell of every row. Building each row separately, as in the code above, avoids this.

Once the matrix is created, we can fill it with values as needed.

The total space required to store a matrix depends on the number of elements. Our grid holds 5 x 6 = 30 values. For a matrix with R rows and C columns, the space complexity is O(R x C).

Now let's move to one of the most important operations: traversing a matrix. Traversing means visiting its elements, usually to read, update, or process their values.

For a regular one-dimensional array, we typically use a single loop. But a matrix has two dimensions, so we generally use nested loops. The outer loop iterates through the rows. And the inner loop iterates through the columns within each row.

Let's understand this with an example. Suppose we have a 3 x 4 matrix containing the numbers 1 through 12:

We start at the first row and visit its elements from left to right. Once we reach the end of that row, we move to the next row and repeat the process. We continue until we've visited every element:

For our matrix, this visits the elements in this order:

This is called row-wise traversal. And it's probably the most common way you'll process a matrix.

But row-wise traversal isn't our only option. Sometimes, we want to process a matrix one column at a time.

For example, suppose we want to calculate the total number of orders received on each day across all regions. Since each column represents a day, it makes sense to process the matrix column by column.

We can do this by reversing the order of our loops. The outer loop now iterates through the columns. And for each column, the inner loop visits every row:

So we first visit every element in column 0, moving from top to bottom. Then we move to column 1. And we continue until we've processed every column.

For the orders matrix (with 160 at orders[0][1]), this gives one total per day:

This is called column-wise traversal. On the 1-to-12 matrix from the previous section, it visits the elements in this order:

The matrix itself hasn't changed. We're simply visiting its elements in a different order.

In most languages, the elements of a row sit next to each other in memory. Row-wise traversal reads them in that order, so it's usually a little faster on very large matrices. For the problems in this chapter, though, pick the order that matches the question.

Now, let's understand the time complexity of traversing a matrix.

Suppose our matrix has R rows and C columns. When we traverse it row by row, the outer loop runs R times. And for every row, the inner loop runs C times. So the total number of iterations is R multiplied by C. That gives us a time complexity of O(R x C).

The same applies to column-wise traversal because we're still visiting every element exactly once.

If the matrix is square, with N rows and N columns, the complexity becomes O(N²).

And since we only need a few loop variables, the traversal itself requires O(1) extra space.

Now, let's put these concepts into practice with a simple problem.

Remember our online store example? We have a matrix containing the number of orders received from different regions over several days. Our task is to find the region that received the highest total number of orders.

How would we solve this?

Since each row represents a region, we can calculate the sum of every row and keep track of the row with the highest sum.

Here is the trace on the orders matrix:

Since we visit every element exactly once, the time complexity is O(R x C). And because we only maintain a few variables, the extra space complexity is O(1).

This is a common matrix pattern: processing each row independently and combining the results. The daily totals from the previous section are the same pattern applied to columns.

Now, let's explore something that makes matrices especially interesting.

Unlike one-dimensional arrays, where we usually think about left and right neighbors, a matrix lets us move in multiple directions. From a given cell, we can potentially move up, down, left, or right. These are called the four cardinal directions.

Let's say we're currently at row 2, column 3. Moving up means decreasing the row index by one. Moving down means increasing it by one. Similarly, moving left decreases the column index, while moving right increases it:

We can represent these movements using direction offsets. Each offset tells us how much to change the current row and column:

For example, moving up corresponds to -1 for the row and 0 for the column. Moving right corresponds to 0 for the row and +1 for the column.

This gives us a simple, reusable way to explore neighboring cells. Instead of writing four separate blocks of code, we store the offsets in an array and loop over them. We'll see the code in the next section, together with one check every neighbor needs.

But there's one important thing we need to handle. Not every cell has four valid neighbors.

Consider a cell in the top-left corner. It doesn't have a neighbor above it or to its left. Applying the offsets to (0, 0) gives (-1, 0) and (0, -1), which are positions outside the matrix.

So before accessing a neighboring cell, we must check whether its coordinates fall within the matrix boundaries. For a matrix with R rows and C columns:

If either index falls outside this range, we simply ignore that position. Here are the offsets and the boundary check together:

These boundary checks are extremely important when solving matrix problems. Without them, we might try to access an invalid position and run into an error. In Java, for example, grid[-1][0] throws an ArrayIndexOutOfBoundsException. In Python, a negative index doesn't fail at all. grid[-1] quietly returns the last row, which can be an even harder bug to find.

You might be wondering where this kind of traversal is useful.

Imagine you're building a photo editing application with a fill tool. When a user clicks on a pixel, the application needs to identify neighboring pixels with the same color. It then continues exploring their neighbors until it finds the entire connected region. This is commonly known as flood fill.

Here is a small image stored as a matrix, where 1 is one color and 0 is another. If the user clicks the pixel at (1, 2), the fill spreads to every 1 it can reach by moving up, down, left, or right:

The group of 1s on the right isn't filled. It only touches the filled region at a corner, and corners aren't one of the four directions.

Similar ideas appear in problems involving connected islands, shortest paths through grids, and maze navigation.

Sometimes, diagonal movements are also allowed. In that case, a cell can have up to eight neighbors instead of four:

With eight directions, the fill above would also reach the group on the right through that corner.

These problems often use graph traversal algorithms like Depth-First Search and Breadth-First Search. We'll explore those algorithms in more detail in separate lessons.

Another important concept you'll encounter is matrix diagonals. Let's consider a square matrix with four rows and four columns:

The main diagonal runs from the top-left corner to the bottom-right corner: 1, 6, 11, 16. And the secondary diagonal runs from the top-right corner to the bottom-left corner: 4, 7, 10, 13.

There's an interesting pattern here. For every element on the main diagonal, the row index and column index are equal. So the main diagonal contains elements at positions (0, 0), (1, 1), (2, 2), and (3, 3).

For the secondary diagonal, the sum of the row and column indices is always N - 1, where N is the size of the matrix. Here N = 4, so every position adds up to 3: (0, 3), (1, 2), (2, 1), and (3, 0).

These observations are useful in problems involving diagonal sums and matrix transformations. Because we know exactly where each diagonal element is, we can read a diagonal with a single loop:

For our 4 x 4 matrix, the main diagonal adds up to 1 + 6 + 11 + 16 = 34, and the secondary diagonal to 4 + 7 + 10 + 13 = 34.

This runs in O(N) time, because we touch only N cells per diagonal instead of all N² cells. One thing to watch: when N is odd, the two diagonals share the center cell. If a problem asks for the sum of both diagonals together, count that cell only once.

Let's look at another common matrix operation called transposition. The transpose of a matrix is obtained by converting its rows into columns.

For example, suppose we have a matrix with two rows and three columns. When we transpose it, we get a new matrix with three rows and two columns:

The first row of the original matrix becomes the first column of the transposed matrix. And the second row becomes the second column.

In general, the element at row r and column c moves to row c and column r. For example, the 2 at original[0][1] ends up at transposed[1][0]. So we're essentially swapping the row and column coordinates.

To build the transpose, we can visit every element and place it at its corresponding position in the new matrix:

Notice that the new matrix is created with the dimensions swapped: cols rows and rows columns. Visiting every element takes O(R x C) time, and the new matrix takes O(R x C) space.

If the matrix is square, we can also transpose it in place, without a second matrix. We swap grid[r][c] with grid[c][r] for every cell above the main diagonal (where c > r). The diagonal itself stays where it is.

Before we wrap up, let's quickly discuss a few common mistakes.

1. Mixing up rows and columns. Always remember that the first index represents the row, and the second represents the column. orders[2][1] is the West region on day 2, not the South region on day 3.

2. Assuming every matrix is square. A matrix can have different numbers of rows and columns, so make sure your loops use the correct dimensions. A loop like for (int c = 0; c < rows; c++) looks fine on a square matrix. On our 3 x 4 orders matrix, it never visits the last column.

3. Forgetting boundary checks. This is especially important when exploring neighboring cells. Check that a neighbor's row and column are both in range before reading it.

4. Not considering empty matrices. If a matrix contains no rows, trying to access its first row will cause an error in many programming languages. Reading grid[0].length on an empty array throws an exception in Java. Guard against it at the start:

These edge cases are easy to overlook, especially under interview pressure.

So, when should you think about using a matrix in a coding interview?

The biggest signal is when the problem involves data arranged in a grid. It might be:

Matrices are also commonly used in dynamic programming, where we store intermediate results in a two-dimensional table. For example, to count the paths from the top-left to the bottom-right of a 3 x 4 grid when you can only move right or down, each cell stores the number of ways to reach it. That value is the cell above plus the cell to the left:

There are 10 such paths. We'll come back to tables like this in the dynamic programming lessons.

Whenever a problem naturally involves rows, columns, or movement between neighboring positions, a matrix is often a good starting point.

To make these concepts stick, try implementing row-wise and column-wise traversal, finding the largest element in a matrix, and calculating the sum of each row and column. These simple exercises will help you build a strong foundation before moving on to more advanced matrix problems.