Wednesday, June 10, 2020

Leetcode Medium - Number of Islands

Today, I started solving Leetcode medium questions.

For reference purpose, I'll be jotting down my solutions to these problems here.

Following is an accepted quick solution to the  Number of Islands problem (problem #200) on Leetcode. This solution implements it using the land "sinking" technique.


class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length==0)
            return 0;
        
        int islands = 0;
        for (int i=0; i<grid.length; i++) {
            for (int j=0; j<grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    islands += dfs(grid, i, j);
                }
            }
        }
        return islands;
    }
    
    int dfs(char[][] grid, int i, int j) {
        if (i<0 || i>=grid.length || j<0 || j>=grid[i].length || grid[i][j]=='0') {
            return 0;
        }
        
        //sink
        grid[i][j] = '0';
        
        dfs(grid, i+1, j);
        dfs(grid, i, j+1);
        dfs(grid, i-1, j);
        dfs(grid, i, j-1);
        
        return 1;
        
    }
}

No comments:

Post a Comment

Featured Post

interviewBit Medium: Palindrome Partitioning II

Problem Name:  Palindrome Partitioning II Problem Description : https://www.interviewbit.com/problems/palindrome-partitioning-ii/ Problem Ap...