Skip to main content
CodePeetCodePeet
CodePeet 250

Reorganize String

MEDIUMProblemSolveExternal Links

Description

You are given an n × n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

It starts raining, and water gradually rises over time. At time t, the water level is t, meaning any cell with elevation less than or equal to t is submerged and therefore reachable by swimming.

You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the minimum time until you can reach the bottom-right square (n - 1, n - 1) starting from the top-left square (0, 0).

In essence, you need to find a path from (0, 0) to (n - 1, n - 1) that minimizes the maximum elevation encountered along the path. The answer equals that maximum elevation, because you must wait until time equals the highest cell on your chosen path before you can traverse it.

Examples

Example 1

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

Output: 3

Explanation: The 2×2 grid has elevations:

0  2
1  3
  • At time 0: you are at (0,0) with elevation 0. Adjacent cells (0,1)=2 and (1,0)=1 both have elevation > 0, so you cannot move.
  • At time 1: you can move to (1,0) since elevation 1 ≤ 1. But (1,1)=3 > 1, so you cannot reach the target.
  • At time 2: you can also reach (0,1) since elevation 2 ≤ 2. But (1,1)=3 > 2 still.
  • At time 3: all cells have elevation ≤ 3. You can swim (0,0) → (1,0) → (1,1) or (0,0) → (0,1) → (1,1).

The minimum time is 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

Explanation: The 5×5 grid is:

 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

The optimal path follows the border: (0,0)→(0,1)→(0,2)→(0,3)→(0,4)→(1,4)→(2,4)→(2,3)→(2,2)→(2,1)→(2,0)→(3,0)→(4,0)→(4,1)→(4,2)→(4,3)→(4,4). The maximum elevation on this path is 16 (at cell (2,4)), so we must wait until time 16.

Example 3

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

Output: 3

Explanation: The 2×2 grid is:

3  2
0  1

The starting cell (0,0) has elevation 3, so we must wait until at least time 3. At time 3, all cells (3, 2, 0, 1) have elevation ≤ 3, so any path works. The answer is 3, determined by the starting cell itself.

Constraints

  • n == grid.length == grid[i].length
  • 1 ≤ n ≤ 50
  • 0 ≤ grid[i][j] < n²
  • Each value grid[i][j] is unique.

Editorial

Brute Force

Intuition

The most straightforward approach is to simulate the rising water level. For each possible time t starting from the minimum possible value, check whether there exists a path from (0, 0) to (n-1, n-1) using only cells with elevation ≤ t.

The minimum possible answer is max(grid[0][0], grid[n-1][n-1]) because both the start and end cells must be submerged. The maximum possible answer is n² - 1 (the largest elevation in the grid).

For each candidate time t, we run a BFS (Breadth-First Search) from (0, 0). The BFS only visits cells whose elevation is at most t. If BFS reaches (n-1, n-1), then t is a valid answer and we return it (since we try values in ascending order, the first valid t is the minimum).

This approach is correct but slow because we might try up to n² values of t, and each BFS traverses up to n² cells, leading to O(n⁴) time.

Step-by-Step Explanation

Let's trace through Example 1: grid = [[0,2],[1,3]].

The minimum possible time is max(grid[0][0], grid[1][1]) = max(0, 3) = 3. But for illustration, let's check from t = 0.

Step 1 — Try t = 0: Cells with elevation ≤ 0: only (0,0)=0. BFS from (0,0): neighbors (0,1)=2 > 0 and (1,0)=1 > 0. Cannot reach anywhere. Target (1,1) unreachable. ✗

Step 2 — Try t = 1: Cells ≤ 1: (0,0)=0 and (1,0)=1. BFS from (0,0): visit (1,0). From (1,0): neighbor (1,1)=3 > 1 → blocked, (0,0) already visited. Target unreachable. ✗

