Stokastik

Machine Learning, AI and Programming

LeetCode : Swim in Rising Water

Problem Statement

Solution :

One possible solution is to see whether for each water level, he can swim from (0, 0) to (N-1, N-1) without waiting anywhere in between. To check whether he can swim from (0, 0) to (N-1, N-1) i.e. there exists a path, we can use DFS or BFS to traverse the matrix. He can swim from point A to B if the height of B is less than equals to the current level of water. Below is the python function, that returns whether he can swim from A to B, for level of water equals to 'curr_height', using DFS. The variable 'visited' tracks whether he has already visited a point in the matrix.

class Solution(object):

    def get_flag(self, grid, curr_height, start, end, visited):
        a = 0 <= start[0] < len(grid) and 0 <= start[1] < len(grid)
        b = 0 <= end[0] < len(grid) and 0 <= end[1] < len(grid)

        if a and b and grid[end[0]][end[1]] <= curr_height and end not in visited:
            return self.traverse(grid, curr_height, end, visited)

        return False


    def traverse(self, grid, curr_height, start, visited):
        if start == (len(grid) - 1, len(grid) - 1):
            return True

        else:
            visited.add(start)

            flag = False

            flag = flag or self.get_flag(grid, curr_height, start, (start[0] - 1, start[1]), visited)
            flag = flag or self.get_flag(grid, curr_height, start, (start[0], start[1] - 1), visited)
            flag = flag or self.get_flag(grid, curr_height, start, (start[0] + 1, start[1]), visited)
            flag = flag or self.get_flag(grid, curr_height, start, (start[0], start[1] + 1), visited)

            return flag

The method 'get_flag' checks whether if it is possible to go from point (x, y) to either (x - 1, y) or (x, y - 1) or (x + 1, y) or (x, y + 1) in the grid.

The time complexity for DFS is O(N^2) since I need to visit each point in the grid at-least once to check whether we can traverse to (N-1, N-1) from that point.

Since I am doing DFS for each water level and the different possible water level is N^2, the total time complexity of this approach would be O(N^4).

But we can do better by noticing that, instead of doing linear search over the water levels, we can do binary search, because, if the swimmer cannot cross the grid for water level X, then he cannot cross the grid for any water level greater than X.

The full code is as follows :

class Solution(object):
    def get_flag(self, grid, curr_height, start, end, visited):
        a = 0 <= start[0] < len(grid) and 0 <= start[1] < len(grid)
        b = 0 <= end[0] < len(grid) and 0 <= end[1] < len(grid)

        if a and b and grid[end[0]][end[1]] <= curr_height and end not in visited:
            return self.traverse(grid, curr_height, end, visited)

        return False


    def traverse(self, grid, curr_height, start, visited):
        if start == (len(grid) - 1, len(grid) - 1):
            return True

        else:
            visited.add(start)

            flag = False

            flag = flag or self.get_flag(grid, curr_height, start, (start[0] - 1, start[1]), visited)
            flag = flag or self.get_flag(grid, curr_height, start, (start[0], start[1] - 1), visited)
            flag = flag or self.get_flag(grid, curr_height, start, (start[0] + 1, start[1]), visited)
            flag = flag or self.get_flag(grid, curr_height, start, (start[0], start[1] + 1), visited)

            return flag


    def can_swim(self, grid, curr_height):
        if grid[0][0] > curr_height or grid[len(grid) - 1][len(grid) - 1] > curr_height:
            return False

        visited = set()
        return self.traverse(grid, curr_height, (0,0), visited)


    def swimInWater(self, grid):
        n = len(grid)
        left, right = 0, n*n - 1

        while left <= right:
            curr_height = int((left + right) / 2)

            if self.can_swim(grid, curr_height):
                right = curr_height - 1
            else:
                left = curr_height + 1

        return left

The time complexity for the above code is O(N^2*logN).

Categories: PROBLEM SOLVING

Tags: , , , , ,