Quick Overview

A grid coding problem where a walker repeatedly climbs to the highest strictly higher of its eight neighbors, with ties broken by row and then column, and you count the starting cells that end on the global maximum height. It tests careful simulation, tie handling and reusing results across starting cells.

Count Grid Cells Whose Steepest-Ascent Walk Reaches the Global Peak

Company: Duolingo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are given a grid of heights. A walker placed on any cell climbs by a fixed rule: it looks at the up to eight cells around it (horizontal, vertical and diagonal neighbors), and if any of them is strictly higher than its current cell, it moves to the highest such neighbor. When several higher neighbors share that highest height, it moves to the one with the smallest row index, and among those to the one with the smallest column index. When no neighbor is strictly higher, the walker stops. Return how many starting cells lead the walker to a cell with the grid's global maximum height. If several cells share the global maximum, ending on any of them counts. ### Function Signature ```python def count_starts_reaching_peak(heights: list[list[int]]) -> int: ``` ### Rules - Row `0` is the top row and column `0` is the leftmost column. The neighbors of `(r, c)` are the cells `(r + dr, c + dc)` with `dr` and `dc` each in `{-1, 0, 1}`, not both `0`, that lie inside the grid. - The walker only ever moves to a strictly higher cell, never to a cell of equal height. - Every cell is a starting cell. A cell that already has the global maximum height counts, because the walker is already on a highest point. - A starting cell counts if and only if the walker stops on a cell whose height equals the global maximum. ### Constraints - `1 <= len(heights) <= 200` and `1 <= len(heights[0]) <= 200`; all rows have the same length. - `0 <= heights[i][j] <= 10^9` - The answer is between `1` and the number of cells. ### Examples **Example 1** ```text Input: heights = [[5, 1, 2, 3], [4, 0, 1, 9], [3, 2, 1, 8]] Output: 6 ``` The global maximum is 9 at `(1, 3)`. The cell `(0, 0)` with height 5 has no higher neighbor, so it is a dead end: the walks from `(0, 1)`, `(1, 0)`, `(1, 1)`, `(2, 0)` and `(2, 1)` all climb to `(0, 0)` and stop there, and `(0, 0)` itself does not count. The other six cells, `(0, 2)`, `(0, 3)`, `(1, 2)`, `(1, 3)`, `(2, 2)` and `(2, 3)`, end at `(1, 3)`. **Example 2** ```text Input: heights = [[5, 0, 0, 0], [0, 1, 5, 6], [0, 0, 0, 0]] Output: 7 ``` From `(1, 1)`, the highest higher neighbors are `(0, 0)` and `(1, 2)`, both with height 5. The tie goes to the smaller row, `(0, 0)`, which is a dead end, so `(1, 1)` does not count; neither do `(0, 0)`, `(0, 1)`, `(1, 0)` and `(2, 0)`, which also end at `(0, 0)`. From `(2, 1)`, the cell `(0, 0)` is not a neighbor, so the walker climbs to `(1, 2)` and then to the peak 6 at `(1, 3)`. The cells that count are `(0, 2)`, `(0, 3)`, `(1, 2)`, `(1, 3)`, `(2, 1)`, `(2, 2)` and `(2, 3)`. **Example 3** ```text Input: heights = [[2, 9, 1, 0], [9, 0, 3, 4]] Output: 6 ``` Both `(0, 1)` and `(1, 0)` have the global maximum 9, and both count. From `(0, 0)` and from `(1, 1)`, the two 9s tie as the highest higher neighbors, and the walker moves to `(0, 1)`. The cells `(0, 2)` and `(1, 2)` climb directly to `(0, 1)`. The cell `(1, 3)` with height 4 is a local peak, and `(0, 3)` climbs to it, so those two cells do not count.

Overview: A grid coding problem where a walker repeatedly climbs to the highest strictly higher of its eight neighbors, with ties broken by row and then column, and you count the starting cells that end on the global maximum height. It tests careful simulation, tie handling and reusing results across starting cells.

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

