Home/Blog/Interview Prep/Frequently asked matrix coding questions
Home/Blog/Interview Prep/Frequently asked matrix coding questions

Frequently asked matrix coding questions

11 min read
Dec 17, 2024

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×nm \times n, where mm is the number of rows, and nn 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]matrix[i][j] is an element from the ithi^{th} row and the jthj^{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:

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

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

Python code for transposing and flipping a matrix:

Let’s explore how to implement the code for transposing a matrix, as well as flipping a matrix both horizontally and vertically.

Note: Click "Run" to execute the code below.

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

3. Rotate a matrix: #

This turns the matrix around a center point by a specific angle, such as 90, 180, or 270 degrees.

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.

main.py
transpose_matrix.py
flip_matrix.py
from transpose_matrix import *
from flip_matrix import *
# Matrix 1 # Matrix 2
# 0 1 3 # 1 2 3
# 9 5. 8 # 4 5 6
# # 7 8. 9
def rotate_90_degrees_anticlockwise(matrix):
# Replace this placeholder return statement with your code
return [[]]
Rotate a matrix by 90 degrees clockwise

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.

2. Column-wise traversal#

Traverse the matrix column by column, moving from the top row to the bottom in each column.

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.

4. Spiral traversal#

Traversing the matrix in a spiral pattern, starting from the outermost elements and moving towards the center. The traversal direction alternates between right, down, left, and up until all elements are visited.

Python code implementation for matrix traversals#

Let’s look at how to implement different matrix traversal methods in Python.

# 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

That's it for exploring common matrix transformations and traversals.

If you want to learn more of such techniques and patterns to make problem-solving easier, check out these courses by Educative.

Frequently asked matrix coding problems#

Now let's explore some commonly asked matrix coding problems.

1. Rotate Image#

This problem involves rotating a given 2D square matrix (image) by 90 degrees clockwise. The challenge is to do this in-place, modifying the original matrix without using additional space.

We did look at a way to rotate a matrix 90 degrees clockwise. Let’s see if you remember it.

Q

How do we rotate a matrix 90 degrees clockwise?

A)

Reverse the order of elements in each row of the matrix.

B)

Mirror each row of the matrix across x-axis.

C)

Transpose the matrix and then reverse each row.

Great! Now you know how to rotate a matrix 90 degrees clockwise.

2. Spiral Matrix#

This task requires returning the elements of a 2D matrix in a spiral order. Starting from the top-left corner, you traverse right, then down, left, and up, repeating until all elements are collected.

3. Spiral Matrix II#

This problem is a follow up of the previous problem, Spiral Matrix. Here, you are given a positive integer nn and you need to generate a new n×nn \times n matrix filled with integers from 1 to n2n^2 in spiral order.

Let's explore one way to solve this problem:

  1. Initialize the matrix: Start by making an nn × nn matrix, initially filled with zeros or any placeholder value. This matrix will later be filled with numbers.

  2. 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.

  3. Fill in numbers: Start filling in the numbers from 1 to n2n^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.

  4. 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.

  5. Repeat: Keep filling and adjusting the boundaries until you've filled all the numbers from 1 to n2n^2.

4. Set Matrix Zeros#

In this problem, given an m×nm \times n integer matrix, if any element is 00, you have to set all elements in its row and column to 00. 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:

  1. 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.

  2. 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.

6. Diagonal Traverse#

The goal here is to return the elements of a matrix in a diagonal order. You start from the top-left and traverse diagonally until you reach the bottom-right, alternating directions for each diagonal (zig-zag diagonal traversal).

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:

  1. Iterate through the matrix: Loop through each element of the first row and the first column because these correspond to all the diagonals.

  2. 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.

  3. 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. 

We've explored the top 7 matrix coding problems frequently asked by leading tech companies like MAANG. These problems focus on matrix operations alone. However, there are many other coding problems involving matrices combined with other algorithms or patterns. Some well-known examples on popular coding platforms include:

Problem Name

Problem Description

Valid Sudoku

Verify if a given 9x9 Sudoku board is valid based on Sudoku rules.

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.

Count the number of distinct islands in a grid where land and water are represented by 1 and 0.

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.

Continue your coding journey with Educative #

Mastering matrix problems is just one piece of the puzzle. Understanding and practicing other data structures and algorithms and coding patterns is also important for a well-rounded preparation.

If you aim to land a job at one of the tech giants like MAANG, explore the learning paths offered by Educative. These paths provide a directed learning experience with the most frequently asked problems, helping you prepare effectively.

Keep exploring, practicing, and pushing your boundaries—you’ve got this! Happy learning!

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?

What are the applications of matrices in programming?


Written By:
Minahil Yaser
 
Join 2.5 million developers at
Explore the catalog

Free Resources