Step 3 — Try t = 2: Cells ≤ 2: (0,0)=0, (1,0)=1, (0,1)=2. BFS from (0,0): visit (1,0) and (0,1). From (1,0): (1,1)=3 > 2 → blocked. From (0,1): (1,1)=3 > 2 → blocked. Target unreachable. ✗

Step 4 — Try t = 3: Cells ≤ 3: all four cells. BFS from (0,0): visit (1,0) and (0,1). From (1,0): visit (1,1). Target reached! ✓

Step 5: Return t = 3.

Brute Force — Trying Each Water Level — Watch how we increment the water level t from 0 upward, running BFS at each level to check if a path exists from the top-left to the bottom-right corner.

Algorithm

  1. Determine the search range: start from t = max(grid[0][0], grid[n-1][n-1]) (both endpoints must be reachable) up to t = n² - 1.
  2. For each candidate time t:
    a. Run BFS from (0, 0). Only visit cells with grid[r][c] ≤ t.
    b. If BFS reaches (n-1, n-1), return t.
  3. If no path found at any level (impossible given constraints), return n² - 1.

Code

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

        for (int t = max(grid[0][0], grid[n-1][n-1]); t < n * n; t++) {
            // BFS to check if path exists at time t
            vector<vector<bool>> visited(n, vector<bool>(n, false));
            queue<pair<int,int>> q;

            if (grid[0][0] <= t) {
                q.push({0, 0});
                visited[0][0] = true;
            }

            while (!q.empty()) {
                auto [r, c] = q.front();
                q.pop();
                if (r == n - 1 && c == n - 1) return t;
                for (auto& d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n
                        && !visited[nr][nc] && grid[nr][nc] <= t) {
                        visited[nr][nc] = true;
                        q.push({nr, nc});
                    }
                }
            }
        }

        return n * n - 1;
    }
};
class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        for t in range(max(grid[0][0], grid[n-1][n-1]), n * n):
            # BFS to check if path exists at time t
            visited = [[False] * n for _ in range(n)]
            queue = deque()

            if grid[0][0] <= t:
                queue.append((0, 0))
                visited[0][0] = True

            while queue:
                r, c = queue.popleft()
                if r == n - 1 and c == n - 1:
                    return t
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < n and 0 <= nc < n
                        and not visited[nr][nc]
                        and grid[nr][nc] <= t):
                        visited[nr][nc] = True
                        queue.append((nr, nc))

        return n * n - 1
class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

        for (int t = Math.max(grid[0][0], grid[n-1][n-1]); t < n * n; t++) {
            boolean[][] visited = new boolean[n][n];
            Queue<int[]> queue = new LinkedList<>();

            if (grid[0][0] <= t) {
                queue.offer(new int[]{0, 0});
                visited[0][0] = true;
            }

            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                int r = cell[0], c = cell[1];
                if (r == n - 1 && c == n - 1) return t;
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n
                        && !visited[nr][nc] && grid[nr][nc] <= t) {
                        visited[nr][nc] = true;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
        }

        return n * n - 1;
    }
}

Complexity Analysis

Time Complexity: O(n⁴)

In the worst case, we try up to n² different values of t. For each value, BFS explores up to n² cells. Total: O(n²) × O(n²) = O(n⁴). For n = 50, this is 50⁴ = 6.25 million operations, which is manageable but not efficient.

Space Complexity: O(n²)

The BFS visited array and queue each use O(n²) space.

Why This Approach Is Not Efficient

The brute force linearly tries every water level from the minimum to the answer. The answer could be as large as n² - 1, so we might run BFS up to n² times. Each BFS is O(n²), leading to O(n⁴).

But notice an important property: if a path exists at time t, then a path also exists at time t + 1 (higher water means more cells are accessible). This means the answer has a monotonic "feasibility" property — there exists a threshold below which no path exists and above which a path always exists.

This monotonicity is the perfect setup for binary search! Instead of checking every value of t one by one, we can binary search for the minimum valid t. This reduces the number of BFS calls from O(n²) to O(log n²) = O(log n), dramatically improving performance.

