C++ O(2mn) time O(1) space solution


  • 0
    A

    I guess the usual method should be checking 4 neighbors for every island cell, but we can do it in another way.
    Simply traverse the grid horizontally once without looking out for neighbors, then traverse the grid vertically once without looking out for neighbors. The total cells accessed are 2*width*height, each cell twice exactly.

    5833 / 5833 test cases passed
    Status: Accepted
    Runtime: 122 ms

    class Solution {
    public:
        int islandPerimeter(vector<vector<int>>& grid) {
            uint p = 0, h = grid.size(), w = h ? grid[0].size() : 0;
            for (uint i = 0; i < h; i++) {
                for (uint j = 0, last = 0; j < w; j++) {
                    if (grid[i][j]) {
                        if (!last) { p += 2; last = 1; }
                    } else last = 0;
                }
            }
            for (uint j = 0; j < w; j++) {
                for (uint i = 0, last = 0; i < h; i++) {
                    if (grid[i][j]) {
                        if (!last) { p += 2; last = 1; }
                    } else last = 0;
                }
            }
            return p;
        }
    };
    

Log in to reply
 

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