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.

Find best downhill ski run from a start

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

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: 1. Return the maximum possible score for a single skier starting at `(sr, sc)`. 2. 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.

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.

Read the full Airbnb Software Engineer interview experience this question came from

Part 1: Maximum Downhill Score for One Skier

You are given a 2D grid of integers where each value is an elevation. A skier starts at cell (sr, sc). From any cell, the skier may move one step up, down, left, or right, but only to a neighboring cell with a strictly lower elevation. The skier may continue moving while the elevation strictly decreases. Return the maximum number of cells that can be visited in a valid downhill run starting from the given cell, including the start cell itself. If the grid is empty, return 0.

Constraints

  • 0 <= R, C
  • If the grid is non-empty, all rows have the same length
  • If the grid is non-empty, 1 <= R * C <= 100000
  • -10^9 <= grid[r][c] <= 10^9
  • If the grid is non-empty, the given start cell is within bounds

Examples

Input: ([[9, 6, 3], [8, 7, 2], [5, 4, 1]], 0, 0)

Expected Output: 7

Explanation: One optimal run is 9 -> 8 -> 7 -> 6 -> 3 -> 2 -> 1, which visits 7 cells.

Input: ([[5, 5], [5, 5]], 0, 0)

Expected Output: 1

Explanation: No move is allowed because all neighboring cells have equal elevation, not lower.

Hints

  1. Think of each cell as a node in a graph. Because you can only move to a strictly lower elevation, cycles are impossible.
  2. Use DFS with memoization so that the best downhill score from each cell is computed only once.

Part 2: Efficient Downhill Scores for Many Skiers

You are given a 2D grid of integers where each value is an elevation. A skier starting at cell (r, c) may move up, down, left, or right to a neighboring cell with a strictly lower elevation. The skier's score is the maximum number of cells that can be visited in a valid downhill run starting from that cell, including the starting cell. Now you are given many starting cells. Return the downhill score for each start efficiently. If the grid is empty, return 0 for every requested start.

Constraints

  • 0 <= R, C
  • If the grid is non-empty, all rows have the same length
  • If the grid is non-empty, 1 <= R * C <= 100000
  • 0 <= len(starts) <= 100000
  • -10^9 <= grid[r][c] <= 10^9
  • If the grid is non-empty, each start cell in starts is within bounds

Examples

Input: ([[9, 6, 3], [8, 7, 2], [5, 4, 1]], [(0, 0), (1, 1), (2, 2)])

Expected Output: [7, 5, 1]

Explanation: The scores are 7 from 9, 5 from 7, and 1 from 1.

Input: ([[5, 5], [5, 5]], [(0, 0), (1, 1)])

Expected Output: [1, 1]

Explanation: No skier can move because no neighboring cell has lower elevation.

Approach

Idea. For every cell we want dp[r][c] = the longest strictly-decreasing downhill run that starts at that cell (counting the cell itself). Once that table is built, each query is just an O(1) lookup. Key observation. A downhill move only goes to a strictly lower neighbor. So if we process cells from lowest elevation to highest, then whenever we handle a cell, every neighbor it can step down to has already been finalized. That removes any need for recursion or memo-on-demand — a single pass in sorted order suffices. Steps in the code. - Empty grid (not grid or not grid[0]) → return [0] for each start. - Initialize dp to all 1s (a run is at least the start cell). - Build cells = [(elevation, r, c)] and cells.sort(), so cells come in increasing elevation (ties broken by coordinates, which is fine — equal elevations are never reachable from each other). - For each (val, r, c) in that order, scan the 4 orthogonal neighbors. If a neighbor's elevation is < val, it was processed earlier, so dp[neighbor] is final; take best = max(best, dp[neighbor] + 1). Store dp[r][c] = best. - For each start, return dp[r][c] (bounds are guaranteed, but the code still guards out-of-range starts with 0). Why correct. The increasing-elevation order is a valid topological order of the DAG whose edges point downhill, so every dependency (dp of a strictly-lower neighbor) is ready when needed. Strict inequality also guarantees the graph is acyclic, so the recurrence is well-defined.

Time complexity: O(R·C·log(R·C) + Q), where Q = len(starts). Sorting the R·C cells by elevation dominates; the DP sweep visits each cell once with O(1) neighbor work, and each of the Q queries is an O(1) lookup. (The previously stored O(R·C + Q) ignored the sort.)