A grid `heights` of non-negative integers describes a terrain. Row `0` is the top row and column `0` is the leftmost column. A walker placed on a cell climbs by a fixed rule. From its current cell `(r, c)` it looks at the up to eight neighbors `(r + dr, c + dc)` with `dr` and `dc` each in `{-1, 0, 1}`, not both `0`, that lie inside the grid (horizontal, vertical and diagonal neighbors; positions outside the grid are not neighbors). If any neighbor is strictly higher than the current cell, the walker moves to the highest such neighbor. When several higher neighbors share that highest height, it moves to the one with the smallest row index, and among those to the one with the smallest column index. When no neighbor is strictly higher, the walker stops. The walker never moves to a cell of equal height. Every cell is a starting cell. A starting cell counts if and only if the walker started there stops on a cell whose height equals the grid's global maximum height. If several cells share the global maximum, stopping on any of them counts; a cell that already has the global maximum height counts, because the walker is already on a highest point. Return the number of starting cells that count, as an integer. ### Example 1 ```text Input: heights = [[5, 1, 2, 3], [4, 0, 1, 9], [3, 2, 1, 8]] Output: 6 ``` The global maximum is 9 at `(1, 3)`. The cell `(0, 0)` with height 5 has no higher neighbor, so it is a dead end: the walks from `(0, 1)`, `(1, 0)`, `(1, 1)`, `(2, 0)` and `(2, 1)` all climb to `(0, 0)` and stop there, and `(0, 0)` itself does not count. The other six cells, `(0, 2)`, `(0, 3)`, `(1, 2)`, `(1, 3)`, `(2, 2)` and `(2, 3)`, end at `(1, 3)`. ### Example 2 ```text Input: heights = [[5, 0, 0, 0], [0, 1, 5, 6], [0, 0, 0, 0]] Output: 7 ``` From `(1, 1)`, the highest higher neighbors are `(0, 0)` and `(1, 2)`, both with height 5. The tie goes to the smaller row, `(0, 0)`, which is a dead end, so `(1, 1)` does not count; neither do `(0, 0)`, `(0, 1)`, `(1, 0)` and `(2, 0)`, which also end at `(0, 0)`. From `(2, 1)`, the cell `(0, 0)` is not a neighbor, so the walker climbs to `(1, 2)` and then to the peak 6 at `(1, 3)`. The cells that count are `(0, 2)`, `(0, 3)`, `(1, 2)`, `(1, 3)`, `(2, 1)`, `(2, 2)` and `(2, 3)`. ### Constraints - `1 <= len(heights) <= 200` and `1 <= len(heights[0]) <= 200`; all rows have the same length. - `0 <= heights[i][j] <= 10^9`. Every height fits in a 32-bit signed integer; no input or output value exceeds `2^31 - 1`. - The answer is between `1` and the number of cells.

Constraints

  • 1 <= len(heights) <= 200 and 1 <= len(heights[0]) <= 200; all rows have the same length.
  • 0 <= heights[i][j] <= 10^9 (every height fits in a 32-bit signed integer; no value exceeds 2^31 - 1).
  • The answer is between 1 and the number of cells.

Examples

Input: ([[0]],)

Expected Output: 1

Explanation: Minimum 1x1 grid with height 0: the only cell is the global maximum, so it counts.

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

Expected Output: 6

Explanation: Source example 1: the dead end 5 at (0, 0) captures (0, 1), (1, 0), (1, 1), (2, 0), (2, 1) and itself; the other six cells end at the 9 at (1, 3).

Hints

  1. The walker only ever moves to a strictly higher cell, so a walk can never revisit a cell and always stops after finitely many moves.
  2. Where the walker goes next depends only on the cell it is standing on, so two walks that ever share a cell end at the same place.
  3. Ties among the highest higher neighbors go to the smaller row first and only then to the smaller column; positions outside the grid are never neighbors.

Loading coding console...

Show the approach

Approach

Each cell's move depends only on that cell and its neighbors, so first compute next[cell] for every cell. Scan the eight neighbors in row-major order (dr = -1, 0, 1, and within each dr, dc = -1, 0, 1), skipping the cell itself and any position outside the grid, and start with the cell's own height as the best height. A neighbor replaces the current choice only when its height is strictly greater than the best seen so far. Because the scan visits smaller rows first and, within a row, smaller columns first, and a later neighbor wins only when strictly higher, the kept neighbor is the highest strictly higher neighbor with the smallest row, then the smallest column, which is exactly the tie rule. If no neighbor is strictly higher, next is -1 and the cell is a stopping point. Invariant: every move goes to a strictly higher cell, so the next pointers contain no cycle, every walk visits distinct cells, and every walk ends at a stopping point after at most rows*cols - 1 moves. A stopping point reaches the peak exactly when its height equals the global maximum. Walks that meet at a cell share the rest of their route, so a cell's outcome equals its successor's outcome. To resolve every start, follow next pointers until reaching a cell whose outcome is already known or a stopping point, then copy that outcome to every cell on the path just walked; each cell is resolved once, so the total work is linear. The answer is the number of cells whose outcome is reaching the peak. Edge cases: a 1x1 grid and an all-equal grid return the number of cells, because nobody moves and every cell already holds the global maximum; equal-height neighbors are never moved to, so a plateau of non-maximum cells is a dead end; cells on edges and corners have fewer neighbors and indexes never wrap around the grid.

Time complexity:
O(R * C)
Space complexity:
O(R * C)