LeetCode 200: Number of Islands

class Solution {

    /**
     * @param String[][] $grid
     * @return Integer
     */
    function numIslands($grid) {
        $count = 0;
        
        for ($i=0; $i<count($grid); $i++) {
            for ($j=0; $j<count($grid[$i]); $j++) {
                if ($grid[$i][$j] == "1") {
                    $count++;
                    // zero out rest of 1s
                    $this->zeroOut($grid, $i, $j);
                }
            }
        }
        
        return $count;
    }
    
    function zeroOut(&$grid, $i, $j) {
        if ($i<0 || $i>=count($grid) || $j<0 || $j>=count($grid[$i]) || $grid[$i][$j] == "0")
            return;
        
        $grid[$i][$j] = "0";
        
        $this->zeroOut($grid, $i-1, $j);
        $this->zeroOut($grid, $i+1, $j);
        $this->zeroOut($grid, $i, $j-1);
        $this->zeroOut($grid, $i, $j+1);
    }
}

I had to watch some YouTube videos for solution. Initially, I was creating over-complicated solutions to track islands.

Ref: https://leetcode.com/problems/number-of-islands/

Leave a Reply

Your email address will not be published. Required fields are marked *