Frequently asked matrix coding questions

Matrix coding problems are known to be tough in interviews, with many rated as medium or hard on LeetCode. Leading tech companies, including MAANGPreviously known as FAANG.—Meta (Facebook), Apple, Amazon, Netflix, and Google—often feature matrix questions to test candidates’ technical strength. Successfully solving these problems highlights your ability to manage complex data structures and meet the expectations of interviewers.

A matrix, as a 2D data structure, can seem daunting at first, but with practice and a grasp of key techniques, you'll be good to go. In this blog, we'll look at some basic matrix operations and go over some frequently asked coding problems that can be solved with these techniques.

We'll essentially cover the following topics in this blog:

Matrix structure: 2D arrays as matrices.
Matrix transformations: Transposing a matrix, flipping it horizontally or vertically, and rotating it by specific degrees.
Matrix traversals: Row-wise, column-wise, diagonal, zig-zag and spiral traversal.
Frequently asked matrix coding problems: Rotate Image, Spiral Matrix, Spiral Matrix II, Set Matrix Zeroes, Valid Word Square, Diagonal Traverse, and Toeplitz Matrix.

Let’s get started!

Why do interviewers ask matrix coding questions?#

Here are a few reasons why interviewers like to ask candidates matrix questions:

They test a candidate’s ability to handle multi-dimensional data structures.
Their resemblance with real-world applications like image processing, game development, and more. Example of a few problems that mirror real-world scenarios:
- Rotate Image resembles image manipulation.
- Valid Word Square resembles text processing.
- Diagonal Traversal resembles data organization.
In real-world applications involving large matrices, arriving at an optimal solution is critical. Therefore, these questions test whether a candidate can write solutions that are not just correct but also efficient in terms of time and space complexity.

Understanding the matrix structure in computer science#

In computer science, matrices are represented by 2D arrays with dimensions $m \times n$ , where $m$ is the number of rows, and $n$ is the number of columns. Each element in the matrix can be accessed using the array indexes. The first index represents the row, and the second index represents the column. For example, $matrix[i][j]$ is an element from the $i^{th}$ row and the $j^{th}$ column of the matrix.

Let's explore the most common matrix operations in detail.

Must-know matrix operations for coding interviews#

A matrix operation is simply a change applied to a matrix to modify its structure. These changes can involve reordering the rows and columns like swapping them, rotating, or flipping the matrix.

Let's explore a few most common matrix transformations:

1. Transpose a matrix: #

This swaps rows of a matrix with its columns.

While square matrices can be transposed directly in place, non-square matrices need extra space for the new arrangement. This is primarily due to the dimensions of matrices. In square matrices, we can simply swap elements across the main diagonal directly. For example, an element at position (i, j) can be swapped with the element at (j, i).

2. Flip a matrix: #

You can flip a matrix in two ways:

Horizontal flip: This reverses the order of elements in each row of the matrix. Each row is mirrored horizontally across the y-axis.
Vertical flip: This reverses the order of elements in each column of the matrix. Each column is mirrored vertically across the x-axis.

Python 3.10.4

def transpose(matrix):
    # Get number of rows and columns
    num_rows = len(matrix)
    num_cols = len(matrix[0]) if num_rows > 0 else 0
    
    # Initialize transposed matrix
    transposed_matrix = [[0] * num_rows for _ in range(num_cols)]
    
    # Fill the transposed matrix
    for i in range(num_rows):
        for j in range(num_cols):
            transposed_matrix[j][i] = matrix[i][j]
    
    return transposed_matrix  # Return transposed matrix
#---------------------------------------------------------------------------
def flip_horizontal(matrix):
    # Flip the matrix horizontally (reverse each row)
    return [row[::-1] for row in matrix]
#---------------------------------------------------------------------------
def flip_vertical(matrix):
    # Flip the matrix vertically (reverse the order of rows)
    return matrix[::-1]
