Crack the Backend

Problem Statement

You are given an n×n grid where grid[i][j] is the elevation at (i,j). Water starts at time 0 and rises by 1 each unit of time. You can swim from one cell to another only when the water level (current time) is at least the elevation of both cells. Return the minimum time (water level) at which you can reach the bottom-right (n-1, n-1) from the top-left (0, 0).

Key Observations

UF + sort by elevation: Sort all cells (i, j) by grid[i][j] in ascending order. "Add" cells in that order: when we add a cell, we union it with any of its 4 neighbors that have already been added. When the roots of (0,0) and (n-1,n-1) first become the same, the current cell's elevation is the answer (we can swim at that time). Alternatively Dijkstra: state (max elevation so far, i, j); expand with minimum max elevation.

Approach

High-level: Build list (grid[i][j], i, j), sort by value. UF of size nn. For each (val,i,j) in order: for each 4-neighbor already "added" (e.g. we add in order so neighbors with smaller value are added), union; if find(0)==find(nn-1) return val.

Steps: List<int[]> cells = new ArrayList<>(); for (i,j) cells.add(new int[]{grid[i][j], i, j}); sort by cells.get(0); boolean[][] added; UF; for (int[] c : cells) { added[c[1]][c[2]]=true; for (each neighbor in grid and added) union; if (find(0)==find(n*n-1)) return c[0]; } return -1;

Implementation

Java

public int swimInWater(int[][] grid) {
    int n = grid.length;
    List<int[]> cells = new ArrayList<>();

    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
    cells.add(new int[]{grid[i][j], i, j});
    cells.sort(Comparator.comparingInt(a -> a[0]));
    int[] parent = new int[n * n];

    for (int i = 0; i < n * n; i++) {
        parent[i] = i;
    }

    int[] dx = {0,0,1,-1}, dy = {1,-1,0,0};

    for (int[] c : cells) {
        int v = c[0], i = c[1], j = c[2];
        int idx = i * n + j;

        for (int d = 0; d < 4; d++) {
            int ni = i + dx[d], nj = j + dy[d];

            if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] <= v)
            union(parent, idx, ni * n + nj);
        }

        if (find(parent, 0) == find(parent, n * n - 1)) {
            return v;
        }
    }

    return -1;
}

Test Cases

Example 1

Input

grid = [[0,2],[1,3]]

Expected

3

Explanation

At time 3 we can swim from 0 to 3.

Complexity Analysis

Time: O(n α(n)) ≈ O(n).
Space: O(n).

Follow-ups

Path compression + rank for optimal UF.