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

Node.js: Extract text from image using Tesseract.

In this article, we will see how to extract text from images using Tesseract . So let's start with this use-case, Suppose you have 300 screenshot images in your mobile which has an email attribute that you need for some reason like growing your network or for email marketing. To get an email from all these images manually into CSV or excel will take a lot of time. So now we will check how to automate this thing. First, you need to install Tesseract OCR( An optical character recognition engine ) pre-built binary package for a particular OS. I have tested it for Windows 10. For Windows 10, you can install  it from here. For other OS you make check  this link. So once you install Tesseract from windows setup, you also need to set path variable probably, 'C:\Program Files\Tesseract-OCR' to access it from any location. Then you need to install textract library from npm. To read the path of these 300 images we can select all images and can rename it to som...
1 comment
Read more

Globant part 1

 1)call,apply,bind example? Ans: a. call Method: The call method is used to call a function with a given this value and arguments provided individually. Javascript code: function greet(name) {   console.log(`Hello, ${name}! I am ${this.role}.`); } const person = {   role: 'developer' }; greet.call(person, 'Alice'); // Output: Hello, Alice! I am developer. In this example, call invokes the greet function with person as the this value and passes 'Alice' as an argument. b. apply Method: The apply method is similar to call, but it accepts arguments as an array. Javascript code: function introduce(language1, language2) {   console.log(`I can code in ${language1} and ${language2}. I am ${this.name}.`); } const coder = {   name: 'Bob' }; introduce.apply(coder, ['JavaScript', 'Python']); // Output: I can code in JavaScript and Python. I am Bob. Here, apply is used to invoke introduce with coder as this and an array ['JavaScript', 'Pyt...
Post a Comment
Read more

Maximizing MongoDB Performance: A Guide to Effective Indexing Strategies

Introduction: MongoDB, a leading NoSQL database, offers unparalleled flexibility and scalability. However, achieving optimal query performance in MongoDB often relies on implementing effective indexing strategies. In this article, we'll delve into various indexing techniques and provide real-world examples to demonstrate their impact on query performance. Single Field Index: Single field indexes are ideal for accelerating queries that filter, sort, or search based on a specific field. Let's consider a scenario where we have a collection of user profiles, and we frequently query users by their username field: db.users.createIndex({ "username": 1 }) This index significantly speeds up queries like: db.users.find({ "username": "john_doe" }) Compound Index: Compound indexes are invaluable when queries involve multiple fields. Suppose we have a collection of products and often filter by both category and price: db.products.createIndex({ "category...
Post a Comment
Read more