Problem statement

You are given an n x n grid where grid[i][j] is the elevation of that square. Rain raises the water level: at time t the water depth everywhere is t.

You start at the top-left square and may swim to any adjacent square (up, down, left or right) as long as both squares have elevation at most t. Swimming itself takes no time. Return the least time at which you can reach the bottom-right square.

Example 1

Input: grid = [[0,2],[1,3]]
Output: 3

Example 2

Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16

Example 3

Input: grid = [[0]]
Output: 0

Constraints

• 1 <= grid.length <= 8
• grid[i].length == grid.length
• grid holds a permutation of 0 … n² - 1.

Follow-up: Binary search on the time gives O(n² log n). A Dijkstra variant that minimises the maximum elevation on the path is the classic alternative.

Hints for Swim in Rising Water

1. Hint 1

   Ask the yes/no question first: at time t, can you reach the corner using only squares with elevation at most t?

2. Hint 2

   That is a plain flood fill, and the answer is monotone in t — so binary search it.

3. Hint 3

   The answer can never be below either corner's elevation, which gives a tight lower bound to start from.

How to solve Swim in Rising Water

Binary search the time: at time t the corner is reachable iff a flood fill through squares with elevation ≤ t reaches it.

Approach

1. lo = max(corner elevations), hi = n² - 1.
2. Bisect with a DFS reachability test.
3. Return lo.

Why it works

Reachability is monotone in t, and elevations are distinct values in 0..n²-1, so bisection over that range finds the minimum feasible time in O(log n²) tests.

Complexity

• Time — O(n² log n)
• Space — O(n²)

Pitfalls

• A Dijkstra/priority-queue walk minimising the path maximum is the alternative.

Reference solution

Python

def swimInWater(grid) -> int:
    n = len(grid)

    def reachable(limit):
        if grid[0][0] > limit:
            return False
        seen = [[False] * n for _ in range(n)]
        seen[0][0] = True
        stack = [(0, 0)]
        while stack:
            r, c = stack.pop()
            if r == n - 1 and c == n - 1:
                return True
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= limit:
                    seen[nr][nc] = True
                    stack.append((nr, nc))
        return seen[n - 1][n - 1]

    lo = max(grid[0][0], grid[n - 1][n - 1])
    hi = n * n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if reachable(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Java

private static boolean swimReachable(int[][] grid, int limit) {
    int n = grid.length;
    if (grid[0][0] > limit) return false;
    boolean[][] seen = new boolean[n][n];
    seen[0][0] = true;
    Deque<int[]> stack = new ArrayDeque<>();
    stack.push(new int[]{0, 0});
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    while (!stack.isEmpty()) {
        int[] cell = stack.pop();
        if (cell[0] == n - 1 && cell[1] == n - 1) return true;
        for (int d = 0; d < 4; d++) {
            int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n || seen[nr][nc]) continue;
            if (grid[nr][nc] > limit) continue;
            seen[nr][nc] = true;
            stack.push(new int[]{nr, nc});
        }
    }
    return seen[n - 1][n - 1];
}

public static int swimInWater(int[][] grid) {
    int n = grid.length;
    int lo = Math.max(grid[0][0], grid[n - 1][n - 1]);
    int hi = n * n - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (swimReachable(grid, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

C++

static bool swimReachable(vector<vector<int>>& grid, int limit) {
    int n = (int) grid.size();
    if (grid[0][0] > limit) return false;
    vector<vector<bool>> seen(n, vector<bool>(n, false));
    seen[0][0] = true;
    vector<pair<int,int>> stack;
    stack.push_back(make_pair(0, 0));
    int dr[4] = {1, -1, 0, 0};
    int dc[4] = {0, 0, 1, -1};
    while (!stack.empty()) {
        pair<int,int> cell = stack.back();
        stack.pop_back();
        if (cell.first == n - 1 && cell.second == n - 1) return true;
        for (int d = 0; d < 4; d++) {
            int nr = cell.first + dr[d], nc = cell.second + dc[d];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n || seen[nr][nc]) continue;
            if (grid[nr][nc] > limit) continue;
            seen[nr][nc] = true;
            stack.push_back(make_pair(nr, nc));
        }
    }
    return seen[n - 1][n - 1];
}

int swimInWater(vector<vector<int>>& grid) {
    int n = (int) grid.size();
    int lo = max(grid[0][0], grid[n - 1][n - 1]);
    int hi = n * n - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (swimReachable(grid, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

JavaScript

var swimInWater = function(grid) {
    const n = grid.length;
    const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    const reachable = function(limit) {
        if (grid[0][0] > limit) return false;
        const seen = [];
        for (let r = 0; r < n; r++) {
            const row = [];
            for (let c = 0; c < n; c++) row.push(false);
            seen.push(row);
        }
        seen[0][0] = true;
        const stack = [[0, 0]];
        while (stack.length > 0) {
            const cell = stack.pop();
            if (cell[0] === n - 1 && cell[1] === n - 1) return true;
            for (let d = 0; d < 4; d++) {
                const nr = cell[0] + dr[d], nc = cell[1] + dc[d];
                if (nr < 0 || nc < 0 || nr >= n || nc >= n || seen[nr][nc]) continue;
                if (grid[nr][nc] > limit) continue;
                seen[nr][nc] = true;
                stack.push([nr, nc]);
            }
        }
        return seen[n - 1][n - 1];
    };
    let lo = grid[0][0] > grid[n - 1][n - 1] ? grid[0][0] : grid[n - 1][n - 1];
    let hi = n * n - 1;
    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (reachable(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard