# 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:

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:

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