Number of islands (leetcode)

Category: mm

Question ကိုဒီလင့်မှာသွားဖတ်နိုင်ပါတယ်။

Question explanation

ဒီ question ကမေးထားတာကရှင်းပါတယ်။ Grid ပေးထားတယ် (M x N grid ပေါ့)။ အဲ့မှာ land ဆိုရင် 1 လို့ယူပြီး 0 ဆို water လို့မှတ်တယ်။ Island ဆိုတာကဘယ်လိုသပ်မှတ်သလဲဆို land တစ်ခုကသူနဲ့ ဆက်စပ်နေတဲ့ land တွေကိုစုလိုက်မယ်။ စကားနဲ့ပြောရတာသိပ်မရှင်းရင်အောက်ကဆွဲထားတဲ့ပုံကိုကြည့်ရင်သဘောပေါက်မှာပါ။

အဲ့မှာဆက်စပ်တယ်ဆိုတာ left/right/up/down ဆက်နေတာကိုမှဆက်စပ်တယ်လို့ယူလို့ရပါတယ်။ Question ကရှင်းပါတယ် ပေးထားတဲ့ grid မှာ island ဘယ်နှခုရှိလဲတွက်ခိုင်းတာပါဒါပါပဲ။

ဒီ question ကို rust လုပ်ဖြစ်နေတော့ rust နဲ့ solve ထားပါတယ်။ ဒါပေမယ့် Python solution ကိုလဲအောက်မှာပေးထားပါတယ်။

Thought process

medium ဆိုပေမယ့်ဒီ question ကတကယ်တော့မခက်ပါဘူး။ လုပ်ရမှာက land တစ်ခုကို iterate လုပ်ပြီဆိုသူနဲ့ဆက်စပ်တဲ့ land တွေကိုပဲနောက်တစ်ခု visit မလုပ်အောင်လုပ်ရုံပါပဲ။ အပေါ်ကဥပမာကိုကြည့်ရင် grid[0][0] ရောက်ရင်သူ့ neighbors တွေကိုပါ visit လုပ်ပေးရမှာဒါပါပဲ။

ဆိုတော့သူ့ရဲ့ direction လေးမျက်နှာလုံးကိုကြည့်မယ်၊ ရေမဟုတ်ဘူးဆိုရင် visit လုပ်မယ်နောက် visit လုပ်သမျှကောင်တွေအကုန်လုံးကိုသိမ်းမယ်ဒါပါပဲ။ ဒါကိုကြည့်ခြင်းအားဖြင့် question က graph traversal question ဆိုတာသဘောပေါက်မိမှာပါ။ Graph traverse လုပ်ရင်၂မျိုးရှိမယ်။ DFS (depth first search) or BFS (breadth first search) ဒီမှာတော့၂ခုထဲကဘာသုံးသုံးအဆင်ပြေတယ်။

Regarding Graph Interview Questions
Graph question မြင်ရင်ခေါင်းထဲတန်း၀င်လာသင့်တာ၃ခုပဲရှိတယ်များသောအားဖြင့်က Breadth first search, Depth first search, and Topological sort. Interview မှာ question အများစုကဒါပဲ။
Niche ဖြစ်တဲ့ question တွေတော့ရှိသေးတယ်၊ ဒါပေမယ့်တော်ရုံတန်ရုံမေးလေ့မေးထမရှိဘူး။ ကိုယ်လုပ်ရမယ် job position က graph နဲ့တိုက်ရိုက်ဆက်စပ်တာဆိုရင်တော့မေးတတ်တယ်။ ဥပမာ self driving car company တစ်ခုမှာသူ့တို့ကားတွေအတွက် GPS data build လုပ်တဲ့ team မျိုး join မယ်ဆိုပါစို့အဲ့တာဆို Graph ကိုအပေါ်ကထက်နဲနဲပို niche ဖြစ်တဲ့ algorithm မျိုးတွေမေးကောင်းမေးလိမ့်မယ်။ ဥပမာ Dijkstra တို့ A* algorithm တို့။

Edge cases

edge case က traverse တဲ့အခါ out of bound check တာသတိထားဖို့ပဲလိုတယ်၊ တခြားတော့ဘာမှထွေထွေထူးထူးသတိထားစရာမရှိဘူး။

Solution

ပေးထားတာကတော့အောက်ကလိုပါပဲ။

impl Solution {
    pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
        
    }
}

အဲ့တော့ solution ကပေးတဲ့ graph ကိုကြည့်မယ်၊ island ဘယ်နှခုရှိလဲတွက်ပြီး interger return ပြန်ရမယ်။ ဒီ question ကိုတော့ DFS iterative နဲ့ပဲ solve မယ်။ အဲ့တော့ variable ကတကယ်လိုတာ၂ခုပဲလိုမယ်။

1. number of islands: ဒါကရှင်းတယ်၊ interger ပဲ။
2. visited cells: ဒါကိုက grid ကို flatten လုပ်လိုက်ပြီး array အနေနဲ့သိမ်းမယ်၊ visit လုပ်လိုက်တဲ့ cell ဆို boolean/int 1 လို့သပ်မှတ်မယ်မဟုတ်ရင် 0၊ ဘာလို့ visited သိမ်းဖို့လိုလဲဆိုသူ့ဆက်စပ်တာတွေကိုလိုက် visit ပြီးတိုင်းမှတ်ထားမှမဟုတ်ရင်ပြန် visit မိပြီး island count တွက်တဲ့အချိန်မှာမှားလိမ့်မယ်။

