DEV Community

codingpineapple
codingpineapple

Posted on

LeetCode 200. Number of Islands (javascript solution)

Description:

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Solution:

Time Complexity : O(n^2)
Space Complexity: O(1)

// DFS solution
var numIslands = function(grid) {
    const gridLength = grid.length
    const rowLength = grid[0].length
    let count = 0

    // Loop through every cell in the grid
    for(let i = 0; i < gridLength; i++){
        for(let j = 0; j < rowLength; j++) {
            // When we hit land we know we are on an island
            // We will use this cell to visit all the 1's connected to it
            // Once we've visited all the 1's connected to this cell then we increase the count
            if(grid[i][j]==="1") {
                dfs(i, j)
                count++
            }
        }
    }

    // DFS search
    // Look in all directions and set the current cell to 0 to prevent this cell from being visited again
    function dfs(i,j) {
        if(grid[i][j] ==="1") {
            grid[i][j] = '0'
            // look north
            if(i - 1 >= 0) dfs(i-1,j)
            // look east
            if(j + 1 < rowLength) dfs(i,j+1)
            // look south
            if(i + 1 < gridLength) dfs(i+1,j)
            // look west
            if(j - 1 >= 0) dfs(i,j-1)
        }
    }

    return count
};

Enter fullscreen mode Exit fullscreen mode

Top comments (0)