## 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 · Washington DC

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. Example: 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. Follow-ups What is the time and space comp…

Full Details

🔒

Unlock all Karat questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a reported interview question from a karat interview.

It covers the following topics: Matrix, Coding, Graph, Dynamic Programming .

Topics

Matrix Coding Graph Dynamic Programming

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

Question Details

Full Details

About This Question

Topics

More Karat Interview Questions