A two-dimensional array or simply 2D array is a format to store data in a grid format that is rows and columns format. There is no special way of declaring a 2D array in JavaScript, we can simply pass an array as an element inside another array. the array obtained in this method will be created as a 2D array.
Syntax:
var arr = [[…], […], …]
Examples:
Input: grid = [[1, 2, 3, 4 ], [5, 6, 7, 8 ], [9, 10, 11, 12 ], [13, 14, 15, 16 ] ]
Output: 1 2 5 3 6 9 4 7 10 13 8 11 14 12 15 16Input: grid = [ [ -1, 2, 3 ], [ 0, 9, 8 ], [ 1, 0, 1 ] ]
Output: -1 2 3 8 1 0 9 0 1
Traversal of 2D Array:
In general, there are two ways of traversing a 2D array. The two methods are:
Approach 1: To solve the problem using BFS traversal follow the below steps:
BFS traversal is also called as level order traversal and we use a queue data structure to implement it. In this algorithm first, all the nodes at the same level are traversed and child nodes are traversed.
Follow the below steps to solve the problem:
- Select the root node and initialize a queue
- Mark the node visited, print it then push it into the queue
- Initialize a 2D array to mark the visited cells and mark the root node as visited
- Now iterate till the queue is not empty and perform the following steps:
- Dequeue the current cell present at the beginning and print it.
- Visit its adjacent cells
- Mark them visited, print it, and enqueue them to queue
Below is the implementation for the above approach:
Javascript
// Javascript program for the above approach
var ROW = 4;
var COL = 4;
// Direction vectors
var dRow = [-1, 0, 1, 0 ];
var dCol = [0, 1, 0, -1 ];
// Function to check if a cell
// is be visited or not
function isValid(vis, row, col)
{
// If cell lies out of bounds
if (row < 0 || col < 0
|| row >= ROW || col >= COL)
return false;
// If cell is already visited
if (vis[row][col])
return false;
// Otherwise
return true;
}
// Function to perform the BFS traversal
function BFS( grid, vis, row, col)
{
// Stores indices of the matrix cells
var q = [];
// Mark the starting cell as visited
// and push it into the queue
q.push([row, col ]);
vis[row][col] = true;
// Iterate while the queue
// is not empty
while (q.length!=0) {
var cell = q[0];
var x = cell[0];
var y = cell[1];
console.log( grid[x][y] + " ");
q.shift();
// Go to the adjacent cells
for (var i = 0; i < 4; i++) {
var adjx = x + dRow[i];
var adjy = y + dCol[i];
if (isValid(vis, adjx, adjy)) {
q.push([adjx, adjy ]);
vis[adjx][adjy] = true;
}
}
}
}
// Driver Code
// Given input matrix
var grid = [[1, 2, 3, 4 ],
[5, 6, 7, 8 ],
[9, 10, 11, 12 ],
[13, 14, 15, 16 ] ];
// Declare the visited array
var vis = Array.from(Array(ROW), ()=> Array(COL).fill(false));
BFS(grid, vis, 0, 0);
1 2 5 3 6 9 4 7 10 13 8 11 14 12 15 16
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
Approach 2: To solve the problem using DFS traversal follow the below idea:
DFS traversal is an algorithm that uses stack data structure to implement LIFO(Last In First Out) principle. In this algorithm, we will first select the node mark it visited and visit all its child nodes. Once no child node is left we will use backtracking to visit the unvisited nodes.
Follow the steps to solve the problem:
- Select the root node and initialize a stack
- Mark the node visited, print it then push it into the stack
- Initialize a 2D array to mark the visited cells and mark the root node as visited.
- Now iterate till the queue is not empty and perform the following steps:
- Pop the element at top of the stack and print it
- Push the adjacent cells into a stack
Below is the implementation for the above approach:
Javascript
// Javascript program of the above approach
var ROW = 3;
var COL = 3
// Initialize direction vectors
var dRow = [0, 1, 0, -1];
var dCol = [ -1, 0, 1, 0];
// Function to check if mat[row][col]
// is unvisited and lies within the
// boundary of the given matrix
function isValid(vis, row, col)
{
// If cell is out of bounds
if (row < 0 || col < 0
|| row >= ROW || col >= COL)
return false;
// If the cell is already visited
if (vis[row][col])
return false;
// Otherwise, it can be visited
return true;
}
// Function to perform DFS
// Traversal on the matrix grid[]
function DFS(row, col, grid, vis)
{
// Initialize a stack of pairs and
// push the starting cell into it
var st = [];
st.push([ row, col ]);
// Iterate until the
// stack is not empty
while (st.length!=0) {
// Pop the top pair
var curr = st[st.length-1];
st.pop();
var row = curr[0];
var col = curr[1];
// Check if the current popped
// cell is a valid cell or not
if (!isValid(vis, row, col))
continue;
// Mark the current
// cell as visited
vis[row][col] = true;
// Print the element at
// the current top cell
console.log( grid[row][col] + " ");
// Push all the adjacent cells
for (var i = 0; i < 4; i++) {
var adjx = row + dRow[i];
var adjy = col + dCol[i];
st.push([ adjx, adjy ]);
}
}
}
// Driver Code
var grid = [ [ -1, 2, 3 ],
[ 0, 9, 8 ],
[ 1, 0, 1 ] ];
// Stores whether the current
// cell is visited or not
var vis = Array.from(Array(ROW), ()=> Array(COL).fill(false));
// Function call
DFS(0, 0, grid, vis);
-1 2 3 8 1 0 9 0 1
Time Complexity: O(N * M)
Auxiliary Space: O(N * M )
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
