1
class Solution {
2
  public int swimInWater(int[][] grid) {
3
    int len = grid.length;
4
    Map<Integer, int[]> reverseMap = new HashMap<>();
5
    for (int i = 0; i < len; i++) {
6
      for (int j = 0; j < len; j++) {
7
        reverseMap.put(grid[i][j], new int[] {i, j});
8
      }
9
    }
10

11
    int left = grid[0][0]; // answer cannot be less than value of starting position
12
    int right = len * len - 1;
13

14
    int ans = right;
15

16
    while (left <= right) {
17
      int mid = left + (right - left) / 2;
18
      if (canSwim(grid, reverseMap, mid, len)) {
19
        ans = mid;
20
        right = mid - 1;
21
      } else {
22
        left = mid + 1;
23
      }
24
    }
25

26
    return ans;
27
  }
28

29
  boolean canSwim(int[][] grid, Map<Integer, int[]> reverseIndex, int ans, int len) {
30
    int[] x_diff = {1, -1, 0, 0};
31
    int[] y_diff = {0, 0, 1, -1};
32

33
    // BFS
34
    Queue<int[]> container = new LinkedList<>();
35
    container.add(new int[] {0, 0});
36

37
    boolean[][] visited = new boolean[grid.length][grid[0].length];
38
    visited[0][0] = true;
39

40
    while (!container.isEmpty()) {
41
      int[] curr = container.poll();
42
      int currVal = grid[curr[0]][curr[1]];
43
      for (int i = 0; i < 4; i++) {
44
        int newX = curr[0] + x_diff[i];
45
        int newY = curr[1] + y_diff[i];
46
        if (isValidCell(grid, newX, newY, ans) && !visited[newX][newY]) {
47
          if (newX == grid.length - 1 && newY == grid[0].length - 1) {
48
            return true;
49
          }
50
          visited[newX][newY] = true;
51
          container.add(new int[] {newX, newY});
52
        }
53
      }
54
    }
55

56
    return false;
57
  }
58

59
  boolean isValidCell(int[][] grid, int x, int y, int ans) {
60
    // check boundary and if grid elevation is greater than evaluated answer
61
    return !(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] > ans);
62
  }
63
}