leetcode/src/L200.java at master · prabhakar97/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution200 {
    class Solution {
        /**
         * 200. Number of Islands https://leetcode.com/problems/number-of-islands/description/
         *
         * @param grid Input character matrix
         * @return
         * @timeComplexity O(m * n) Each position is examined once
         * @spaceComplexity O(m * n) We mutate the input grid, proportional to number of ones.
         */
        public int numIslands(char[][] grid) {
            int count = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == '1') {
                        flood(grid, i, j);
                        count++;
                    }
                }
            }
            return count;
        }

        private void flood(char[][] grid, int i, int j) {
            if (grid[i][j] == '1') {
                // Mark flooded
                grid[i][j] = '0';
                if (i > 0) {
                    flood(grid, i - 1, j);
                }
                if (i < grid.length - 1) {
                    flood(grid, i + 1, j);
                }
                if (j > 0) {
                    flood(grid, i, j - 1);
                }
                if (j < grid[0].length - 1) {
                    flood(grid, i, j + 1);
                }
            }
        }
    }
}