Better Approach - Binary Search + BFS

Intuition

Since the feasibility of reaching the target is monotonic in t (if we can reach at time t, we can also reach at any time > t), we can binary search on the answer.

The search space is [max(grid[0][0], grid[n-1][n-1]), n² - 1]. At each step of binary search, we pick mid and ask: "Can we swim from (0,0) to (n-1,n-1) at time mid?" This check is answered by a BFS that only visits cells with elevation ≤ mid.

  • If BFS reaches the target: the answer might be mid or lower, so we search the left half: high = mid.
  • If BFS fails: we need more time, so we search the right half: low = mid + 1.

The binary search converges when low == high, giving us the exact minimum time.

This reduces the number of BFS calls from O(n²) to O(log n²) = O(2 log n), while each BFS still costs O(n²). Total: O(n² log n).

Step-by-Step Explanation

Let's trace through Example 1: grid = [[0,2],[1,3]], n = 2.

Search range: low = max(0, 3) = 3, high = 2² - 1 = 3. Since low == high immediately, the answer is 3.

This is too simple! Let's instead use low = 0, high = 3 for illustration (the general form of the algorithm).

Step 1 — Binary search state: low = 0, high = 3.

Step 2 — First iteration: mid = (0 + 3) / 2 = 1. BFS with t = 1: cells ≤ 1 are (0,0)=0 and (1,0)=1. BFS reaches (1,0) but cannot reach (1,1)=3 > 1. FAIL → low = mid + 1 = 2.

Step 3 — Second iteration: low = 2, high = 3. mid = (2 + 3) / 2 = 2. BFS with t = 2: cells ≤ 2 are (0,0), (1,0), (0,1). From these, (1,1)=3 > 2. FAIL → low = mid + 1 = 3.

Step 4 — Termination: low = 3, high = 3. low == high. Return 3.

For Example 2 (5×5 grid), binary search would search [0, 24] and find 16 in about log₂(25) ≈ 5 BFS calls, versus the brute force which would need 17 calls (t = 0 to 16).

Binary Search + BFS — Halving the Search Space — Watch how binary search narrows down the minimum water level by testing the midpoint and deciding which half to explore, using BFS to verify path existence.

Algorithm

  1. Set low = max(grid[0][0], grid[n-1][n-1]) and high = n² - 1.
  2. While low < high:
    a. Compute mid = (low + high) / 2.
    b. Run BFS from (0, 0), only visiting cells with grid[r][c] ≤ mid.
    c. If BFS reaches (n-1, n-1): set high = mid (answer could be mid or lower).
    d. If BFS fails: set low = mid + 1 (need higher water level).
  3. Return low.

Code

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        int lo = max(grid[0][0], grid[n-1][n-1]);
        int hi = n * n - 1;
        int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;

            // BFS to check reachability at time mid
            vector<vector<bool>> visited(n, vector<bool>(n, false));
            queue<pair<int,int>> q;
            q.push({0, 0});
            visited[0][0] = true;
            bool found = false;

            while (!q.empty() && !found) {
                auto [r, c] = q.front();
                q.pop();
                if (r == n - 1 && c == n - 1) {
                    found = true;
                    break;
                }
                for (auto& d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n
                        && !visited[nr][nc] && grid[nr][nc] <= mid) {
                        visited[nr][nc] = true;
                        q.push({nr, nc});
                    }
                }
            }

            if (found) hi = mid;
            else lo = mid + 1;
        }

        return lo;
    }
};
class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def can_reach(t: int) -> bool:
            if grid[0][0] > t:
                return False
            visited = [[False] * n for _ in range(n)]
            queue = deque([(0, 0)])
            visited[0][0] = True
            while queue:
                r, c = queue.popleft()
                if r == n - 1 and c == n - 1:
                    return True
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < n and 0 <= nc < n
                        and not visited[nr][nc]
                        and grid[nr][nc] <= t):
                        visited[nr][nc] = True
                        queue.append((nr, nc))
            return False

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

        return lo
