Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-115 · Minimax Dijkstra on an implicit four-neighbor grid

Path with Minimum Effort

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 45026 deterministic checks. Learner drafts are not executed.

Understand the problem

Travel from the top-left to the bottom-right cell using orthogonal moves. A route’s effort is its largest absolute height difference across one move. Return the smallest possible effort; a grid with no cells or a one-cell route has effort zero.

  • heights is a nonnull rectangular int[][] with nonnull rows. Empty outer arrays and zero-column rows are valid and return zero. Null outer input throws NullPointerException; null or ragged rows throw IllegalArgumentException before traversal, including zero-column cases. Size preconditions: at most 100,000 rows and 100,000 cells; row-major indexing fits int.
  • minimumEffort returns long. Heights span the full int domain; an edge jump can be 4,294,967,295. Cast before subtraction, then apply Math.abs to a long. Only up/right/down/left neighbors exist. Route effort counts no summed distance or cell count; every nonempty rectangle is connected.
  • Preserve source values and row identities, including shared row objects. No sorting or marking may alter the caller’s arrays. Auxiliary graph entries are privately allocated. Input must not be modified concurrently. Coordinate positions remain different vertices when two rows alias. All labels, heap entries, and BFS marks live in private storage.

Examples

  1. Input: [[1,2,2],[3,8,2],[5,3,5]]
    Output: 2

    The route 1→3→5→3→5 has jumps 2,2,2,2. Summing them would optimize a different objective.

  2. Input: [[MIN,MAX]]
    Output: 4294967295

    The only move spans the full signed-int height range.

  3. Input: [[7]], [], or [[],[]]
    Output: 0

    There is no required edge jump in each case.

Before you start

  • Implicit grid graphs and minimum-priority traversal
  • Bottleneck path costs and overflow-safe height differences

Recognize the structure

The cost of extending a route is max(currentEffort,newJump), not currentEffort+newJump. This extension is monotone and never lowers the prefix effort, so the same minimum-label finalization idea works with a different relaxation operator. An alternative view asks whether the target is reachable when edges above a chosen threshold are forbidden; that predicate is monotone and supports binary search.

Try before revealing

Hint 1

How does appending one edge change the largest jump so far?

Hint 2

The extension max(old,jump) never lowers a path cost.

Hint 3

Use Dijkstra with bottleneck relaxation, or binary search an allowed-jump threshold and test BFS reachability.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Binary search a threshold with BFS feasibility

For a candidate limit, run a fresh BFS through only edges whose absolute height difference is at most the limit. Reachability is false below the answer and true at or above it. Binary search the inclusive long interval [0,4294967295]. This compiling alternative is not exponential: it trades at most 32 grid traversals for avoiding a heap. Mark coordinates on enqueue to avoid repeated BFS claims.

Improve the baseline

Define bottleneck labels

distance[v] is the smallest discovered largest jump on a route from cell zero. Initialize it to infinity except distance[0]=0. A one-cell input immediately has a valid zero target pop. Generate neighbors from four directions instead of allocating a full grid edge list.

Relax with max and preserve the heap invariant

For edge jump w, candidate=max(current.cost,w). If candidate improves distance[next], assign it and insert an immutable snapshot. Cast heights[r][c] to long before subtraction. Order entries by cost and then row-major ID; a sorted teaching picture is not the internal PriorityQueue array.

Exit when the target is finalized

Skip stale snapshots first. A current minimum pop fixes a vertex’s optimal bottleneck. If that vertex is the target, return its cost immediately; discovery at enqueue time is too early. Other cells may retain tentative labels and frontier entries when the function returns.

Why it is correct

Path extension matches the objective

The edges of an extended path consist of the prefix edges and one last edge. Their maximum is exactly max(prefixEffort,lastJump). Every installed label therefore has a real route witness and never underestimates the optimum.

Minimum valid pop is optimal

Suppose a better bottleneck route to a popped vertex existed. Its first not-yet-finalized vertex has a finalized predecessor. Relaxing their edge would yield a candidate no larger than that better route’s bottleneck and hence smaller than the popped label. The heap would have chosen it first. This argument uses max monotonicity rather than additive weights.

Early target exit and threshold equivalence

