Max Area Of Island


  • 1

    Click here to see the full article post


  • 0
    L

    No need to have 'seen' set to keep track of visited squares... if immutability of input grid is not important


  • 0
    R

    Agree with @lulutao. The seen array is not necessary.


  • 0
    P

    'seen' can help us to determine whether the location has been calculated.


  • 0
    R

    That's irrelevant information for this specific problem.


  • 0
    P

    @rliu054 In this problem you are right. I thought is the other problem that if input is array of boolean. And we can use 'seen' to get the result in shorter time.


  • 0
    P

    @passeraha array of boolean also can sort without 'seen' .


  • 0
    D

    write a program C #


  • 0
    G

    agree with @lulutao, seen is not necessary


  • 0
    P

    why + 1 in approach 1, Java, area method/????


  • 0
    L

    Very clean solution!

    Keep a separate place to track if a cell is visited or not is a good habit, as usually your input should maintain read-only.


  • 0
    P

    What do you my way of doing it then?
    Iterative + Recursive = Itecursive? Hehe. Check it out.

    class Solution(object):
    def maxAreaOfIsland(self, grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    seen_dict = {}

        def findmaxarea(rindex, eindex):
            # if current element at grid[rindex,eindex] is 1 so we start looking in all 4 directions from this point
            
            if rindex<0 or eindex <0:
                return 0
            
            if rindex >= len(grid):
                return 0
    
            if eindex >= len(grid[rindex]):
                return 0
    
            if grid[rindex][eindex] == 1:
                if (rindex,eindex) in seen_dict:
                    return 0
                else:
                    seen_dict[(rindex,eindex)] = 1
                return findmaxarea(rindex, eindex + 1) + findmaxarea(rindex, eindex - 1) + findmaxarea(rindex - 1, eindex) + findmaxarea(rindex + 1, eindex) + 1
            else:
                return 0
    
        max_area = 0
        for row_index, row in enumerate(grid):
            for element_index, element in enumerate(row):
                if element == 1:
                    if (row_index,element_index) not in seen_dict:
                        cmax = findmaxarea(row_index, element_index)
                        if cmax > max_area:
                            max_area = cmax
        
        return max_area

Log in to reply
 

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