Traversing 2 D array

#### 💡 First Understand JavaScript multidimensional array

JavaScript does not provide the multidimensional array natively. However, We create a multidimensional array by defining an array of elements, where each element also contains an array.

```** 2 D Matrix Example **
[
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
];```

💡 Create 2 D Array in JavaScript

```const rows = new Array(4).fill('');
console.log('created blank rows :', rows);

const testBlankMatrix = rows.map(() => new Array(5).fill(false));
console.log('created test matrix of 4 * 5 :', testBlankMatrix);

// Output

[
[false, false, false, false, false],
[false, false, false, false, false],
[false, false, false, false, false],
[false, false, false, false, false],
]; ```

💡 Let’s See 3-D array Structure – each element of the array is a two-dimensional array.

```**  3-D array **

const threeD = [
[
[1, 2, 3],
[4, 5, 6],
],
[
[7, 8, 9],
[10, 11, 12],
],
];```

BFS & DFS

#### 💡 What is BFS?

`BFS stands for Breadth-First Search`. It is also known as `level order traversal`.
BFS algorithm uses a `queue `data structure to track which node to visit next. Upon reaching that element, the algorithm adds it to the queue to visit this later.
When we use the BFS algorithm for the traversal in a graph, we can consider any node as a root node.
BFS is a traversal technique in which all the vertex of the same level are explored first, and then we move to the next level.
BFS does not use the backtracking concept.

A real example of a Queue data structure is waiting in line at the ticket window. Who comes first in line, that will take the ticket first.
Adding an element in the queue is called `Enqueue `and removing an item from the queue is called `Dequeue`.

#### 💡 What is DFS?

DFS stands for `Depth First Search.` In DFS traversal, the `stack `data structure is used, which works on the LIFO (Last In First Out) principle.
In DFS, traversing can be started from any node, or we can say that any node can be considered as a root node until the root node is not mentioned in the problem.
DFS is also a traversal technique in which traversal is started from the root node and explores the nodes until the node has no unvisited adjacent nodes.
DFS uses backtracking to traverse all the unvisited nodes.

BFS Steps

1. Start from any Node (that is called as root node)
2. Visit that Node and push into Queue
3. Explore all adjacent of visited Node in any order and push all into Queue
4. Once all adjacent pushed into Queue then pick a new vertex
5. This new vertex will be the first non explored element from the queue

DFS Steps

1. Start from any Node (that is called as root node)
2. Visit that Node and push into Stack
4. Visit any one of its adjacent and push into Stack
6. Repeat 4 and 5
7. Once there is no adjacent remaining then backtrack to the parent
8. Visit another adjacent of that parent and push into stack
9. If still no any parent’s adjacent then backtrack to its parent.
10. Do this until all vertex traversed.

https://www.javatpoint.com/bfs-vs-dfs

### 💡 Traversal in 2 D array

Let’s find adjacent of any element in 2 D array

If we see a 2 D array, then we will find that there are 4 adjacent to every element and directions are `up, right, bottom, and left.`

If we take – (See the first Image of this Post)

```Node A - adjacent are ->
up (-1, 0) - undefined
right (0, 1) - B
down (1, 0) -  F
left (0, -1) - undefined```
```Node H - adjacent are ->
up (-1, 0) - C
right (0, 1) - I
down (1, 0) -  M
left (0, -1) - G```

#### 💡 Directions are –

```  [-1, 0], //up
[0, 1], //right
[1, 0], //down
[0, -1], //left

```

Let’s see algorithm of DFS travering in 2 D Matrix

```const traversalDFS = (matrix) => {
if (!matrix.length) {
return [];
}

// store all visited element and finally returned this
const values = [];

// created 2-d matrix same as given matrix with falsy values
const seen = new Array(matrix.length).fill('').map(() => new Array(matrix.length).fill(false));

// call recursive function dfs
dfs(matrix, 0, 0, values, seen);

return values;
};

const dfs = (matrix, row, col, values, seen) => {
// row should not be less then 0
// row should not be greater then matrix.length
// col should not be less then 0
// col should not be greater then matrix.length
// element should not be visited (seen[row][col])

const invalidRow = row < 0 || row >= matrix.length;
const invalidCol = col < 0 || col >= matrix.length;
if (invalidRow || invalidCol || seen[row][col]) {
return;
}

seen[row][col] = true; // marked true so that not to visit this again

values.push(matrix[row][col]); // push visited element into values array

for (let dir of directions) {
dfs(matrix, row + dir, col + dir, values, seen);
}
};```
```** Output **

const testMatrix = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
];
console.log('traversalDFS(testMatrix) :', traversalDFS(testMatrix));
> [1, 2, 3, 4, 5, 10, 15, 20, 19, 14, 9, 8, 13, 18, 17, 12, 7, 6, 11, 16]

const test2 = [
[2, 3],
[4, 5],
];
console.log('traversalDFS(test2) :', traversalDFS(test2));
> traversalDFS(test2) : (4) [2, 3, 5, 4]

const test3 = [[]];
console.log('traversalDFS(test3) :', traversalDFS(test3));
> traversalDFS(test3) : []

const test4 = [];
console.log('traversalDFS(test4) :', traversalDFS(test4));
> traversalDFS(test4) : []```

Let’s see algorithm of BFS travering in 2 D Matrix

```const traversalBFS = (matrix) => {
if (!matrix.length) {
return [];
}

// store all visited element and finally returned this
const values = [];
// BFS uses queue to process data, Initially store first element
const queue = [[0, 0]];

// created 2-d matrix same as given matrix with falsy values
const seen = new Array(matrix.length).fill('').map(() => new Array(matrix.length).fill(false));

while (queue.length) {
const currentPos = queue.shift();
const row = currentPos;
const col = currentPos;

// row should not be less then 0
// row should not be greater then matrix.length
// col should not be less then 0
// col should not be greater then matrix.length
// element should not be visited (seen[row][col])

const invalidRow = row < 0 || row >= matrix.length;
const invalidCol = col < 0 || col >= matrix.length;
if (invalidRow || invalidCol || seen[row][col]) {
continue; // continue while loop
}

seen[row][col] = true; // marked true so that not to visit this again

values.push(matrix[row][col]); // push visited element into values array

// Push adjacent item in to queue
for (let dir of directions) {
queue.push([row + dir, col + dir]);
}
}

return values;
};```
```** Output *******

const testMatrix1 = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
];
console.log('traversalBFS(testMatrix1) :', traversalBFS(testMatrix1));
> traversalBFS(testMatrix1) : (16) [1, 2, 5, 3, 6, 9, 4, 7, 10, 13, 8, 11, 14, 12, 15, 16]

const test5 = [
[2, 3],
[4, 5],
];
console.log('traversalBFS(test5) :', traversalBFS(test5));
> traversalBFS(test5) : (4) [2, 3, 4, 5]```

Traversing 2 D array