class Solution {
    public 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;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;

            boolean[][] visited = new boolean[n][n];
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{0, 0});
            visited[0][0] = true;
            boolean found = false;

            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                int r = cell[0], c = cell[1];
                if (r == n - 1 && c == n - 1) {
                    found = true;
                    break;
                }
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n
                        && !visited[nr][nc] && grid[nr][nc] <= mid) {
                        visited[nr][nc] = true;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }

            if (found) hi = mid;
            else lo = mid + 1;
        }

        return lo;
    }
}

Complexity Analysis

Time Complexity: O(n² log n)

Binary search runs O(log n²) = O(log n) iterations. Each iteration performs a BFS that visits at most n² cells in O(n²) time. Total: O(n² × log n).

Space Complexity: O(n²)

The BFS visited array and queue each use O(n²) space.

Why This Approach Is Not Efficient

Binary search + BFS is a significant improvement over brute force, but it still performs multiple BFS traversals (one per binary search iteration). Each BFS rediscovers much of the same information: cells that are reachable are re-explored across iterations.

The key insight is that we do not actually need to guess the water level and verify — we can directly compute the minimum time by treating this as a shortest-path problem with a modified distance metric.

Instead of the usual sum-of-weights shortest path, we want to minimize the maximum elevation along the path. This is equivalent to finding the path where the bottleneck (highest cell) is minimized. Dijkstra's algorithm, adapted with max instead of +, solves this in a single pass without any binary search. The priority queue naturally processes cells in order of their required time, and we stop as soon as we reach the target.

Optimal Approach - Modified Dijkstra's Algorithm

Intuition

We can model this problem as a shortest-path problem with a twist. In standard Dijkstra's, the distance to a node is the sum of edge weights along the path. Here, the "distance" (time) to reach a cell is the maximum elevation encountered along the path to that cell.

Define dist[r][c] as the minimum time needed to reach cell (r, c) from (0, 0). The recurrence is:

dist[nr][nc] = min(dist[nr][nc], max(dist[r][c], grid[nr][nc]))

