DSA 101: Matrix
Tags: algorithms, codenewbie, javascript
Published: 2021-04-20 19:25:24

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. :smile:

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
![Snake Traversal](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6sy2j1nlo2teu84e7i4p.png)
 
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.

```js

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
![Boundary Traversal](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dix9p4peylgufi9cxvo4.png)
 
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.

```js

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
![Spiral Traversal](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eoigi80vuz5zk0hre1pi.png)

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.
![Spiral initial state](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3hfpvzxdfa2m8inr37uc.png)

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.
![step 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/okyxgeb89uhrbofroq2w.png)

2. Traverse the column from `top` to `bottom`. Numbers printed: `8 12 16`. After this, we decrease the `right` by 1.
![step 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oxhmugw1nx9r73uckafy.png)

3. Traverse the row from `right` to `left`. Numbers printed: `15 14 13`. After this, we decrease the `bottom` by 1.
![step 3](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/efz6as4s0xuq2y2vmsov.png)

4. Traverse the column from `bottom` to `top`. Numbers printed: `9 5`. After this, we increase the `left` by 1.
![step 4](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5o83d0eyftmv3chzdsgr.png)

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.

```js
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! :v: I will be sharing more articles on data structures and algorithms. Stay connected.

:earth_asia: [thesanjeevsharma.now.sh](https://thesanjeevsharma.now.sh)