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`

to`right`

. Numbers printed:`1 2 3 4`

. After this, we increase the`top`

by 1.

Traverse the column from

`top`

to`bottom`

. Numbers printed:`8 12 16`

. After this, we decrease the`right`

by 1.

Traverse the row from

`right`

to`left`

. Numbers printed:`15 14 13`

. After this, we decrease the`bottom`

by 1.

Traverse the column from

`bottom`

to`top`

. Numbers printed:`9 5`

. After this, we increase the`left`

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 the`bottom`

is decreasing. Similarly, the`left`

is increasing and the`right`

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.

## Discussion (0)