Skip to content
Katabench
Try free

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

C#
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.

C# coding challenges →

What it practices

Shortest paths
Find cheapest routes with Dijkstra-style relaxation over weighted or stateful graphs.

Related katas