Java Intuitive Solution Using Hash Table


  • 0
    U

    In order to calculate the perimeter, we only care about the element whose content is 1. For the element whose content is 1, there are five cases considering the number of its adjacent 1's:

    case 1: 0 adjacent 1's
    case 2: 1 adjacent 1's
    case 3: 2 adjacent 1's
    case 4: 3 adjacent 1's
    case 5: 4 adjacent 1's

    For each case, the corresponding number of valid edges are 4, 3, 2, 1, 0, so that we can create the hash table for later look up based on the number of adjacent 1's of each element whose content is 1. Then we iterate the matrix, and tally the number of valid edges (hash table look up) as soon as the content is 1.

    class Solution {
        public int islandPerimeter(int[][] grid) {
            int perimeter = 0;
            // four possible values (# of valid edges) for the cell: 0, 1, 2, 3, 4
            // the number of adjacent 1's decides the value
            // key is the number of adjacent 1's and value is the corresponding number of valid edges
            Map<Integer, Integer> edge = new HashMap<Integer, Integer>();
            edge.put(0, 4);
            edge.put(1, 3);
            edge.put(2, 2);
            edge.put(3, 1);
            edge.put(4, 0);
            
            // iterate the matrix and find the number of adjacent 1's for each 1
            int r = grid.length, c = grid[0].length;
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    
                    // found a 1
                    if (grid[i][j] == 1) {
                        int numOfAdjacentOnes = 0;
                        if (i - 1 >= 0 && grid[i - 1][j] == 1) { // up
                            numOfAdjacentOnes++;
                        }
                        if (i + 1 < r && grid[i + 1][j] == 1) { // down
                            numOfAdjacentOnes++;
                        }
                        if (j - 1 >= 0 && grid[i][j - 1] == 1) { // left
                            numOfAdjacentOnes++;
                        }
                        if (j + 1 < c && grid[i][j + 1] == 1) { //right
                            numOfAdjacentOnes++;
                        }
                        perimeter += edge.get(numOfAdjacentOnes);
                    }
                    
                }
            }
            return perimeter;
            
        }
    }
    

Log in to reply
 

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