Easy Java O(1) space, O(mn) time complexity Solution


  • 1
    S

    2 pass approach:

    1. Each 1 makes 4 perimeters. count total 1s, multiply by 4
    2. each adjacent 1 removes 2 perimeter, find total adjacents
      Total perimeter = (total 1s * 4) - (total adjacents * 2)
    public class Solution {
        public int islandPerimeter(int[][] grid) {
            // count total 1s
            int ones = 0;
            int adj = 0;
            for(int i = 0; i < grid.length; i++)
                for(int j = 0; j < grid[0].length; j++) {
                    if(j > 0 && grid[i][j] == grid[i][j-1] && grid[i][j]==1) adj++; // count row adjacent
                    if(grid[i][j] == 1) ones++;
                }
            
            // count column adjacents
            for(int j = 0; j < grid[0].length; j++) 
                for(int i = 0; i < grid.length; i++)
                    if(i > 0 && grid[i][j] == grid[i-1][j] && grid[i][j]==1) adj++;
                    
            return ((ones * 4) - (adj *2));
        }
    }
    

  • 0
    C

    Obviously, It's not O(1),but O(m*n).


  • 0
    S

    @ciaoliang1992 My apology, it is O(1) space, O(m *n) time complexity, I submitted too soon without fixing my title. Sorry for the inconvenience


Log in to reply
 

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