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 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 , the total time complexity of this approach would be .

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 .

Categories: PROBLEM SOLVING

Tags: algorithms, Binary Search, Breadth First Search, Depth First Search, Leetcode, problem solving