A valid target pop equals the global optimum by finality, so remaining vertices need not be processed. Independently, a route has effort≤T exactly when every edge on it has jump≤T. This equivalence establishes the BFS predicate and the baseline’s binary-search answer, giving a different verification route.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}};
    private record Entry(long cost,int vertex) {}
    private static int columns(int[][] heights) {
        Objects.requireNonNull(heights,"heights");int cols=heights.length==0?0:heights[0]==null?-1:heights[0].length;
        for(int[] row:heights)if(row==null||row.length!=cols)throw new IllegalArgumentException("ragged or null row");return cols;
    }
    public static long minimumEffort(int[][] heights) {
        int cols=columns(heights),rows=heights.length;if(rows==0||cols==0)return 0;
        int n=rows*cols;long[] distance=new long[n];Arrays.fill(distance,Long.MAX_VALUE);distance[0]=0;
        PriorityQueue<Entry> heap=new PriorityQueue<>(Comparator.comparingLong(Entry::cost).thenComparingInt(Entry::vertex));heap.add(new Entry(0,0));
        while(!heap.isEmpty()) {
            Entry current=heap.remove();int v=current.vertex();
            if(current.cost()!=distance[v])continue;
            if(v==n-1)return current.cost();
            int r=v/cols,c=v%cols;
            for(int[] direction:DIRECTIONS) {
                int nr=r+direction[0],nc=c+direction[1];if(nr<0||nr>=rows||nc<0||nc>=cols)continue;
                int next=nr*cols+nc;long weight=Math.abs((long)heights[r][c]-heights[nr][nc]);
                long candidate=Math.max(current.cost(),weight);
                if(candidate<distance[next]) {distance[next]=candidate;heap.add(new Entry(candidate,next));}
            }
        }
        throw new AssertionError("nonempty rectangle is connected");
    }
    private static boolean reachable(int[][] h,int cols,long limit) {
        boolean[] seen=new boolean[h.length*cols];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[0]=true;queue.addLast(0);
        while(!queue.isEmpty()){int v=queue.removeFirst();if(v==seen.length-1)return true;int r=v/cols,c=v%cols;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<h.length&&nc>=0&&nc<cols&&!seen[nr*cols+nc]&&Math.abs((long)h[r][c]-h[nr][nc])<=limit){seen[nr*cols+nc]=true;queue.addLast(nr*cols+nc);}}}return false;
    }
    public static long baseline(int[][] heights) {
        int cols=columns(heights);if(heights.length==0||cols==0)return 0;long low=0,high=4294967295L;
        while(low<high){long mid=low+(high-low)/2;if(reachable(heights,cols,mid))high=mid;else low=mid+1;}return low;
    }
}

Read the meaningful blocks

A jump can exceed int without long overflow

MIN−MAX must be widened before subtraction; Math.abs(int) cannot repair an already wrapped difference. Math.abs((long)a−b) ranges up to 4294967295 and is safe. Bottleneck labels never exceed this maximum single jump.

Row-major identity belongs to coordinates

Encode vertex=r*cols+c and decode with division/remainder after checking nonempty dimensions. Aliased source rows do not collapse coordinates, because they have different positions and different adjacency. Validation checks all row lengths before any fast empty return.

Finalized and discovered are separate states

A target first discovered with effort six might later improve to two. The walkthrough records settled IDs and pending proposals separately and shows a target-return state after a valid pop. It does not claim every label is globally final at that point.

Complexity

Let R be rows, B be cells, and N=R+B. Validation costs O(R+1). The grid has O(B) directed neighbor occurrences; Dijkstra takes O(R+(B+1)log(B+2)) time and O(R+B+1) auxiliary storage conservatively, with O(B) labels and heap entries. No source row is copied or mutated. Output is a long.

Threshold BFS uses O(R+32(B+1)) time for the fixed full-int domain and O(B+1) auxiliary storage. More generally it is O(R+(B+1)log(W+1)) for maximum possible jump W, with shape validation once. Its fresh seen arrays are O(B) live workspace per probe; teaching trace snapshots are excluded.

Exact-state walkthroughs

Reveal normal and boundary traces

A gentle detour beats a steep center

Input: [[1,2,2],[3,8,2],[5,3,5]] · Minimum largest jump: 2

Step 1 of 29: Seed a cost-zero snapshot for the source.

Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.

Minimum effort — bottleneck labels on coordinate vertices

Phase: initial.

Read-only heights — MIN/MAX are signed-int extremes

122
382
535

Cell ID = row × column count + column. A label is the largest jump on its best known route, never a sum of jumps.

Cell bottleneck labels — tentative and final are separate

  • cell (0, 0) — ID 0cost: 0tentative
  • cell (0, 1) — ID 1cost: ∞ (no finite label)not reached
  • cell (0, 2) — ID 2cost: ∞ (no finite label)not reached
  • cell (1, 0) — ID 3cost: ∞ (no finite label)not reached
  • cell (1, 1) — ID 4cost: ∞ (no finite label)not reached
  • cell (1, 2) — ID 5cost: ∞ (no finite label)not reached
  • cell (2, 0) — ID 6cost: ∞ (no finite label)not reached
  • cell (2, 1) — ID 7cost: ∞ (no finite label)not reached
  • cell (2, 2) — ID 8cost: ∞ (no finite label)not reached

Heap proposals — sorted removal order, not internal array order

  • 0: [cost 0, vertex 0]

Cost snapshots are immutable; improved labels leave older proposals to be discarded later. Strict improvements stop equal-cost cycles from re-enqueueing forever.

∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Nonempty rectangular grids are connected; empty-grid effort is zero. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.

