[LeetCode] Solving Iterative, Right and Bottom cells, DFS with Island Perimeter issue

Account Login - LeetCode

We can refer the solution in this link: https://leetcode.com/explore/challenge/card/july-leetcoding-challenge/544/week-1-july-1st-july-7th/3383/discuss/776406/3-Solutions-or-Simple-Iterate-or-Check-Right-and-Bottom-Cells-or-DFS

Let’s get started with the 2 first solutions

Basically, 2 above solutions the same it is just different in moving left, right, up, down steps

The main idea both of those solutions is:

We will loop through the 2D array, and when we found a number 1, automatically we will default it is an island and increase the perimeter + 4

look at the above image

After + 4 for perimeter of each grid[i][j]

move to the next step:

First Solution

Second Solution

First Solution, we will check the 4 sides of a cell: top, right, bottom, left and in each If condition we want to assure that we can avoid array index out of bound

The perimeter will minus 1 if the value of the grid at this position is 1 and

minus 0 if the value of the grid at this position is 0

With this First Solution, we can easy to understand this idea.

Let’s move on Second Solution, we call this approach is Right and Bottom cells

Second Solution

We just have 2 If conditions instead of 4,

The reason we have to multiply 2 is

because the border will not be used in both cells.

Solution 3

Basically DFS using a recursive way to approach

so we can easy to see that the method getPerimeter is called again a lot.

in this solution, we still using 2 For loop, the main difference comes from using a new method getPerimeter() as a recursive method to replace the if condition to move left or right, up or down like the previous solution.

Focusing on getPerimeter() method, we will transfer 3 parameters: the array and index of 2 axis

The idea also the same just different in assign grid[i][j] = -1 for the visited cell, this step also means that when we meet the land the perimeter will plus 0

To calculate the perimeter we use the recursive to move to 4 directions by changing the 2 axis index.

Conclusion, I think through this topic we can have a better understanding of the Iterative and Recursive approach.

So that all for this topic. Hope that you can learn some new things from my sharing. Enjoy and Keep Learning!