...
    pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
        let R = grid.len();
        let C = grid[0].len();

        let mut islands = 0;
        
        // create R * C length array with 0s
        let mut visited = vec![0; R * C];
        
        for i in 0..R {
            for j in 0..C {
                if grid[i][j] == '1' && visited[i * C + j] == 0 {
                    islands += 1;
                    
                    // the code below is incomplete for now
                    Solution::dfs();
                }
            }
        }
        
        /*
          In rust, you can just write `islands` instead of `return islands;`
           but I chose the latter for people who are not familiar in rust.
        */
        return islands;
    }
...

ရှင်းပါတယ်။ Cell တစ်ခုချင်းစီကို visit ဘယ်အဲ့မှာ island ဖြစ်ပြီး visit မလုပ်ရသေးတယ်၊ visited က 0 ဖြစ်မယ်အဲ့တာဆို island count ကို၁တိုးပြီး DFS လုပ်မယ်။ DFS ထဲမှာက island တစ်ခုလုံးကိုလိုက် visit လုပ်မယ်ပြီးတော့ visit လုပ်လိုက်တဲ့ cell တွေကို visited ဆိုတဲ့ variable ထဲမှာမှတ်မယ်။

ဆိုတော့ DFS function ကိုဆက်ရေးမယ်။ DFS လုပ်မယ်ဆိုအမြဲတမ်း end condition ကိုစစဥ်းစားတာကောင်းတယ်။ ဘယ်အချိန်မှာ traverse တာရပ်မလဲပေါ့။ အခု question မှာကရပ်မမယ့် condition ၃ခုရှိတယ်။

1. row ဖြစ်ဖြစ် column ဖြစ်ဖြစ်က out of bound ဖြစ်သွားရင်
2. visited လုပ်ပြီးသားဆိုရင်
3. land မဟုတ်တော့ရင်

နောက်ပြီး visit ရမယ့် condition ကလေးခုရှိတယ်။ up/down/left/right

ဒါတွေသဘောပေါက်ပြီးဆို code ကိုကြည့်မယ်။

...
    fn dfs(visited: &mut Vec<i32>, grid: &Vec<Vec<char>>, i: usize, j: usize) {
        let (R, C) = (grid.len(), grid[0].len());
        
        // check if out of bound or visited
        if i >= R || j >= C || visited[i * C + j] != 0 || grid[i][j] == '0' {
            return;
        }
        
        // set visited as 1
        visited[i * C + j] = 1;
        
        // visit top, down, left, right
        Solution::dfs(visited, grid, i + 1, j);
        Solution::dfs(visited, grid, i - 1, j);
        Solution::dfs(visited, grid, i, j + 1);
        Solution::dfs(visited, grid, i, j - 1);
    }
...

function မှာက parameter ၄ခုရှိမယ်။ Visited နောက် original grid ပြီးတော့ visit တဲ့ position (i, j). အဲ့မှာ out of bound အပေါ်ကပြောခဲ့တဲ့ end condition ၃ခုဖြစ်မဖြစ်ကြည့်မယ် မဖြစ်ရင် visit လုပ်ပြီးကြောင်း update လုပ်မယ်ပြီးရင်သူ့ဘေးက neighboring cells တွေကို visit လုပ်မယ်။

ဆိုတော့အပေါ်က incomplete ဖြစ်နေတဲ့ function call ကိုလဲပြန်သွားပြင်မယ်။

...
        for i in 0..R {
            for j in 0..C {
                if grid[i][j] == '1' && visited[i * C + j] == 0 {
                    islands += 1;
                    Solution::dfs(&mut visited, &grid, i, j);
                }
            }
        }
...

Time complexity က MxN ဖြစ်မယ်ဘာလို့လဲဆို cell အကုန် visit ရလို့နောက် Space complexity ကတော့ 2(MxN) ဒါက rust မှာမို့လို့၊ rust မှာသူက grid ကို immutable အနေနဲ့ pass ထားတော့ visited ကိုသပ်သပ်သိမ်းနေရတာမဟုတ်ရင် MxN ပဲ။ Python နဲ့ဆိုရင်တော့အောက်ကလိုပါပဲ။

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        self.grid = grid
        self.R = len(grid)
        self.C = len(grid[0])

        islands = 0
        
        for r in range(self.R):
            for c in range(self.C):
                if self.grid[r][c] == "1":
                    islands += 1
                    self.dfs(r, c)
        
        return islands
 
    def dfs(self, r, c):
        if r < 0 or r >= self.R:
            return
        
        if c < 0 or c >= self.C:
            return
        
        if self.grid[r][c] == "0":
            return
        
        self.grid[r][c] = "0"
        
        # go left right up down
        self.dfs(r + 1, c)
        self.dfs(r - 1, c)
        self.dfs(r, c + 1)
        self.dfs(r, c - 1)
        
        return