DSA 101: Matrix

#javascript #codenewbie #algorithms

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