How to use Depth First Search (DFS) In Javascript
- Create an array of N*M for marking the visited cells so far. Initially, all the cells will be unvisited.
- Create arrays called dx (for rows) and dy (for columns) to represent the four possible adjacent directions for each cell.
- Now, in the recursive DFS function, the current row, column and the direction will be the parameters.
- As a base case, check if the current cell is within the bounds of the given matrix and if the cell has not been visited earlier.
- If not, then mark it as visited and print its value.
- Calculate the value of the next row and column by adding the respective values from dx and dy arrays. Make a recursive call in the new indices of those directions.
- When one traversal gets complete, change the direction to the next clockwise direction to print the matrix spirally.
- Start the DFS from the top-left corner of the given matrix which will be the first cell.
Example: Below is the implementation of the above approach:
Javascript
// JavaScript code for the above approach function spiralDFS(matrix) { const N = matrix.length; const M = matrix[0].length; // Initialize a visited array let vis = new Array(N); for (let n = 0; n < N; n++) { vis[n] = new Array(M).fill(false); } // Row and column directions for // right, down, left, and up const dx = [0, 1, 0, -1]; const dy = [1, 0, -1, 0]; let i = 0; let row = 0; let col = 0; const result = []; // DFS function function dfs(row, col) { // Base case: Check if the current // cell is within bounds and unvisited if (row < 0 || row >= N || col < 0 || col >= M || vis[row][col]) { return; } // Mark the cell as visited // and add it to the result result.push(matrix[row][col]); vis[row][col] = true; // Calculate the next row and column const nrow = row + dx[i]; const ncol = col + dy[i]; // Recursively call DFS with the new indices dfs(nrow, ncol); // If DFS completes in the current // direction, change direction clockwise if (nrow < 0 || nrow >= N || ncol < 0 || ncol >= M || vis[nrow][ncol]) { i = (i + 1) % 4; const nrow = row + dx[i]; const ncol = col + dy[i]; dfs(nrow, ncol); } } // Start DFS from the top-left // corner of the matrix dfs(row, col); console.log(result.join(' ')); } // Example const matrix = [ [1, 2, 3], [6, 5, 7], [4, 8, 11], [12, 0, 16] ]; spiralDFS(matrix); |
Output
1 2 3 7 11 16 0 12 4 6 5 8
Time Complexity: O(N*M) To traverse the entire matrix O(m*n) time is required.
Space Complexity: O(N*M) We use an external data structure here, which is a 2D visited matrix. Also, the algorithm will consume a recursive stack space.
JavaScript Program to Print Given Matrix in Spiral Form
Write a JavaScript program to print a given 2D matrix in spiral form.
You are given a two-dimensional matrix of integers. Write a program to traverse the matrix starting from the top-left corner which moves right, bottom, left, and up in a spiral pattern until all the elements are visited. Let us understand it with the examples and figures given below:
Examples:
Example 1:
Input: matrix = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
Output: [1 2 3 6 9 8 7 4 5]
Spiral Matrix Example-1
Example 2:
Input: matrix = [[1, 2, 3, 4],
[12, 13, 14, 5],
[11, 16, 15, 6],
[10, 9, 8, 7]]
Output: [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]
Spiral Matrix Example-2
Table of Content
- Using Boundary Traversal Approach
- Using Simulation Approach
- Using Recursion in JavaScript
- Using Depth First Search (DFS)
Contact Us