State after this step
VariableValue
input[[1,2,2],[3,8,2],[5,3,5]]
rows3
cols3
distance[0,null,null,null,null,null,null,null,null]
frontier[[0,0]]
settled[]
phase"initial"
currentnull
See the affected Java block
 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}};
 4     private record Entry(long cost,int vertex) {}
 5     private static int columns(int[][] heights) {
 6         Objects.requireNonNull(heights,"heights");int cols=heights.length==0?0:heights[0]==null?-1:heights[0].length;
 7         for(int[] row:heights)if(row==null||row.length!=cols)throw new IllegalArgumentException("ragged or null row");return cols;
 8     }
 9     public static long minimumEffort(int[][] heights) {
10         int cols=columns(heights),rows=heights.length;if(rows==0||cols==0)return 0;
11         int n=rows*cols;long[] distance=new long[n];Arrays.fill(distance,Long.MAX_VALUE);distance[0]=0;
12         PriorityQueue<Entry> heap=new PriorityQueue<>(Comparator.comparingLong(Entry::cost).thenComparingInt(Entry::vertex));heap.add(new Entry(0,0));
13         while(!heap.isEmpty()) {
14             Entry current=heap.remove();int v=current.vertex();
15             if(current.cost()!=distance[v])continue;
16             if(v==n-1)return current.cost();
17             int r=v/cols,c=v%cols;
18             for(int[] direction:DIRECTIONS) {
19                 int nr=r+direction[0],nc=c+direction[1];if(nr<0||nr>=rows||nc<0||nc>=cols)continue;
20                 int next=nr*cols+nc;long weight=Math.abs((long)heights[r][c]-heights[nr][nc]);
21                 long candidate=Math.max(current.cost(),weight);
22                 if(candidate<distance[next]) {distance[next]=candidate;heap.add(new Entry(candidate,next));}
23             }
24         }
25         throw new AssertionError("nonempty rectangle is connected");
26     }
27     private static boolean reachable(int[][] h,int cols,long limit) {
28         boolean[] seen=new boolean[h.length*cols];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[0]=true;queue.addLast(0);
29         while(!queue.isEmpty()){int v=queue.removeFirst();if(v==seen.length-1)return true;int r=v/cols,c=v%cols;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<h.length&&nc>=0&&nc<cols&&!seen[nr*cols+nc]&&Math.abs((long)h[r][c]-h[nr][nc])<=limit){seen[nr*cols+nc]=true;queue.addLast(nr*cols+nc);}}}return false;
30     }
31     public static long baseline(int[][] heights) {
32         int cols=columns(heights);if(heights.length==0||cols==0)return 0;long low=0,high=4294967295L;
33         while(low<high){long mid=low+(high-low)/2;if(reachable(heights,cols,mid))high=mid;else low=mid+1;}return low;
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Seed a cost-zero snapshot for the source.

    Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,null,null,null,null,null,null,null,null]
    frontier
    [[0,0]]
    settled
    []
    phase
    "initial"
    current
    null
  2. Remove the least valid cost and finalize this vertex.

    Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,null,null,null,null,null,null,null,null]
    frontier
    []
    settled
    [0]
    phase
    "settle"
    current
    0
    cost
    0
  3. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,null,null,null,null,null,null,null]
    frontier
    [[1,1]]
    settled
    [0]
    phase
    "relax"
    current
    0
    cost
    0
    edgeIndex
    0
    next
    1
    weight
    1
    candidate
    1
    improved
    true
  4. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,null,2,null,null,null,null,null]
    frontier
    [[1,1],[2,3]]
    settled
    [0]
    phase
    "relax"
    current
    0
    cost
    0
    edgeIndex
    1
    next
    3
    weight
    2
    candidate
    2
    improved
    true
  5. Remove the least valid cost and finalize this vertex.

    Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,null,2,null,null,null,null,null]
    frontier
    [[2,3]]
    settled
    [0,1]
    phase
    "settle"
    current
    1
    cost
    1
  6. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,null,null,null,null,null]
    frontier
    [[1,2],[2,3]]
    settled
    [0,1]
    phase
    "relax"
    current
    1
    cost
    1
    edgeIndex
    0
    next
    2
    weight
    0
    candidate
    1
    improved
    true
  7. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,6,null,null,null,null]
    frontier
    [[1,2],[2,3],[6,4]]
    settled
    [0,1]
    phase
    "relax"
    current
    1
    cost
    1
    edgeIndex
    1
    next
    4
    weight
    6
    candidate
    6
    improved
    true
  8. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,6,null,null,null,null]
    frontier
    [[1,2],[2,3],[6,4]]
    settled
    [0,1]
    phase
    "relax"
    current
    1
    cost
    1
    edgeIndex
    2
    next
    0
    weight
    1
    candidate
    1
    improved
    false
  9. Remove the least valid cost and finalize this vertex.

    Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,6,null,null,null,null]
    frontier
    [[2,3],[6,4]]
    settled
    [0,1,2]
    phase
    "settle"
    current
    2
    cost
    1
  10. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,6,1,null,null,null]
    frontier
    [[1,5],[2,3],[6,4]]
    settled
    [0,1,2]
    phase
    "relax"
    current
    2
    cost
    1
    edgeIndex
    0
    next
    5
    weight
    0
    candidate
    1
    improved
    true
  11. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,6,1,null,null,null]
    frontier
    [[1,5],[2,3],[6,4]]
    settled
    [0,1,2]
    phase
    "relax"
    current
    2
    cost
    1
    edgeIndex
    1
    next
    1
    weight
    0
    candidate
    1
    improved
    false
  12. Remove the least valid cost and finalize this vertex.

    Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,6,1,null,null,null]
    frontier
    [[2,3],[6,4]]
    settled
    [0,1,2,5]
    phase
    "settle"
    current
    5
    cost
    1
  13. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,6,1,null,null,null]
    frontier
    [[2,3],[6,4]]
    settled
    [0,1,2,5]
    phase
    "relax"
    current
    5
    cost
    1
    edgeIndex
    0
    next
    2
    weight
    0
    candidate
    1
    improved
    false
  14. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,6,1,null,null,3]
    frontier
    [[2,3],[3,8],[6,4]]
    settled
    [0,1,2,5]
    phase
    "relax"
    current
    5
    cost
    1
    edgeIndex
    1
    next
    8
    weight
    3
    candidate
    3
    improved
    true
  15. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,6,1,null,null,3]
    frontier
    [[2,3],[3,8],[6,4]]
    settled
    [0,1,2,5]
    phase
    "relax"
    current
    5
    cost
    1
    edgeIndex
    2
    next
    4
    weight
    6
    candidate
    6
    improved
    false
  16. Remove the least valid cost and finalize this vertex.

    Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,6,1,null,null,3]
    frontier
    [[3,8],[6,4]]
    settled
    [0,1,2,5,3]
    phase
    "settle"
    current
    3
    cost
    2
  17. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,6,1,null,null,3]
    frontier
    [[3,8],[6,4]]
    settled
    [0,1,2,5,3]
    phase
    "relax"
    current
    3
    cost
    2
    edgeIndex
    0
    next
    0
    weight
    2
    candidate
    2
    improved
    false
  18. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,5,1,null,null,3]
    frontier
    [[3,8],[5,4],[6,4]]
    settled
    [0,1,2,5,3]
    phase
    "relax"
    current
    3
    cost
    2
    edgeIndex
    1
    next
    4
    weight
    5
    candidate
    5
    improved
    true
  19. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,5,1,2,null,3]
    frontier
    [[2,6],[3,8],[5,4],[6,4]]
    settled
    [0,1,2,5,3]
    phase
    "relax"
    current
    3
    cost
    2
    edgeIndex
    2
    next
    6
    weight
    2
    candidate
    2
    improved
    true
  20. Remove the least valid cost and finalize this vertex.

    Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,5,1,2,null,3]
    frontier
    [[3,8],[5,4],[6,4]]
    settled
    [0,1,2,5,3,6]
    phase
    "settle"
    current
    6
    cost
    2
  21. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,5,1,2,null,3]
    frontier
    [[3,8],[5,4],[6,4]]
    settled
    [0,1,2,5,3,6]
    phase
    "relax"
    current
    6
    cost
    2
    edgeIndex
    0
    next
    3
    weight
    2
    candidate
    2
    improved
    false
  22. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,5,1,2,2,3]
    frontier
    [[2,7],[3,8],[5,4],[6,4]]
    settled
    [0,1,2,5,3,6]
    phase
    "relax"
    current
    6
    cost
    2
    edgeIndex
    1
    next
    7
    weight
    2
    candidate
    2
    improved
    true
  23. Remove the least valid cost and finalize this vertex.

    Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,5,1,2,2,3]
    frontier
    [[3,8],[5,4],[6,4]]
    settled
    [0,1,2,5,3,6,7]
    phase
    "settle"
    current
    7
    cost
    2
  24. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,5,1,2,2,3]
    frontier
    [[3,8],[5,4],[6,4]]
    settled
    [0,1,2,5,3,6,7]
    phase
    "relax"
    current
    7
    cost
    2
    edgeIndex
    0
    next
    4
    weight
    5
    candidate
    5
    improved
    false
  25. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,5,1,2,2,2]
    frontier
    [[2,8],[3,8],[5,4],[6,4]]
    settled
    [0,1,2,5,3,6,7]
    phase
    "relax"
    current
    7
    cost
    2
    edgeIndex
    1
    next
    8
    weight
    2
    candidate
    2
    improved
    true
  26. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,5,1,2,2,2]
    frontier
    [[2,8],[3,8],[5,4],[6,4]]
    settled
    [0,1,2,5,3,6,7]
    phase
    "relax"
    current
    7
    cost
    2
    edgeIndex
    2
    next
    6
    weight
    2
    candidate
    2
    improved
    false
  27. Remove the least valid cost and finalize this vertex.

    Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,5,1,2,2,2]
    frontier
    [[3,8],[5,4],[6,4]]
    settled
    [0,1,2,5,3,6,7,8]
    phase
    "settle"
    current
    8
    cost
    2
  28. The target is final when popped with its current bottleneck.

    Discovery is insufficient for early exit; a later route can lower a tentative bottleneck. Other cells can remain tentative when the target is returned.

    input
    [[1,2,2],[3,8,2],[5,3,5]]
    rows
    3
    cols
    3
    distance
    [0,1,1,2,5,1,2,2,2]
    frontier
    [[3,8],[5,4],[6,4]]
    settled
    [0,1,2,5,3,6,7,8]
    phase
    "target"
    current
    8
    cost
    2
  29. Return the documented result without changing caller input.

    Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.

    result
    2

