Java O(n) Easy To Understand Solution


  • 0
    B

    Explanation

    For this question, we simply have to compute the cell perimeter for each land cell, and record the total cell perimeter sum.

    In computeCellPerimeter(...), we increment the cell's perimeter if an adjacent cell is either out of bounds, which means it's bordering water, or explicitly next to a water cell.

    Time Complexity
    The time complexity is O(n) where n is the number of total cells in our input grid, since our two for loops help us iterate through each cell once, while the running time of computeCellPerimeter(...) is in constant time.

    class Solution {
        public int computeCellPerimeter(int[][] grid, int row, int col) {
            int result = 0;
            
            // Check if the left adjacent cell is out of bounds or is water
            if (col == 0 || grid[row][col - 1] == 0) {
                result++;
            }
            // Check if the right adjacent cell is out of bounds or is water
            if (col == grid[0].length - 1 || grid[row][col + 1] == 0) {
                result++;
            }
            // Check if the above adjacent cell is out of bounds or is water
            if (row == 0 || grid[row - 1][col] == 0) {
                result++;
            }
            // Check if the below adjacent cell is out of bounds or is water
            if (row == grid.length - 1 || grid[row + 1][col] == 0) {
                result++;
            }
            return result;
        }
        
        public int islandPerimeter(int[][] grid) {
            int result = 0;
            // Iterate through all cells within our grid for land cells
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    // Compute perimeter for land cell
                    if (grid[i][j] == 1) {
                        result += computeCellPerimeter(grid, i, j);
                    }
                }
            }   
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.