## Problem You are given an `m x n` matrix where each cell represents the elevation at that point. A skier can move from a cell to an adjacent cell (up, down, left, right) only if the destination is strictly lower. Find the length of the longest such path. ```python def longest_downhill(matrix: list[list[int]]) -> int: pass ``` **Example:** ``` matrix = [ [9, 9, 4], [6, 6, 8], [2, 1, 7] ] Longest path: 9->6->2->1 (length 4) or 9->6->1 (length 3) Output: 4 ``` ## Approach Use memoized DFS. For each cell, `dfs(r, c)` returns the longest path starting there. A cell's result depends only on strictly lower neighbors, so there are no cycles — memoization is safe. ```python from functools import lru_cache def longest_downhill(matrix): m, n = len(matrix), len(matrix[0]) @lru_cache(maxsize=None) def dfs(r, c): best = 1 for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc = r+dr, c+dc if 0<=nr<m and 0<=nc<n and matrix[nr][nc] < matrix[r][c]: best = max(best, 1 + dfs(nr, nc)) return best return max(dfs(r,c) for r in range(m) for c in range(n)) ``` ## Follow-ups 1. What is the time and space complexity of this approach? 2. How would you find the actual path (not just the length)? 3. What if diagonal moves are also allowed? 4. What if you can move to a neighbor that is equal in elevation (not strictly lower)?

InterviewDB Question

Snowy Mountain: Find the Longest Downhill Path in a 2D Elevation Grid

Question Details

Problem You are given an m x n matrix where each cell represents the elevation at that point. A skier can move from a cell to an adjacent cell (up, down, left, right) only if the destination is strictly lower. Find the length of the longest such path…

Full Details

🔒

Unlock full leaked content

Full insider details, leaked discussions, and candidate experiences.

Get Premium →

Topics

Coding

← All Karat questions Karat Software Engineer Questions → All Dynamic Programming Questions →

Snowy Mountain: Find the Longest Downhill Path in a 2D Elevation Grid

Question Details

Full Details

Topics

More from Karat