#---------------------------------------------------------------------------
# Example usage
original_matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
horizontally_flipped = flip_horizontal(original_matrix)
vertically_flipped = flip_vertical(original_matrix)
transposed_matrix = transpose(original_matrix)
# Print original and transposed matrices
print("Original Matrix:")
for row in original_matrix:
    print(row)
print("\nTransposed Matrix:")
for row in transposed_matrix:
    print(row)
print("\nHorizontally Flipped Matrix:")
for row in horizontally_flipped:
    print(row)
print("\nVertically Flipped Matrix:")
for row in vertically_flipped:
    print(row)

Transpose of a matrix

To rotate a matrix in a programming language, like Python or Java, you typically perform the following steps:

For 90-degree clockwise rotation:
- Transpose the matrix.
- Flip the matrix horizontally.
For 90-degree anticlockwise rotation:
- Transpose the matrix.
- Flip the matrix vertically.
For 180-degree rotation (either clockwise or anticlockwise):
- Flip the matrix horizontally and vertically.
For 270-degree clockwise rotation:
- Equivalent to a 90-degree counterclockwise rotation.

Now you know how to code for rotating matrices using the code for transposing and flipping a matrix. Before we proceed, can you write code to rotate a matrix 90 degrees anticlockwise in the code widget below? If you succeed, it will be shown in the output tab.

Click "Test" to execute the code. It will be tested against two matrices. Don’t click "Show Solution" until you’ve tried it at least once.

Now that we're done with looking at basic matrix operations, let's explore some common matrix traversals.

Mastering matrix traversals for coding interviews#

Matrix traversal refers to the systematic process of visiting and accessing the elements of a matrix in a specific order. Different traversal methods define unique sequences, and the choice of traversal can greatly influence the approach to solving a problem.

Let's explore a few most common matrix traversals:

1. Row-wise traversal#

Traverse the matrix row by row, moving from the first column to the last in each row.

3. Diagonal traversal#

Traverse the matrix along its diagonal elements. There are different variations of diagonal traversal:

Main diagonal: It includes traversing from the top-left corner to the bottom-right corner of the matrix. The direction of traversing the diagonals may change as per the context. For example, it can be always diagonal up-right (↗) or diagonal down-left (↙).
Anti-diagonal: It includes traversing from the top-right corner to the bottom-left corner of the matrix. For example, it can be always diagonal up-right (↗) or diagonal down-left (↙).
Zig-zag diagonal: It includes traversing all the diagonals in alternating directions.

Python 3.10.4

# Template for row-wise traversal in Python (store in a list and print)
def row_wise_traversal(matrix):
    result = []
    for i in range(len(matrix)):  # Traverse each row
        result.extend(matrix[i])  # Add each element to the result list
    print(result)
#---------------------------------------------------------------------------
# Template for column-wise traversal in Python (store in a list and print)
def column_wise_traversal(matrix):
    result = []
    for j in range(len(matrix[0])):  # Traverse each column
        for i in range(len(matrix)):
            result.append(matrix[i][j])  # Add each element to the result list
    print(result)
    
#-------------------------------------------------------------------------------
# Template for zigzag diagonal traversal in Python (store in a list and print)
def zigzag_diagonal_traversal(matrix):
    rows = len(matrix)  # Get the number of rows in the matrix
    cols = len(matrix[0])  # Get the number of columns in the matrix
    result = []  # Initialize an empty list to store the traversal result
    # Iterate through each diagonal, from 0 to rows + cols - 2
    for d in range(rows + cols - 1):
        if d % 2 == 0:  # For even index diagonals, traverse upwards
            # Determine the starting row (r) for the upward traversal
            r = min(d, rows - 1)
            c = d - r  # Calculate the starting column (c)
            # Traverse upwards along the diagonal
            while r >= 0 and c < cols:
                result.append(matrix[r][c])  # Add the current element to the result
                r -= 1  # Move up in the row
                c += 1  # Move right in the column
        else:  # For odd index diagonals, traverse downwards
            c = min(d, cols - 1)  # Determine the starting column (c) for the downward traversal
            r = d - c  # Calculate the starting row (r)
            # Traverse downwards along the diagonal
            while c >= 0 and r < rows:
                result.append(matrix[r][c])  # Add the current element to the result
                r += 1  # Move down in the row
                c -= 1  # Move left in the column
    print(result)  # Print the final zigzag diagonal traversal result