This says: to reach neighbor (nr, nc) through cell (r, c), we need time at least max(current time, neighbor's elevation). We want the path that minimizes this maximum.

We use a min-heap (priority queue) that always processes the cell with the smallest required time first. This greedy strategy works (just like standard Dijkstra's) because once we pop a cell from the heap, we have found the optimal time to reach it.

The algorithm terminates as soon as we pop the target cell (n-1, n-1) from the heap. This single-pass approach is more elegant and practically faster than binary search + BFS, even though both have the same asymptotic complexity O(n² log n).

Step-by-Step Explanation

Let's trace through Example 1: grid = [[0,2],[1,3]].

Step 1 — Initialize: dist = [[0, ∞], [∞, ∞]]. Push (0, 0, 0) into min-heap. dist[0][0] = grid[0][0] = 0.

Step 2 — Pop (time=0, r=0, c=0): Process cell (0,0). Check neighbors:

  • (0,1): new_time = max(0, grid[0][1]) = max(0, 2) = 2. Since 2 < dist[0][1]=∞, update dist[0][1]=2. Push (2, 0, 1).
  • (1,0): new_time = max(0, grid[1][0]) = max(0, 1) = 1. Since 1 < dist[1][0]=∞, update dist[1][0]=1. Push (1, 1, 0).
    Heap: [(1, 1, 0), (2, 0, 1)].

Step 3 — Pop (time=1, r=1, c=0): Process cell (1,0). Check neighbors:

  • (0,0): dist[0][0]=0 ≤ max(1, 0)=1. No improvement.
  • (1,1): new_time = max(1, grid[1][1]) = max(1, 3) = 3. Since 3 < dist[1][1]=∞, update dist[1][1]=3. Push (3, 1, 1).
    Heap: [(2, 0, 1), (3, 1, 1)].

Step 4 — Pop (time=2, r=0, c=1): Process cell (0,1). Check neighbors:

  • (0,0): no improvement.
  • (1,1): new_time = max(2, 3) = 3. dist[1][1] already 3. No improvement.
    Heap: [(3, 1, 1)].

Step 5 — Pop (time=3, r=1, c=1): This is the target! Return 3.

Dijkstra's found the answer in a single pass through the grid, processing only 4 cells. The key insight: by always expanding the cell with the smallest required time, we guarantee optimality.

Modified Dijkstra's — Single-Pass Optimal Path — Watch how Dijkstra's algorithm with a min-heap finds the optimal swim time in one pass, always expanding the cell that requires the least water level.

Algorithm

  1. Initialize dist[r][c] = ∞ for all cells. Set dist[0][0] = grid[0][0].
  2. Push (grid[0][0], 0, 0) into a min-heap.
  3. While the heap is not empty:
    a. Pop (time, r, c) with the smallest time.
    b. If (r, c) == (n-1, n-1), return time — we've reached the target optimally.
    c. If time > dist[r][c], this is a stale entry — skip it.
    d. For each 4-directional neighbor (nr, nc) within bounds:
    • Compute new_time = max(time, grid[nr][nc]).
    • If new_time < dist[nr][nc], update dist[nr][nc] = new_time and push (new_time, nr, nc) into the heap.
  4. Return -1 (should never happen for valid input).

Code

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

        // Min-heap: (time, row, col)
        priority_queue<tuple<int,int,int>,
                       vector<tuple<int,int,int>>,
                       greater<>> pq;
        vector<vector<int>> dist(n, vector<int>(n, INT_MAX));

        dist[0][0] = grid[0][0];
        pq.push({grid[0][0], 0, 0});

        while (!pq.empty()) {
            auto [t, r, c] = pq.top();
            pq.pop();

            if (r == n - 1 && c == n - 1) return t;
            if (t > dist[r][c]) continue;

            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                    int newDist = max(t, grid[nr][nc]);
                    if (newDist < dist[nr][nc]) {
                        dist[nr][nc] = newDist;
                        pq.push({newDist, nr, nc});
                    }
                }
            }
        }

        return -1;
    }
};
class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        dist = [[float('inf')] * n for _ in range(n)]
        dist[0][0] = grid[0][0]
        pq = [(grid[0][0], 0, 0)]  # (time, row, col)

        while pq:
            t, r, c = heapq.heappop(pq)

            if r == n - 1 and c == n - 1:
                return t
            if t > dist[r][c]:
                continue

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n:
                    new_dist = max(t, grid[nr][nc])
                    if new_dist < dist[nr][nc]:
                        dist[nr][nc] = new_dist
                        heapq.heappush(pq, (new_dist, nr, nc))

        return -1
class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

        int[][] dist = new int[n][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        dist[0][0] = grid[0][0];

        // Min-heap: [time, row, col]
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{grid[0][0], 0, 0});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int t = curr[0], r = curr[1], c = curr[2];

            if (r == n - 1 && c == n - 1) return t;
            if (t > dist[r][c]) continue;

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                    int newDist = Math.max(t, grid[nr][nc]);
                    if (newDist < dist[nr][nc]) {
                        dist[nr][nc] = newDist;
                        pq.offer(new int[]{newDist, nr, nc});
                    }
                }
            }
        }

        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n² log n)

Each of the n² cells is pushed into the heap at most once (thanks to the dist check). Each heap operation (push/pop) costs O(log n²) = O(log n). Total: O(n² × log n). While asymptotically the same as binary search + BFS, Dijkstra's is faster in practice because it processes each cell only once in a single pass, avoiding the overhead of multiple independent BFS traversals.

Space Complexity: O(n²)

The dist matrix uses O(n²) space. The priority queue can hold at most O(n²) entries.