Hey,
This article is a refresher for algorithms. Since most of us hardly study any algorithms when we are not interviewing, this article aims to bring back some memories. 😄
We'll be discussing Matrix algorithms.
We'll be covering three types of traversal algorithms: Snake traversal, Boundary traversal, and Spiral traversal. We all know the basic traversal; these are some other fun traversals that can be helpful in an interview.
Snake Traversal
For the given matrix, we want to print all the numbers in snake order. So, the output will be:
1 2 3 6 5 4 7 8 9
Logic:
We have to change the direction after every row traversal. How do we know in which direction to go? What changes after every row traversal? Do we have a pattern?
Yes! The rows are even or odd indexed. For every even indexed row, we need to go from left to right, and for every odd indexed row, right to left.
const matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
// snake traversal
for (let i = 0; i < matrix.length; i++) {
if (i % 2 === 0) {
for (let j = 0; j < matrix[i].length; j++) {
console.log(matrix[i][j])
}
} else {
for (let j = matrix[i].length - 1; j > -1; j--) {
console.log(matrix[i][j])
}
}
}
// output
// 1 2 3 6 5 4 7 8 9
Boundary Traversal
For the given matrix, we want to print all the numbers on the boundary. So, the output will be:
1 2 3 6 9 8 7 4
Logic:
There's no trick here. The solution is pretty straightforward. We access each element on the boundary and print them.
const matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
// boundary traversal
const R = matrix.length
const C = matrix[0].length
for (let i = 0; i < C; i++) {
console.log(matrix[0][i])
}
for (let i = 1; i < R; i++) {
console.log(matrix[i][C - 1])
}
for (let i = C - 2; i > -1; i--) {
console.log(matrix[R - 1][i])
}
for (let i = R - 2; i > 0; i--) {
console.log(matrix[i][0])
}
// output
// 1 2 3 6 9 8 7 4
Spiral Traversal
For the given matrix, we want to print all the numbers in spiral order. So, the output will be:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Logic:
This looks a bit tricky at first but it isn't. The basic idea is to have 4 variables - top
, right
, bottom
, and left
. These variables will help us keep track of what row and column should be traversed.
Initially, top
is 0, right
is 3 (# of columns - 1), bottom
is 3 (# of rows - 1), and left
is 0.
Next, we just need to follow some basic steps:
Traverse the row from
left
toright
. Numbers printed:1 2 3 4
. After this, we increase thetop
by 1.
Traverse the column from
top
tobottom
. Numbers printed:8 12 16
. After this, we decrease theright
by 1.
Traverse the row from
right
toleft
. Numbers printed:15 14 13
. After this, we decrease thebottom
by 1.
Traverse the column from
bottom
totop
. Numbers printed:9 5
. After this, we increase theleft
by 1.
If we look closely, we are at the same point from where we started. The difference is we are on an inner layer/path. From here on, we can repeat steps 1 to 4. All we need to do is place a check for when we need to stop. The
top
is increasing and thebottom
is decreasing. Similarly, theleft
is increasing and theright
is decreasing. All we need to check is that they don't cross each other.
const matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
// spiral traversal
let top = 0, left = 0, bottom = 3, right = 3;
while (left <= right && top <= bottom) {
for (let i = left; i <= right; i++) {
console.log(matrix[top][i])
}
top++;
for (let i = top; i <= bottom; i++) {
console.log(matrix[i][right])
}
right--;
for (let i = right; i >= left; i--) {
console.log(matrix[bottom][i])
}
bottom--;
for (let i = bottom; i >= top; i--) {
console.log(matrix[i][left])
}
left++;
}
// output
// 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
That's all, folks! ✌️ I will be sharing more articles on data structures and algorithms. Stay connected.
Top comments (0)