#-------------------------------------------------------------------------------
# Template for spiral traversal in Python (store in a list and print)
def spiral_traversal(matrix):
    # Check if the matrix is empty
    if not matrix or not matrix[0]:
        return []
    result = []  # Initialize an empty list to store the traversal result
    top, bottom = 0, len(matrix) - 1  # Set the top and bottom boundaries
    left, right = 0, len(matrix[0]) - 1  # Set the left and right boundaries
    # Continue the loop until all boundaries converge
    while top <= bottom and left <= right:
        # Traverse from left to right along the top row
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1  # Move the top boundary down
        # Traverse from top to bottom along the right column
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1  # Move the right boundary left
        # Check if there are still rows to traverse
        if top <= bottom:
            # Traverse from right to left along the bottom row
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1  # Move the bottom boundary up
        # Check if there are still columns to traverse
        if left <= right:
            # Traverse from bottom to top along the left column
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1  # Move the left boundary right
    print(result)  # Print the final spiral traversal result
   
#---------------------------------------------------------------------------
# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print("Matrix:")
for row in matrix:
    print(row)
    
print("\nRow-wise traversal: ") 
row_wise_traversal(matrix)
print("\nColumn-wise traversal: ") 
column_wise_traversal(matrix)
print("\nZig-zag traversal: ") 
zigzag_diagonal_traversal(matrix)
print("\nSpiral traversal: ") 
spiral_traversal(matrix)

Matrix traversals

Let's explore one way to solve this problem:

Initialize the matrix: Start by making an $n$ × $n$ matrix, initially filled with zeros or any placeholder value. This matrix will later be filled with numbers.
Set boundaries: Define four boundaries to help you know where to fill in numbers:
1. Top: This boundary starts at the first row.
2. Bottom: This boundary starts at the last row.
3. Left: This boundary starts at the first column.
4. Right: This boundary starts at the last column.
Fill in numbers: Start filling in the numbers from 1 to $n^2$ by following these directions:
1. Fill the top tow: Go from the left boundary to the right boundary and fill the top row with numbers.
2. Move down the right column (last column): Go from the top boundary down to the bottom boundary and fill the right column with numbers.
3. Fill the bottom row: If the top boundary is still above the bottom boundary, fill the bottom row from right to left.
4. Move up the left Column (first column): If the left boundary is still to the left of the right boundary, fill the left column from bottom to top.
After filling each layer of the matrix, move the boundaries inward:
1. Move the Top boundary down by one row.
2. Move the Bottom boundary up by one row.
3. Move the Left boundary right by one column.
4. Move the Right boundary left by one column.
Repeat: Keep filling and adjusting the boundaries until you've filled all the numbers from 1 to $n^2$ .

4. Set Matrix Zeros#

In this problem, given an $m \times n$ integer matrix, if any element is $0$ , you have to set all elements in its row and column to $0$ . This involves identifying the positions of zeros and ensuring they propagate throughout the respective rows and columns.

One of the optimal solutions involves using a two-pass algorithm:

First pass—Marking: In the first pass, you traverse the entire matrix and identify which rows and columns contain at least one zero. You can use two sets to keep track of the rows and columns that need to be zeroed. As you iterate through the matrix, whenever you encounter a zero, you add its row index to one set and its column index to another.
Second pass—Setting zeros: In the second pass, you iterate over the matrix again. For each cell, you check if its row or column index is present in the sets you created in the first pass. If it is, you set that cell to zero. This ensures that you only modify the necessary elements without affecting the zeros you identified in the first pass.