The only jump spans the full int domain

Input: [[-2147483648,2147483647]] · Minimum largest jump: 4294967295

Step 1 of 6: Seed a cost-zero snapshot for the source.

Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.

Minimum effort — bottleneck labels on coordinate vertices

Phase: initial.

Read-only heights — MIN/MAX are signed-int extremes

MINMAX

Cell ID = row × column count + column. A label is the largest jump on its best known route, never a sum of jumps.

Cell bottleneck labels — tentative and final are separate

  • cell (0, 0) — ID 0cost: 0tentative
  • cell (0, 1) — ID 1cost: ∞ (no finite label)not reached

Heap proposals — sorted removal order, not internal array order

  • 0: [cost 0, vertex 0]

Cost snapshots are immutable; improved labels leave older proposals to be discarded later. Strict improvements stop equal-cost cycles from re-enqueueing forever.

∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Nonempty rectangular grids are connected; empty-grid effort is zero. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.

State after this step
VariableValue
input[[-2147483648,2147483647]]
rows1
cols2
distance[0,null]
frontier[[0,0]]
settled[]
phase"initial"
currentnull
See the affected Java block
 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}};
 4     private record Entry(long cost,int vertex) {}
 5     private static int columns(int[][] heights) {
 6         Objects.requireNonNull(heights,"heights");int cols=heights.length==0?0:heights[0]==null?-1:heights[0].length;
 7         for(int[] row:heights)if(row==null||row.length!=cols)throw new IllegalArgumentException("ragged or null row");return cols;
 8     }
 9     public static long minimumEffort(int[][] heights) {
10         int cols=columns(heights),rows=heights.length;if(rows==0||cols==0)return 0;
11         int n=rows*cols;long[] distance=new long[n];Arrays.fill(distance,Long.MAX_VALUE);distance[0]=0;
12         PriorityQueue<Entry> heap=new PriorityQueue<>(Comparator.comparingLong(Entry::cost).thenComparingInt(Entry::vertex));heap.add(new Entry(0,0));
13         while(!heap.isEmpty()) {
14             Entry current=heap.remove();int v=current.vertex();
15             if(current.cost()!=distance[v])continue;
16             if(v==n-1)return current.cost();
17             int r=v/cols,c=v%cols;
18             for(int[] direction:DIRECTIONS) {
19                 int nr=r+direction[0],nc=c+direction[1];if(nr<0||nr>=rows||nc<0||nc>=cols)continue;
20                 int next=nr*cols+nc;long weight=Math.abs((long)heights[r][c]-heights[nr][nc]);
21                 long candidate=Math.max(current.cost(),weight);
22                 if(candidate<distance[next]) {distance[next]=candidate;heap.add(new Entry(candidate,next));}
23             }
24         }
25         throw new AssertionError("nonempty rectangle is connected");
26     }
27     private static boolean reachable(int[][] h,int cols,long limit) {
28         boolean[] seen=new boolean[h.length*cols];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[0]=true;queue.addLast(0);
29         while(!queue.isEmpty()){int v=queue.removeFirst();if(v==seen.length-1)return true;int r=v/cols,c=v%cols;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<h.length&&nc>=0&&nc<cols&&!seen[nr*cols+nc]&&Math.abs((long)h[r][c]-h[nr][nc])<=limit){seen[nr*cols+nc]=true;queue.addLast(nr*cols+nc);}}}return false;
30     }
31     public static long baseline(int[][] heights) {
32         int cols=columns(heights);if(heights.length==0||cols==0)return 0;long low=0,high=4294967295L;
33         while(low<high){long mid=low+(high-low)/2;if(reachable(heights,cols,mid))high=mid;else low=mid+1;}return low;
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Seed a cost-zero snapshot for the source.

    Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.

    input
    [[-2147483648,2147483647]]
    rows
    1
    cols
    2
    distance
    [0,null]
    frontier
    [[0,0]]
    settled
    []
    phase
    "initial"
    current
    null
  2. Remove the least valid cost and finalize this vertex.

    Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.

    input
    [[-2147483648,2147483647]]
    rows
    1
    cols
    2
    distance
    [0,null]
    frontier
    []
    settled
    [0]
    phase
    "settle"
    current
    0
    cost
    0
  3. Compare the largest jump along this candidate route.

    A failed relaxation leaves both label and frontier unchanged. The path extension uses max, not addition.

    input
    [[-2147483648,2147483647]]
    rows
    1
    cols
    2
    distance
    [0,4294967295]
    frontier
    [[4294967295,1]]
    settled
    [0]
    phase
    "relax"
    current
    0
    cost
    0
    edgeIndex
    0
    next
    1
    weight
    4294967295
    candidate
    4294967295
    improved
    true
  4. Remove the least valid cost and finalize this vertex.

    Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.

    input
    [[-2147483648,2147483647]]
    rows
    1
    cols
    2
    distance
    [0,4294967295]
    frontier
    []
    settled
    [0,1]
    phase
    "settle"
    current
    1
    cost
    4294967295
  5. The target is final when popped with its current bottleneck.

    Discovery is insufficient for early exit; a later route can lower a tentative bottleneck. Other cells can remain tentative when the target is returned.

    input
    [[-2147483648,2147483647]]
    rows
    1
    cols
    2
    distance
    [0,4294967295]
    frontier
    []
    settled
    [0,1]
    phase
    "target"
    current
    1
    cost
    4294967295
  6. Return the documented result without changing caller input.

    Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.

    result
    4294967295

A one-cell path has no edge cost

Input: [[7]] · Minimum largest jump: 0

Step 1 of 4: Seed a cost-zero snapshot for the source.

Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.

Minimum effort — bottleneck labels on coordinate vertices

Phase: initial.

Read-only heights — MIN/MAX are signed-int extremes

7

Cell ID = row × column count + column. A label is the largest jump on its best known route, never a sum of jumps.

Cell bottleneck labels — tentative and final are separate

  • cell (0, 0) — ID 0cost: 0tentative

Heap proposals — sorted removal order, not internal array order

  • 0: [cost 0, vertex 0]

Cost snapshots are immutable; improved labels leave older proposals to be discarded later. Strict improvements stop equal-cost cycles from re-enqueueing forever.

∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Nonempty rectangular grids are connected; empty-grid effort is zero. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.

State after this step
VariableValue
input[[7]]
rows1
cols1
distance[0]
frontier[[0,0]]
settled[]
phase"initial"
currentnull
See the affected Java block
 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}};
 4     private record Entry(long cost,int vertex) {}
 5     private static int columns(int[][] heights) {
 6         Objects.requireNonNull(heights,"heights");int cols=heights.length==0?0:heights[0]==null?-1:heights[0].length;
 7         for(int[] row:heights)if(row==null||row.length!=cols)throw new IllegalArgumentException("ragged or null row");return cols;
 8     }
 9     public static long minimumEffort(int[][] heights) {
10         int cols=columns(heights),rows=heights.length;if(rows==0||cols==0)return 0;
11         int n=rows*cols;long[] distance=new long[n];Arrays.fill(distance,Long.MAX_VALUE);distance[0]=0;
12         PriorityQueue<Entry> heap=new PriorityQueue<>(Comparator.comparingLong(Entry::cost).thenComparingInt(Entry::vertex));heap.add(new Entry(0,0));
13         while(!heap.isEmpty()) {
14             Entry current=heap.remove();int v=current.vertex();
15             if(current.cost()!=distance[v])continue;
16             if(v==n-1)return current.cost();
17             int r=v/cols,c=v%cols;
18             for(int[] direction:DIRECTIONS) {
19                 int nr=r+direction[0],nc=c+direction[1];if(nr<0||nr>=rows||nc<0||nc>=cols)continue;
20                 int next=nr*cols+nc;long weight=Math.abs((long)heights[r][c]-heights[nr][nc]);
21                 long candidate=Math.max(current.cost(),weight);
22                 if(candidate<distance[next]) {distance[next]=candidate;heap.add(new Entry(candidate,next));}
23             }
24         }
25         throw new AssertionError("nonempty rectangle is connected");
26     }
27     private static boolean reachable(int[][] h,int cols,long limit) {
28         boolean[] seen=new boolean[h.length*cols];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[0]=true;queue.addLast(0);
29         while(!queue.isEmpty()){int v=queue.removeFirst();if(v==seen.length-1)return true;int r=v/cols,c=v%cols;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<h.length&&nc>=0&&nc<cols&&!seen[nr*cols+nc]&&Math.abs((long)h[r][c]-h[nr][nc])<=limit){seen[nr*cols+nc]=true;queue.addLast(nr*cols+nc);}}}return false;
30     }
31     public static long baseline(int[][] heights) {
32         int cols=columns(heights);if(heights.length==0||cols==0)return 0;long low=0,high=4294967295L;
33         while(low<high){long mid=low+(high-low)/2;if(reachable(heights,cols,mid))high=mid;else low=mid+1;}return low;
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Seed a cost-zero snapshot for the source.

    Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.

    input
    [[7]]
    rows
    1
    cols
    1
    distance
    [0]
    frontier
    [[0,0]]
    settled
    []
    phase
    "initial"
    current
    null
  2. Remove the least valid cost and finalize this vertex.

    Compare the stored snapshot with the current label before scanning outgoing edges. Equal-cost alternatives do not enqueue, so zero-cost cycles cannot loop indefinitely. A finalized cost cannot later decrease.

    input
    [[7]]
    rows
    1
    cols
    1
    distance
    [0]
    frontier
    []
    settled
    [0]
    phase
    "settle"
    current
    0
    cost
    0
  3. The target is final when popped with its current bottleneck.

    Discovery is insufficient for early exit; a later route can lower a tentative bottleneck. Other cells can remain tentative when the target is returned.

    input
    [[7]]
    rows
    1
    cols
    1
    distance
    [0]
    frontier
    []
    settled
    [0]
    phase
    "target"
    current
    0
    cost
    0
  4. Return the documented result without changing caller input.

    Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.

    result
    0

Empty grid

Input: [] · Minimum largest jump: 0

Step 1 of 3: Seed a cost-zero snapshot for the source.

Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.

Minimum effort — bottleneck labels on coordinate vertices

Phase: initial.

Read-only heights — MIN/MAX are signed-int extremes

No cell vertices; effort is zero.

Cell ID = row × column count + column. A label is the largest jump on its best known route, never a sum of jumps.

Cell bottleneck labels — tentative and final are separate

    Heap proposals — sorted removal order, not internal array order

    Empty.

    Cost snapshots are immutable; improved labels leave older proposals to be discarded later. Strict improvements stop equal-cost cycles from re-enqueueing forever.

    ∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Nonempty rectangular grids are connected; empty-grid effort is zero. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.

    State after this step
    VariableValue
    input[]
    rows0
    cols0
    distance[]
    frontier[]
    settled[]
    phase"initial"
    currentnull
    See the affected Java block
     1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}};
 4     private record Entry(long cost,int vertex) {}
 5     private static int columns(int[][] heights) {
 6         Objects.requireNonNull(heights,"heights");int cols=heights.length==0?0:heights[0]==null?-1:heights[0].length;
 7         for(int[] row:heights)if(row==null||row.length!=cols)throw new IllegalArgumentException("ragged or null row");return cols;
 8     }
 9     public static long minimumEffort(int[][] heights) {
10         int cols=columns(heights),rows=heights.length;if(rows==0||cols==0)return 0;
11         int n=rows*cols;long[] distance=new long[n];Arrays.fill(distance,Long.MAX_VALUE);distance[0]=0;
12         PriorityQueue<Entry> heap=new PriorityQueue<>(Comparator.comparingLong(Entry::cost).thenComparingInt(Entry::vertex));heap.add(new Entry(0,0));
13         while(!heap.isEmpty()) {
14             Entry current=heap.remove();int v=current.vertex();
15             if(current.cost()!=distance[v])continue;
16             if(v==n-1)return current.cost();
17             int r=v/cols,c=v%cols;
18             for(int[] direction:DIRECTIONS) {
19                 int nr=r+direction[0],nc=c+direction[1];if(nr<0||nr>=rows||nc<0||nc>=cols)continue;
20                 int next=nr*cols+nc;long weight=Math.abs((long)heights[r][c]-heights[nr][nc]);
21                 long candidate=Math.max(current.cost(),weight);
22                 if(candidate<distance[next]) {distance[next]=candidate;heap.add(new Entry(candidate,next));}
23             }
24         }
25         throw new AssertionError("nonempty rectangle is connected");
26     }
27     private static boolean reachable(int[][] h,int cols,long limit) {
28         boolean[] seen=new boolean[h.length*cols];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[0]=true;queue.addLast(0);
29         while(!queue.isEmpty()){int v=queue.removeFirst();if(v==seen.length-1)return true;int r=v/cols,c=v%cols;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<h.length&&nc>=0&&nc<cols&&!seen[nr*cols+nc]&&Math.abs((long)h[r][c]-h[nr][nc])<=limit){seen[nr*cols+nc]=true;queue.addLast(nr*cols+nc);}}}return false;
30     }
31     public static long baseline(int[][] heights) {
32         int cols=columns(heights);if(heights.length==0||cols==0)return 0;long low=0,high=4294967295L;
33         while(low<high){long mid=low+(high-low)/2;if(reachable(heights,cols,mid))high=mid;else low=mid+1;}return low;
34     }
35 }
36

    Highlight locates the relevant statement or block; one trace step may summarize several assignments.

    Read the full static trace
    1. Seed a cost-zero snapshot for the source.

      Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.

      input
      []
      rows
      0
      cols
      0
      distance
      []
      frontier
      []
      settled
      []
      phase
      "initial"
      current
      null
    2. Finish after the frontier is exhausted.

      Unreachable labels remain infinite internally; the API uses −1. Network delay is the maximum shortest distance only when every declared vertex is reachable. Empty grid effort is zero.

      input
      []
      rows
      0
      cols
      0
      distance
      []
      frontier
      []
      settled
      []
      phase
      "complete"
      current
      null
    3. Return the documented result without changing caller input.

      Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.

      result
      0

    Zero-column rows

    Input: [[],[]] · Minimum largest jump: 0

    Step 1 of 3: Seed a cost-zero snapshot for the source.

    Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.

    Minimum effort — bottleneck labels on coordinate vertices

    Phase: initial.

    Read-only heights — MIN/MAX are signed-int extremes

    No cell vertices; effort is zero.

    Cell ID = row × column count + column. A label is the largest jump on its best known route, never a sum of jumps.

    Cell bottleneck labels — tentative and final are separate

      Heap proposals — sorted removal order, not internal array order

      Empty.

      Cost snapshots are immutable; improved labels leave older proposals to be discarded later. Strict improvements stop equal-cost cycles from re-enqueueing forever.

      ∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Nonempty rectangular grids are connected; empty-grid effort is zero. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.

      State after this step
      VariableValue
      input[[],[]]
      rows2
      cols0
      distance[]
      frontier[]
      settled[]
      phase"initial"
      currentnull
      See the affected Java block
       1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}};
 4     private record Entry(long cost,int vertex) {}
 5     private static int columns(int[][] heights) {
 6         Objects.requireNonNull(heights,"heights");int cols=heights.length==0?0:heights[0]==null?-1:heights[0].length;
 7         for(int[] row:heights)if(row==null||row.length!=cols)throw new IllegalArgumentException("ragged or null row");return cols;
 8     }
 9     public static long minimumEffort(int[][] heights) {
10         int cols=columns(heights),rows=heights.length;if(rows==0||cols==0)return 0;
11         int n=rows*cols;long[] distance=new long[n];Arrays.fill(distance,Long.MAX_VALUE);distance[0]=0;
12         PriorityQueue<Entry> heap=new PriorityQueue<>(Comparator.comparingLong(Entry::cost).thenComparingInt(Entry::vertex));heap.add(new Entry(0,0));
13         while(!heap.isEmpty()) {
14             Entry current=heap.remove();int v=current.vertex();
15             if(current.cost()!=distance[v])continue;
16             if(v==n-1)return current.cost();
17             int r=v/cols,c=v%cols;
18             for(int[] direction:DIRECTIONS) {
19                 int nr=r+direction[0],nc=c+direction[1];if(nr<0||nr>=rows||nc<0||nc>=cols)continue;
20                 int next=nr*cols+nc;long weight=Math.abs((long)heights[r][c]-heights[nr][nc]);
21                 long candidate=Math.max(current.cost(),weight);
22                 if(candidate<distance[next]) {distance[next]=candidate;heap.add(new Entry(candidate,next));}
23             }
24         }
25         throw new AssertionError("nonempty rectangle is connected");
26     }
27     private static boolean reachable(int[][] h,int cols,long limit) {
28         boolean[] seen=new boolean[h.length*cols];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[0]=true;queue.addLast(0);
29         while(!queue.isEmpty()){int v=queue.removeFirst();if(v==seen.length-1)return true;int r=v/cols,c=v%cols;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<h.length&&nc>=0&&nc<cols&&!seen[nr*cols+nc]&&Math.abs((long)h[r][c]-h[nr][nc])<=limit){seen[nr*cols+nc]=true;queue.addLast(nr*cols+nc);}}}return false;
30     }
31     public static long baseline(int[][] heights) {
32         int cols=columns(heights);if(heights.length==0||cols==0)return 0;long low=0,high=4294967295L;
33         while(low<high){long mid=low+(high-low)/2;if(reachable(heights,cols,mid))high=mid;else low=mid+1;}return low;
34     }
35 }
36

      Highlight locates the relevant statement or block; one trace step may summarize several assignments.

      Read the full static trace
      1. Seed a cost-zero snapshot for the source.

        Distances are tentative; null is infinity, represented by Long.MAX_VALUE in Java. Frontier pairs are [cost snapshot, vertex]. Heap pairs are shown in sorted removal order; deque pairs are exact front-to-back order.

        input
        [[],[]]
        rows
        2
        cols
        0
        distance
        []
        frontier
        []
        settled
        []
        phase
        "initial"
        current
        null
      2. Finish after the frontier is exhausted.

        Unreachable labels remain infinite internally; the API uses −1. Network delay is the maximum shortest distance only when every declared vertex is reachable. Empty grid effort is zero.

        input
        [[],[]]
        rows
        2
        cols
        0
        distance
        []
        frontier
        []
        settled
        []
        phase
        "complete"
        current
        null
      3. Return the documented result without changing caller input.

        Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.

        result
        0

      Test the contract

      1. Input: Plateau and one cell
        Output: 0

        All required jumps are zero or absent.

      2. Input: Empty and zero-column rectangular inputs
        Output: 0

        No row-major vertex may be dereferenced.

      3. Input: Full-int neighboring extremes
        Output: 4294967295

        Tests cast-before-subtraction.

      4. Input: Aliased rows and randomized small grids
        Output: same minimax optimum, unchanged references

        Independent minimax Floyd closure checks the answer.

      5. Input: 100,000-cell corridor
        Output: largest consecutive jump

        The main method avoids recursive depth.

      Common mistakes and counterexamples

      Add edge jumps

      Counterexample: A path with several jumps of two has effort two, regardless of their sum.

      Relax with max(prefix effort, edge jump).

      Return on first target discovery

      Counterexample: A direct or early discovered route can have a worse largest jump than a later detour.

      Return only after popping the target with a current snapshot.

      Subtract heights in int

      Counterexample: MIN to MAX must cost 4294967295, not one.

      Widen one operand before subtraction and take long absolute value.

      Use diagonal neighbors or reuse source as a visited mark

      Counterexample: Both change the declared graph or caller-owned values.

      Generate exactly four directions and store private distance/seen state.

      Follow-ups

      Return an actual minimum-effort route.

      Keep predecessor IDs on strict improvements, reconstruct after final target pop, and verify each step is orthogonal and its largest jump equals the result. Account for O(L) returned coordinates separately.

      Answer many source-target bottleneck queries.

      In an undirected weighted graph, a minimum spanning tree preserves minimum bottleneck values along its unique paths. Prove the cut-based bottleneck property, then preprocess maximum-edge path queries; building one tree per query wastes shared work.

      Minimize total climb instead.

      Replace max with addition for nonnegative per-step climb and retain a suitable shortest-path proof. Define whether downhill is free, absolute, or signed: signed descent can change which algorithms are valid.

      Your Java attempt

      Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

      Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

      No unsaved text changes · 173/20,000 characters

      Self-review

      Use the checklist to test your explanation. Checks apply to this visit.

      Related foundations

      Keep practicing

      Open focused practice

      AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform parity claims.