Skip to main content

Diwali Data Structure Famous Problem



Number of Islands 

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.




Solution Javascript:
var grid = [
    ["1","1","0"],
    ["0","1","0"],
  ]

  const numIslands =  (grid) => {
    let count = 0 // the counted islands
    //Go though each cell of the 2d array/grid 
    for(let row = 0; row < grid.length; row++){
    for(let col = 0; col < grid[row].length; col ++){
    if(grid[row][col] == '1'){
        count ++
        explore(row,col, grid)
            }
        }
    }
    return count
}



// Takes a cell in a grid with a “1” , turns it into a “0” and explores (DFS) any of the left, right, up, down 1’s
function explore(row, col, grid){
    //Let's return IF
    // row < 0 OR col < 0 OR row is out of bounds(meaning the row is larger than the number of arrays in the 2d array) OR col is at/out of bounds (meaning the current col is at/over the number of elements a row has.)
     if (row < 0 || col < 0 || row >= grid.length  
         || col >= grid[row].length || grid[row][col] === '0')  {
        return
    }
    
    //Otherwise, we should explore it!
    //First let's set the current spot to "0"
    grid[row][col]='0'
    
    //Possibilites:
    // 1) 1 to the right, left, top, bottom
    //right
    explore(row, col+1, grid)   
    //Left
    explore(row, col-1, grid)  
    //Down
    explore(row+1, col, grid) 
    //Up
    explore(row-1, col, grid)   

}
numIslands(grid);




Comments

Post a Comment

Popular posts from this blog

Coding Interview Questions Set 1

From this article, I will be sharing with you all a series of articles on coding interview questions. So please stay connected for the latest set of questions. It will be a good brainstorming exercise and will also prepare you for coding interviews and will definitely boost your confidence. So let's start, 1)Reverse of a string with only O(1) extra memory. Solution: var reverse = function(string) {     let result = ''     for(let i= string.length -1; i >= 0; i--){         result += string[i];     }     return result; }; 2)Fizz Buzz: Write a program that will accept a number n and will output number till n but for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”. Solution: var fizzBuzz= function(n) {     const arr=[]     for(i=1; i<=n; i++){ ...
9 comments
Read more

JavaScript: Debouncing | Flipkart UI Interview Question.

To understand this programming practice will go with a quick example. We all do online shopping and we do search for products on Flipkart on the search bar. So when we type on search bar i.e on every keypress we are actually giving API requests to the server, which in response gives us suggestions. Actually, it's a time-consuming task and may degrade the performance of the webpage. So to improve the performance we use debounce function which actually acts as a controller which reduces the API request to the server on keypress event. In simple terms, we are giving API request only after a certain amount of time between two keypress events. A debounce is a higher-order function. Higher-order function: A function that returns another function. Let's dive deep: HTML Code: <input type="text" onkeyup="searchProducts()"/> Consider this as a search bar for Flipkart. On any keypress, we are calling searchProducts() function. Javascri...
Post a Comment
Read more

Node.js: Bundling your Node.js application to single executable for Windows.

In this article, we will see how to bundle Node.js application to a single executable for Windows. What's the need? Well recently, I had taken a work where I needed to convert pdf's(Of similar format) to excel sheet. So I was reading the pdf's from a folder in desktop and I was storing the output excel sheet into a separate folder on the desktop. I used Node.js for the program. Now the client wanted it to install the program on 25 windows machine and his budget was really low. So it was also not possible for me to install node.js for 25 machines and then install the required dependency for each one. One of the solution: While I was searching for an easy solution I found this amazing npm module pkg . This module can make your node.js app work like plug and play type. No need to install Node.js on the client machine or any other dependency.  It helps to make a commercial or trial version of your node.js application without exposing the source code. I found ...
Post a Comment
Read more