Why the tag is "Hash Table"? Is there a hash table solution?


  • 11
    B

    Why the tag is "Hash Table"? Is there a hash table solution?


  • 2
    P

    Yes, there exist a hash table solution. Though I think it's not fast or elegant. The time complexity should be O(N*M). My idea is using a hash table to record which lines we already found on the islands. If a new line is not in the hash table, then add it into the hash table. If it's already in the hash table, then it cannot be a perimeter, as it is shared by two islands. Then just remove it from the hash table (since one line can only associated with one or two islands in this problem setting). Finally just return the length of the hash table should work.

    The advantage of this solution is that it do not use recursion and is quite easy to code.


  • 0

    Stack(Hash Table)Solution:
    The idea is all islands are connected together.
    So you can find first one. you can get all by checking it's neighborhood

    It's not a good solution for this.
    But would become the better solution when water area is much bigger than island.

    public class Solution {
        public int IslandPerimeter(int[,] grid) {
            int borders=0;
            int[] firstblock=getFirstBlock(grid);
            int row=firstblock[0];
            int col=firstblock[1];
            if(row!=-1)
            {
                List<int[]> ops=new List<int[]>();
                ops.Add(new int[]{1,0});
                ops.Add(new int[]{-1,0});
                ops.Add(new int[]{0,1});
                ops.Add(new int[]{0,-1});
                Stack<int[]> checkPoints=new Stack<int[]>();
                checkPoints.Push(new int[]{row,col});
                grid[row, col] = -1;
                while(checkPoints.Count>0)
                {
                    borders+=4;
                    int[] cur=checkPoints.Pop();
                    for(int i=0;i<ops.Count;i++)
                    {
                        if( cur[0]+ops[i][0]>=0 
                            && cur[0]+ops[i][0]<grid.GetLength(0) 
                            && cur[1]+ops[i][1]>=0 
                            && cur[1]+ops[i][1]<grid.GetLength(1)
                            )
                        {
                            if(grid[cur[0]+ops[i][0], cur[1]+ops[i][1]]==1)
                            {
                                checkPoints.Push(new int[]{cur[0]+ops[i][0], cur[1]+ops[i][1]});
                                grid[cur[0]+ops[i][0], cur[1]+ops[i][1]] = -1;
                            }
                            if(grid[cur[0]+ops[i][0], cur[1]+ops[i][1]]!=0)
                            {
                                borders-=1;
                            }
                        }
                    }
                }
            }
            return borders;
        }
        
        public int[] getFirstBlock(int[,] grid)
        {
            int[] rs={-1,-1};
            for(int i=0;i<grid.GetLength(0);i++)
            {
                for(int j=0;j<grid.GetLength(1);j++)
                {
                    if(grid[i,j]==1)
                    {
                        rs[0]=i;
                        rs[1]=j;
                        return rs;
                    }
                }
            }
            return rs;
        }
    }

  • 0
    S

    @Vick.Chen

    This is just non-recursive DFS. How is this a hash table solution.


  • 0
    C

    my hashtable method is to to create a hashtable(or an array) which key is the neighbors of an island and the value is the number of such islands, then I scan the key to obtain the answer.

        int[][] dirs = new int[][]{{1,0},{0,1},{0,-1},{-1,0}};
        public int islandPerimeter(int[][] grid) {
            int[] map = new int[5];
            int res = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 0) continue;
                    int num = calculate(grid, i, j);
                    res +=  4 - num;
                }
            }
            return res;
        }
        private int calculate(int[][] grid, int i, int j) {
            int nums = 0;
            for (int[] dir : dirs) {
                int x = dir[0] + i;
                int y = dir[1] + j;
                if (!inBound(x, y, grid)) continue;
                if (grid[x][y] == 1) nums++;
            }
            return nums;
        }
        private boolean inBound(int x, int y, int[][] grid) {
            return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
        }
    }

  • 0
    G

    I used a hashset to keep track of which island cells I have already visited. This uses O(N) space though.

    class Solution(object):
        def islandPerimeter(self, grid):
            visited = set()
            
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] == 1:
                        return self.helper(grid, i, j, visited)
        
            return 0
    
        def helper(self, grid, i, j, visited):
            if (i, j) in visited:
                return 0
            
            if i < 0 or i > len(grid) - 1 or j < 0 or j > len(grid[0]) - 1 or grid[i][j] == 0:
                return 1
            
            visited.add((i, j))
            return self.helper(grid, i + 1, j, visited) + self.helper(grid, i - 1, j, visited) + self.helper(grid, i, j + 1, visited) + self.helper(grid, i, j - 1, visited)
    

Log in to reply
 

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