Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example:

Input:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Output: 16

Explanation: The perimeter is the 16 yellow stripes in the image below:
 class Solution {
    public int islandPerimeter(int[][] grid) {
        int lands = 0, neighbours = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    lands++;
                    if (i < grid.length - 1 && grid[i + 1][j] == 1) neighbours++;  //step 2
                    if (j < grid[i].length - 1 && grid[i][j + 1] == 1) neighbours++; //step3
                }
            }
        }

        return lands * 4 - neighbours * 2;
    }
}


Here, we are going to solve using normal matrix traversal.
1) If 1 is found, then that cell must be a land and increase land count.
2) Step 2 in code is to check for any lands in down (i.e., neighbours)
3) Step 3 in code is to check for any lands in right(i.e., neighbours)
4) Finally return lands*4 - neighbours*2.  This is pattern hidden in image in problem description. since every adjacent lands made two sides disappeared (Just compare with above image).

Example
Consider there are two lands, then total perimeter is 8. Now assume if both are adjacent, then total perimeter is 6. This is reason behind for making the return result formula.

Related Post:

Click here for April month challenges with solution and explanation

Click Follow button to receive latest updates from us instantly.

Please let us know about your views in comment section.

Help Others, Please Share..!!!!
                                                     😍..Happy Coding...😍
The intention behind this blog is to help all my fellow programmers. Also to provide solutions for various coding platform problems with solution and explanation. I will add many tutorials in future. I am not a professional blogger but whenever time permits I will post. I hope you’ll enjoy the content and find it useful! Check out my Writer blog for a more valuable quotes. For any queries or suggestions, please feel free to reach out to me. Happy coding!

Comments

  1. Amrendra Yadav7 July 2020 at 15:04

    Nice and concise, My mistake i started solving using brute force. I need to think in terms of generalizing the prob statement. Thanks!!

    ReplyDelete
    Replies
    1. Fellow Programmer8 July 2020 at 08:24

      Thank You Amrendra Yadav for encouraging us by your wonderful feedback. This will motive us to achieve more. Whatever problem, first check is there any pattern hidden in problem, so that you can complete it in more concise solution. Please do follow us to receive latest updates instantly and keep supporting. Happy Coding...!!!

      Delete
  2. Anonymous8 July 2020 at 23:05

    Can you help me understand this `The island doesn't have "lakes"` this is something I haven't go it yet. what does this means

    because with the given input
    [[1,0,0,0],[0,0,0,0],[0,0,0,0],[1,1,1,1]]
    the expected result does not matched the output

    ReplyDelete
    Replies
    1. Fellow Programmer9 July 2020 at 12:17

      Thanks for posting your doubt. The island doesn't have lakes means that if you are forming island but inside there is one cell with water (which means island having lakes). According to problem island should be completely connected and surrounded by water, also within island there should be no water cells. Please do follow us to receive latest updates from us instantly.

      Delete

Post a Comment

Popular posts from this blog

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of  every  node differ in height by no more than 1. Example 1: Input: root = [3,9,20,null,null,15,7] Output: true Example 2: Input: root = [1,2,2,3,3,null,null,4,4] Output: false Example 3: Input: root = [] Output: true   Constraints: The number of nodes in the tree is in the range  [0, 5000] . -10 4  <= Node.val <= 10 4 Solution: /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeNode right) {  *         this.val = val;  *         this.left = left;  *         this.right = right;  *     }
Read more

First Unique Character in a String

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1. Examples: s = "leetcode" return 0. s = "loveleetcode", return 2. Note: You may assume the string contain only lowercase letters. class Solution {     public int firstUniqChar(String s) {         int length = s.length();         String str;         for(int i=0;i<length;i++){             if(i==length-1){                 str = s.substring(0, i);             }             else{                 str = s.substring(0,i)+s.substring(i+1);             }             if(!str.contains(s.charAt(i)+""))                 return i;         }         return -1;     } } Try it on Leetcode Here, we are going to use substring method. 1) If character is at end, then take substring from 0 till before last character of string. 2) Else make a temporary string, by removing exactly that particular character using index. [e.g..
Read more

Majority Element

Given an array of size n , find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1,1,2,2] Output: 2   class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } } Here, we are sorting the entire array using sort() of Arrays class. Then, number at index position n/2 would be a majority element. There is no chance of wrong values in odd or even length.   Below is another method using HashMap. METHOD 2: class Solution { public int majorityElement(int[] nums) { HashMap<Integer, Integer>list = new HashMap<Integer, Integer>(); int repeatLen
Read more

Smallest Range II

Given an array   A   of integers, for each integer   A[i]   we need to choose   either  x = -K  or  x = K , and add   x   to   A[i]  (only once) . After this process, we have some array  B . Return the smallest possible difference between the maximum value of  B  and the minimum value of  B . Example 1: Input: A = [1] , K = 0 Output: 0 Explanation : B = [1] Example 2: Input: A = [0,10] , K = 2 Output: 6 Explanation : B = [2,8] Example 3: Input: A = [1,3,6] , K = 3 Output: 3 Explanation : B = [4,6,3] Note: 1 <= A.length <= 10000 0 <= A[i] <= 10000 0 <= K <= 10000 Solution: class Solution {     public int smallestRangeII(int[] A, int K) {         int i, min=0, max=0, min1, min2, max1, max2, length = A.length, diff
Read more