Space complexity: O(R·C) — the dp table plus the list of (elevation, r, c) tuples. No recursion is used (the algorithm is iterative), so there is no extra call-stack term.

Hints

  1. The answer for a starting cell depends only on that cell, not on which skier asks for it.
  2. Memoize the best downhill score from each cell once, then answer each query by reusing that stored value.

Community answers

Answer by psiinyou

package dsa; public class SkiResort { int [][] grid; int[][] dirs = new int[][]{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; int[][] memo; int R; int C; public SkiResort(int[][] grid) { this.grid = grid; R = grid.length; C = grid[0].length; this.memo = new int[R][C]; } public int getScore(int sr, int sc) { return dfs(sr, sc); } public int[] getScores(int[][] skiers) { int[] scores = new int[skiers.length]; for (int i = 0; i < skiers.length; i++) { scores[i] = dfs(skiers[i][0], skiers[i][1]); } return scores; } int dfs(int r, int c){ if(memo[r][c] != 0) return memo[r][c]; int max = 1; for(int i = 0; i < 4; i++){ int nr = r+dirs[i][0]; int nc = c+dirs[i][1]; if(canVisit(nr, nc) && grid[nr][nc] < grid[r][c]){ max = Math.max(max, 1+dfs(nr, nc)); } } memo[r][c] = max; return max; } boolean canVisit(int r, int c){ if(r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return false; return true; } public static void main(String[] args) { System.out.println("--- Running SkiResort Tests ---\n"); // Test Case 1: Standard Snake (Maximum possible path) int[][] mountain1 = { {9, 8, 7}, {4, 5, 6}, {3, 2, 1} }; runTest("TC1: Standard Snake", mountain1, new int[][]{{0, 0}, {1, 1}, {2, 0}}, new int[]{9, 5, 3}); // Test Case 2: Flat Mountain (No valid moves) int[][] mountain2 = { {5, 5, 5}, {5, 5, 5}, {5, 5, 5} }; runTest("TC2: Flat Mountain", mountain2, new int[][]{{0, 0}, {1, 1}, {2, 2}}, new int[]{1, 1, 1}); // Test Case 3: 1x1 Grid (Smallest boundary) int[][] mountain3 = { {10} }; runTest("TC

Answer by Orion

This is not the ski question I encounter in Airbnb interview. The real question was like a top down graph, with edge value and vertices value, question is to get the largest sum.

Loading coding console...

Show the approach

Approach

Problem. Find the longest strictly-decreasing walk (up/down/left/right) that starts at (sr, sc), counting the start cell. This is the classic longest decreasing path in a grid, but we only need the answer for one fixed start cell.

Key idea. Define dp[r][c] = length of the longest strictly-downhill run that begins at (r, c). A run from a higher cell can step into a strictly-lower neighbor, so:

dp[r][c] = 1 + max(dp[nbr]) over neighbors with grid[nbr] < grid[r][c], or just 1 if no lower neighbor exists.

Because every move goes to a strictly smaller value, dp for any cell depends only on cells with smaller elevation. So if we process cells in ascending elevation order, every neighbor we read has already been finalized — no recursion or memo guards needed.

Steps in the code.

  1. Guard empty grids and an out-of-bounds start, returning 0.
  2. Collect all (value, r, c) and sort ascending by value.
  3. Initialize dp = 1 everywhere (a single cell is always a valid run of length 1).
  4. Iterate cells low→high; for each, take 1 + dp[nbr] for every strictly-lower neighbor and keep the max.
  5. Return dp[sr][sc].

Why correct. Processing in ascending order guarantees the four neighbor dp values are final before use, so the recurrence is satisfied for every cell. Equal-elevation neighbors are never traversed (strict <), which correctly handles plateaus — the [[5,5],[5,5]] case yields 1.

Time complexity:
O(R*C log(R*C)) — dominated by sorting all R*C cells by elevation; the DP sweep itself is O(R*C) since each cell inspects 4 neighbors in O(1).
Space complexity:
O(R*C) — the sorted `cells` list and the `dp` grid each hold one entry per cell; the algorithm is iterative, so there is no recursion stack.