## DEV Community is a community of 862,249 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # DSA 101: Matrix

Hey,

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

for (let i = 0; i < C; i++) {
console.log(matrix[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])
}

// 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:

1. Traverse the row from `left` to `right`. Numbers printed: `1 2 3 4`. After this, we increase the `top` by 1. 2. Traverse the column from `top` to `bottom`. Numbers printed: `8 12 16`. After this, we decrease the `right` by 1. 3. Traverse the row from `right` to `left`. Numbers printed: `15 14 13`. After this, we decrease the `bottom` by 1. 4. Traverse the column from `bottom` to `top`. Numbers printed: `9 5`. After this, we increase the `left` by 1. 5. 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.