Matrix means an array with two or more 2 dimensions and is also known as a multidimensional array. Arrays are one of the hot topics of coding contests and interviews of any product as well as service-based companies. Most of the time let candidates think over solutions to problems are asked on multidimensional arrays.
Table of Contents
Welcome to the wonderful series of competitive programming and DSA where we are preparing to crack interviews at top product-based companies. Before beginning, you should know the Golden rule of our series that in the practice section you will try to solve and think over an approach to a problem and then go through the solution.
Brief Introduction to Multidimensional arrays
A multidimensional array is an array with more than one dimension. In more simple words you can assume it as a list of lists or a small array in another array.
- Likewise in an array, we can access the element randomly through an index, same we can access the elements from a multidimensional array using two indexes because a multidimensional array is a collection of rows and columns where the first index defines a row and the second one defines a column index.
- In a 2-d array also elements are stored in contiguous memory locations where each element occupies a fixed memory location.
Applications of Multidimensional Array
- Matrix is used to store elements in tabular format.
- In dynamic programming problems, a multidimensional array (matrix) is used to represent the state of the problem.
- It is used in problems based on graphs, and trees to store visited nodes and different states.
- Used in Grid search problems.
Basic Matrix Problems | Traversal Based Problems on Matrix
Traversing the matrix is the same as traversing an array. To traverse the single dimension array we need only one loop but to traverse the multidimensional array we need two loops where the first loop indicates the index of the row and the second loop denotes the index of the column. The questions we will pick will be very basic to give you understanding and confidence to read and try to solve matrix problems. After solving certain basic questions we will increase the level and move towards company-asked problems.
1) Find the sum of upper and lower triangles
Problem Statement ~ Given a square matrix of N*N. Your task is to print the sum of upper and lower triangle matrix elements. The upper triangle consists of elements that are above the diagonal and the lower triangle consist of elements below the diagonal.
Example
The first line of input contains an integer N. The next N lines contain the N number of space-separated matrix elements.
Approach to finding the sum of a lower and upper triangle in a matrix
I hope that you read the question and tried to think of a solution. If you do not get it then no problem. Take Pen, paper and start writing the elements of the upper triangle and also write the position of the element (Index of an element with respect to row and col) and then think what is the condition that we can write to find the elements if we iterate in matrix or find a condition that how much we have to iterate to find all elements of upper triangle and same with lower triangle matrix.
What we observe is the diagonal elements will be in both the triangles. And in both triangles elements will present from each row so we need to traverse in a complete row each time. The conditions that we can see are all the elements in the upper triangle is present where the row index is less than or equal to the column index and for the lower triangle row index elements are at greater or at an equal index than the column index. Using these two conditions we can easily extract both triangle elements and sum them.
Code ~ Now writing code is not a big deal and you can easily implement the code in any language.
def sumTriangles(matrix, n):
upper_sum = 0 #to store upper triangle sum
lower_sum = 0 #to store lower triangle sum
#loop for row
for i in range(n):
#loop for columns
for j in range(n):
#condition for upper traingle elements
if i <= j:
upper_sum = upper_sum + matrix[i][j]
#condition for lower traingle elements
if i >= j:
lower_sum = lower_sum + matrix[i][j]
#return both sum in list
return [upper_sum, lower_sum]
matrix = [
[4,6,1],
[8,0,5],
[12,7,9]
]
print(sumTriangles(matrix, len(matrix)))
2) Transpose of a Matrix
Problem Statement ~ Given a square matrix of size N*N, find the transpose of a matrix. Transpose of a matrix is obtained by interchanging rows and columns (Rows to columns and columns to rows)
Example
How to find the transpose of a matrix (Approach)
Again we will request you to write both input and output in a paper and try to solve which element is swapping by which to understand how row elements are changing into columns and vice-versa. Now if you observe properly the input and output we see that the diagonal elements remain unchanged in output means we can simply loop in a row and till the diagonal element we can make a second loop and swap both the indexes element like row, column = column, row. To get a better understanding of swapping just have a look over the below figure where the first is a loop for the row and the second is a loop for the column that goes to the row index only. and swap the index elements.
Code ~ If you still did not get the approach then you should dry-run the algorithm on paper and then I can promise it will be pretty clear to you. To dry-run just write the input and how we discuss the approach or code below run it by solving each step on paper.
def MatrixTranspose(matrix, n):
for i in range(n):
for j in range(i):
#swap(matrix[i][j], matrix[j][i])
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
matrix = [
[1,1,1],
[2,2,2],
[3,3,3]
]
MatrixTranspose(matrix, len(matrix))
for row in matrix:
print(*row)
3) Search in Row-wise and column-wise sorted matrix
Problem Statement ~ Given an N*N square matrix where each row and column is sorted in increasing order. You are also given an integer X and your task is to find the position of X in a matrix. If X is not present then return -1, -1 as an output.
Example
- First-line contains T denoting the number of test cases.
- The first line of each test case contains two space-separated integers denoting N and X.
- next N lines contain N number of elements of a matrix.
How would you approach the problem?
After solving the above 2 basic problems you can at least traverse in a matrix. And most of you will just use two loops to traverse in a matrix and check if the current index element is equal to X then you will return the position of the row and column. The complexity of the code is O(N*N)
Binary Search Approach to find elements in sorted row and column matrix
We know that the given row and column in the matrix are sorted so how can we take the advantage of this and reduce the complexity. We all know the binary search algorithm which is used to search an element for a sorted array so the basic idea is we will use binary search to find X in each row which will reduce the complexity from N*N to O(N * log N). And if the element is not found in the entire matrix then return [-1, -1].
def Search(matrix, x):
n = len(matrix)
for i in range(n):
l = 0 #beginning index
r = n-1 #end index
#apply binary search in each row
while(l <= r):
#find middle index
mid = (l + r) // 2
#if ele at mid index equal target
if matrix[i][mid] == x:
return [i, mid]
#if ele greater than target then it must present in first half
elif matrix[i][mid] > x:
r = mid-1
#else target is greater so present in second half
else:
l = mid + 1
#if not found then return -1
return [-1, -1]
matrix = [[4,5], [8,6]]
x = 5
print(Search(matrix, x))
An optimal solution to search elements in a matrix
We can also implement the solution in a linear time. Start from the top-right corner (first-row last column) and check with the target element. Now to move forward there can be three cases.
- If the element is equal to the target element then return the current position.
- If the current element is greater than the target element it means the elements down to it in the same column will also greater and the target element must be present in previous columns so we reduce the index of a column and search in previous columns.
- If the current element is smaller than the target. That means any element in a current row must be smaller than the target so we move to the next row.
If we go out of the matrix then the element is not found and return [-1, -1].
Code ~ Try to implement the code as per discussed algorithm.
def Search(matrix, x):
n = len(matrix)
if n == 0:
return [-1, -1]
i = 0
j = n - 1
while(i < n and j >= 0):
if matrix[i][j] == x:
return [i, j]
# Move to the previous column.
if matrix[i][j] > x:
j -= 1
# Move to the next row.
else:
i += 1
return [-1, -1]
matrix = [[4,5], [8,6]]
x = 5
print(Search(matrix, x))
Increasing Matrix Problems Level from Basic to Easy
Above we have solved a very basic traversal based matrix problem that I hope you are able to understand and implement. This problem was only included in the article to get you familiarised with multidimensional arrays. Now we will pick some logic based matrix problems from the easy category that are asked by different companies.
4) Rotate matrix by 90 degree
Problem Statement ~ Given a square matrix of non-negative integers of size N*N. your task is to rotate the matrix by 90 degrees in an anti-clockwise direction without using any extra space.
Example
How to Rotate Matrix Anti-clockwise? (Approach)
I would request you to first think of a solution at least on paper like how the input matrix is getting converted to output. Take the reference of the above transpose problem because half of the approach is very similar.
The approach is to first do the transpose of the matrix in which the rows change to columns and vice-versa. After this, we can see that the output is just reverse or the last row of transpose appears at the first row so we will swap the last row with the first row, the second row with the second last and so on. To swap the rows we will only move till n/2 because the last row is denoted by the N-1-row index.
Code ~ Implement the code and first try it yourself.
def RotateBy90(matrix, n):
for i in range(n):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
#replace the last row with first row
for i in range(n//2):
for j in range(n):
matrix[i][j], matrix[n-1-i][j] = matrix[n-1-i][j], matrix[i][j]
matrix = [
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
RotateBy90(matrix, len(matrix))
for row in matrix:
print(*row)
5) Spirally Traversing a Matrix
Problem Statement ~ Given a matrix of dimension N * M where N denotes the number of rows and M denotes the number of columns. You need to return the spiral path of the matrix. Observe the below image to understand how the spiral path looks. This question is very interesting asked by top-product based companies including Microsoft, DE-Shaw, Snapdeal, Make my trip, etc.
Example
- The first line contains T denoting the number of test cases.
- The second line contains two space-separated integers as N and M
- The next N lines have an M number of space-separated integers.
For each test case, you have to print the spiral path of a given matrix. It means you have to return an array that contains elements in a spiral path.
How to spirally traverse a matrix?
Try to think of like how we are traversing a matrix by taking a sample input and dry-run it on paper. So we can observe that first, we move from left to right, then top to bottom, right to left, and bottom to top in the matrix. This is all the logic like matrix is spirally traversing. So what we can do is take four-pointers and keep track of these four positions and move in these four directions till the left is less than or equal to the right, and the top is less than or equal to the bottom. Let us understand the algorithm step-wise.
- Suppose we take a 4*4 Matrix as given above in sample input. Define four-pointer like left at 0, top at 0, right at column - 1, bottom at a row - 1.
- We start traversing from left to right by considering the index of the top as a row so we get [1, 2, 3, 4] and after the loop, we increase the top by 1 that this row is completed.
- In a second step we start traversing from top to bottom while considering the right column (Index of a column as right) so we get [8, 12, 16]. After the loop, we decrease the right by 1 indicating that the last column traversing is done.
- In the third step, we traverse from right to left considering the bottom row. So we get [15, 14, 13]. And we decrease the bottom index by 1 the last row traversing is done.
- In the fourth and last step, we need to traverse from bottom to top considering the left index column so we get [9, 5]. And we increase the left index by 1 indicates that left index column traversing is done.
The process continues till the left is less than equal to the right and the top is less than equal to the bottom and finally, we reach out the resultant list of elements as [1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10].
Code ~ Now implementing code is very easy.
def spiralPathMatrix(matrix, n, m):
left = 0
right = m-1
top = 0
bottom = n-1
ans = []
while top <= bottom and left <= right:
#1. move from left to right
for i in range(left, right+1):
ans.append(matrix[top][i])
top += 1
#2. move from top to bottom
for i in range(top, bottom+1):
ans.append(matrix[i][right])
right -= 1
#3. move from right to left
if top <= bottom:
for i in range(right, left-1, -1):
ans.append(matrix[bottom][i])
bottom -= 1
#4. move from bottom to top
if left <= right:
for i in range(bottom, top-1, -1):
ans.append(matrix[i][left])
left += 1
return ans
6) Flip Bit in Boolean Matrix
Problem Statement ~ Given a binary matrix of size N*N. Suppose 'i' denotes row and j denotes column index. Now if in the matrix [i][j] is equal to 0, then you have to flip every 1 in the ‘i’th row and ‘j’th column (In the same row and column as 0).
Your task is to return the total number of flips done over all the elements of the matrix.
NOTE
- The matrix contains only 0 or 1.
- The flip operation is performed only for the 0s in the original matrix, not for the new 0s formed after the flip operation.
- If the cell is already flipped, don't flip it twice (the same row and column has 0 the common 1 appearing in both should be flipped only one time)
Your task is to return the minimum number of flips needed.
Example
- The first line contains T denoting the number of test cases.
- The first line of each test case contains N (matrix dimension N*N)
- The next N lines contain N space-separated integers.
Observe the below examples for better understanding.
How to find a Minimum number of flips in Boolean Matrix?
The problem is very interesting and asked in different forms but I can promise that after solving this you can easily implement all the different forms of the same problem. So what we can do is first know in which row and column there is a presence of 0 and after that in that particular row or column we can iterate and check if there is 1 we can convert to 0 and increase the count.
- Create two boolean arrays of size N which initially stores False.
- Iterate in the matrix and check if the current element is equal to 0. If true then change the boolean row array current index to True and the same for the column array.
- After this traverse in boolean row array and if the value is True then keeping row index as the same traverse in all columns and check that if 1 present in matrix and flip to 0 and increase the count.
- The above step same followed for the column and we get the resultant minimum flips required.
Code - Try to implement the logic on your own.
#code
def countFlip(mat):
n = len(mat)
arr_row = [False] * n
arr_col = [False] * n
temp = mat.copy()
for i in range(n):
for j in range(n):
if mat[i][j] == 0:
arr_row[i] = True
arr_col[j] = True
ans = 0
#flip every 1 in 0 in row where 0 is present
for i in range(n):
if arr_row[i]:
for j in range(n):
if temp[i][j] == 1:
temp[i][j] = 0
ans += 1
#flip every 1 in 0 in column where 0 is present
for i in range(n):
if arr_col[i]:
for j in range(n):
if temp[j][i] == 1:
temp[j][i] = 0
ans += 1
return ans
End Notes
We have discussed and solved some of the basic and easy level matrix problems that are asked by most companies. There are still some medium level questions are remaining to cover that we will cover in an upcoming blog because the article will be long and may feel cumbersome to jump directly to a higher level so we will suggest you visit your favourite coding platform and try to solve some basic and easy level matrix problems.
I hope that each and every problem we have discussed in this blog as a part of the competitive series is clear and you can solve it if you face such a problem in future. If you have any queries or suggestions then please post them in the comment section below so we can help you out and get others also know what extra we should learn. You can also post your queries through our contact form.
Thank you for your time! 😊