Route With a Waiver
Hard About 45 min Free, no account needed
Spend one assisted crossing to make a route's hardest remaining step as small as possible.
The brief
A survey crew must cross a rectangular height map from the top-left cell to the bottom-right cell. They can move up, down, left, or right. A move's effort is the absolute difference between the two cell heights.
The crew has a portable lift that can handle at most one move for them. That move contributes zero effort. Choose a route and where to use the lift so that the largest effort among the remaining moves is as small as possible. Return that smallest possible value. Efforts are not added together, and the lift cannot skip cells.
Implement int Solve(int[][] heights).
For [[0, 10, 11], [3, 5, 20]], return 3. Follow heights 0 → 3 → 5 → 20, whose moves require 3, 2, and 15. Use the lift on the last move, leaving a largest effort of 3. Following the top row instead leaves effort 9 after its best lift placement.
For [[2, 900]], return 0: the lift handles the only move. A map with one cell also returns 0 because no moves are needed.
The map is nonempty and rectangular, with at most 100,000 cells. Heights are integers from 0 through 1,000,000,000. Every cell is traversable. You may revisit cells, but may use the lift only once over the entire route. Do not change the input grid.
Starter code
public class Solution
{
public int Solve(int[][] heights)
{
// Return the least possible maximum effort after waiving at most one move.
throw new System.NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Shortest paths
- Find cheapest routes with Dijkstra-style relaxation over weighted or stateful graphs.
Related katas
- Count Bounded Range Sums Hard Free Count signed subarray totals inside an inclusive band without enumerating quadratic pairs.
- Count Inversions Hard Free Count every out-of-order pair without examining every pair.
- Edit Distance Hard Free Fewest single-character edits turning one word into another.
- Fewest Cache Fetches Hard Free Use tomorrow's requests to find the smallest possible number of cache misses today.