Find best downhill ski run from a start
Quick Overview
This question evaluates algorithmic problem-solving in grid graph traversal and dynamic programming, requiring computation of the maximum-length strictly decreasing path from a start cell plus analysis of time and space complexity.
You are given an R x C grid of integers representing elevations.
A skier starts at a given cell (sr, sc). From a cell, the skier may move up/down/left/right to a neighboring cell with strictly lower elevation. The skier can continue moving as long as the elevation strictly decreases.
Define the skier’s score as the maximum number of cells that can be visited in a valid downhill run starting from (sr, sc) (including the start cell).
Tasks:
-
Return the maximum possible score for a single skier starting at
(sr, sc). - Follow-up: if you are given many skiers (a list of starting cells), return the score for each efficiently.
State your time/space complexity for both the single-skier and multi-skier versions.