5. Valid Word Square#

In this problem, you are given a list of strings, words, where each string represents a row in a square grid. Your task is to check whether the given list of strings form a valid word square.

A word square is valid if the words read vertically in each column match the words read horizontally in the corresponding row. So, the grid formed by the given strings will be valid if for all i and j, the character at words[i][j] (if it exists) equals the character at words[j][i] (if it exists).

One way to solve this is to place each word in a matrix, so for the first word, keep it in the first row and first column. Once all words are placed in the matrix, start traversing it and compare each character in a row with the corresponding character in the column. If the characters match at each position, move to the next row and column. If at any point the characters don't match, stop and return false. If all rows and columns match, return true.

7. Toeplitz Matrix#

This problem requires to check if a given matrix is a Toeplitz matrix, where each diagonal contains the same value repeated throughout. The challenge is to verify this condition for all diagonals efficiently.

Let's look at the steps to check if a matrix is a Toeplitz matrix:

Iterate through the matrix: Loop through each element of the first row and the first column because these correspond to all the diagonals.
Check diagonals: For each element you check, look at the element present diagonally below. If these two elements are not the same, the matrix is not a Toeplitz matrix.
Finish checking: If you go through all the diagonals and find that each has the same value repeated throughout, then the matrix is a Toeplitz matrix.

Problem Name	Problem Description
Valid Sudoku	Verify if a given 9x9 Sudoku board is valid based on Sudoku rules.
Sudoku Solver	Solve a partially filled 9x9 Sudoku board to produce a valid solution.
Game of Life	Simulate the next state of a grid based on Conway's Game of Life rules.
Number of Islands	Count the number of distinct islands in a grid where land and water are represented by 1 and 0.
Unique Paths	Find the number of distinct paths from the top-left to the bottom-right corner of a grid.
Minimum Path Sum	Calculate the minimum sum of numbers along a path from the top-left to the bottom-right corner of a grid.

Frequently Asked Questions

Is the matrix important in programming?

Yes, matrices are important in programming, specifically in fields like data science, computer graphics, and machine learning. They serve as foundational structures for representing and manipulating data in multiple dimensions, enabling complex operations such as transformations, rotations, and linear algebra computations.

What is the difference between an array and a matrix?

An array is a data structure that can store a collection of elements, which can be one-dimensional (1D) or multi-dimensional (2D, 3D, etc.). It can hold different data types and is typically used for general-purpose data storage.

A matrix, on the other hand, is a specific type of 2D array that consists of rows and columns. Matrices are usually composed of elements of the same data type.

In summary, all matrices are arrays, but not all arrays are matrices.

What are the applications of matrices in programming?

Matrices have a wide range of applications in programming, including:

Computer graphics: Used for transformations such as rotation, scaling, and translation of images and 3D models.
Image processing: Represent images as matrices of pixels, enabling manipulation and analysis of visual data.
Machine learning: Essential for data representation, where features are organized in matrices for algorithms like neural networks.
Game development: Utilized in physics simulations and to represent game boards or grids.
Data science: Employed in statistical analysis and operations on datasets, such as covariance matrices.
Robotics: Used in control systems and to calculate transformations in robotic movements.
Numerical methods: Involved in solving linear equations and performing operations in scientific computing.

Frequently asked matrix coding questions

Why do interviewers ask matrix coding questions?#

Understanding the matrix structure in computer science#

Must-know matrix operations for coding interviews#

1. Transpose a matrix: #

2. Flip a matrix: #

3. Rotate a matrix: #

Mastering matrix traversals for coding interviews#

1. Row-wise traversal#

2. Column-wise traversal#

3. Diagonal traversal#

4. Spiral traversal#

Python code implementation for matrix traversals#

Frequently asked matrix coding problems#

1. Rotate Image#

2. Spiral Matrix#

3. Spiral Matrix II#