0176HardArrayDynamic ProgrammingDepth-First SearchBreadth-First SearchGraph TheoryTopological SortMemoizationMatrixDirected Acyclic Graph

Tallest Stack Ascent

Tracked in this browser only

Write code

Trains the technique from

LeetCode 329Longest Increasing Path in a Matrix

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A container yard is laid out as a rectangular grid of bays. heights[r][c] is how many containers are stacked in the bay at row r, column c.

A gantry inspector walks the yard bay by bay. From a bay the inspector may step to a bay sharing an edge with it, up, down, left or right, and only if that bay's stack is strictly taller than the one just left. Diagonal steps are not possible, and the walk may not leave the yard.

The inspector picks the starting bay. Return the greatest number of bays a single walk can cover, counting the starting bay itself.

Examples

Example 1

Input: heights = [[1, 5, 9], [2, 4, 8], [3, 7, 6]]
Output: 5

Starting at the bay holding 1 the inspector can reach 2, then 4, then 5, then 9, covering five bays. No walk covers six.

Example 2

Input: heights = [[4, 4], [4, 4]]
Output: 1

Every stack is the same height, so no step is ever allowed and the walk is the starting bay on its own.

Example 3

Input: heights = [[2, 3, 6], [5, 4, 7]]
Output: 4

From 2 the inspector goes to 3, then down to 4, then left to 5, covering four bays. The route through 6 and 7 also stops at four.

Constraints

rows == heights.length
cols == heights[r].length
1 <= rows, cols <= 200
0 <= heights[r][c] <= 2^31 - 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_ascent(heights: list[list[int]]) -> int:

Java

public int longestAscent(int[][] heights)

The intended approach

Time O(rows * cols)Space O(rows * cols)

Since every step lands on a strictly taller stack, no walk can revisit a bay, and the longest walk starting from a bay depends only on that bay. Search outwards from each bay with an explicit stack of pending bays and cache the answer the first time it is settled, so each bay is expanded once and its four neighbours are consulted once. The reply for a bay is one plus the best reply among its taller neighbours. Driving the search from a stack rather than nested calls keeps a yard whose longest walk covers every bay within reach.

Pythonentry point: longest_ascent

def longest_ascent(heights):
    # Settle each bay once with an explicit stack, so a yard 200 bays deep in
    # every direction cannot overrun any call depth. A bay is pushed twice: the
    # first visit schedules its taller neighbours, the second reads their
    # settled answers and records one plus the best of them.
    # Time O(rows * cols): every bay is settled once and each of its four
    # neighbours is consulted a fixed number of times. Space O(rows * cols)
    # for the cache and for the pending stack.
    rows = len(heights)
    cols = len(heights[0])
    cached = [[0] * cols for _ in range(rows)]
    steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    answer = 0
    for srow in range(rows):
        for scol in range(cols):
            pending = [(srow, scol, False)]
            while pending:
                row, col, revisit = pending.pop()
                if cached[row][col]:
                    continue
                if not revisit:
                    pending.append((row, col, True))
                    for drow, dcol in steps:
                        nrow, ncol = row + drow, col + dcol
                        if 0 <= nrow < rows and 0 <= ncol < cols:
                            if (heights[nrow][ncol] > heights[row][col]
                                    and not cached[nrow][ncol]):
                                pending.append((nrow, ncol, False))
                    continue
                best = 1
                for drow, dcol in steps:
                    nrow, ncol = row + drow, col + dcol
                    if 0 <= nrow < rows and 0 <= ncol < cols:
                        if heights[nrow][ncol] > heights[row][col]:
                            reach = 1 + cached[nrow][ncol]
                            if reach > best:
                                best = reach
                cached[row][col] = best
            if cached[srow][scol] > answer:
                answer = cached[srow][scol]
    return answer

The obvious version

Visit the bays in order of decreasing stack height. When a bay is handled every taller neighbour is already final, so its answer can be filled in with a plain scan of the four neighbours. No recursion and no cache lookups.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_longest_ascent(heights):
    rows = len(heights)
    cols = len(heights[0])
    order = []
    for row in range(rows):
        for col in range(cols):
            order.append((heights[row][col], row, col))
    order.sort(reverse=True)
    span = [[1] * cols for _ in range(rows)]
    steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    for value, row, col in order:
        for drow, dcol in steps:
            nrow, ncol = row + drow, col + dcol
            if 0 <= nrow < rows and 0 <= ncol < cols:
                if heights[nrow][ncol] > value and 1 + span[nrow][ncol] > span[row][col]:
                    span[row][col] = 1 + span[nrow][ncol]
    return max(max(row) for row in span)

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in