0448MediumArrayHash TableBinary SearchDynamic Programming

Longest Constant-Step Firing Ladder

Tracked in this browser only

Trains the technique from

LeetCode 1027Longest Arithmetic Subsequence

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 glass studio keeps readings, the peak kiln temperature of every firing it has run, listed oldest firing first.

A ladder is a selection of two or more firings, kept in the order they appear in readings, such that the change from each selected firing to the next selected one is the same signed amount every time. The firings in a ladder need not be neighbours in the log, and that shared amount may be negative or zero.

Return the number of firings in the longest ladder the log admits.

Examples

Example 1

Input: readings = [412, 60, 205, 118, 350, 176]
Output: 3

The firings reading 60, 118 and 176 rise by 58 from one to the next, so a ladder of three firings is reported.

Example 2

Input: readings = [77, 77, 77, 77]
Output: 4

Every firing reads 77, so the whole log is a ladder whose shared change is 0.

Example 3

Input: readings = [8, 500, 26, 44, 0, 62, 494]
Output: 4

The firings reading 8, 26, 44 and 62 each sit 18 above the one before, giving four firings in log order.

Constraints

2 <= readings.length <= 1000
0 <= readings[i] <= 500

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_ladder(readings: list[int]) -> int:

Java

public int longestLadder(int[] readings)

The intended approach

Time O(n^2) for n firings: every ordered pair is handled once with expected O(1) table work.Space O(n^2) in the worst case, since each of the n tables can hold one entry per earlier firing.

Walk the log left to right and, for every firing, keep a table keyed by step size holding the longest ladder that ends at that firing with that step. For a pair of firings the step is fixed by their difference, so the ladder ending at the later firing is one longer than whatever the earlier firing already recorded for the same step. The tables must be kept per firing, since the same step size can be in play in several unrelated ladders at once.

Pythonentry point: longest_ladder

def longest_ladder(readings):
    n = len(readings)
    # dp[j] maps a step size to the longest ladder that ends at firing j
    # with that step. O(n^2) pairs, each handled in O(1) expected time.
    dp = [dict() for _ in range(n)]
    best = 1
    for j in range(n):
        row = dp[j]
        vj = readings[j]
        for i in range(j):
            step = vj - readings[i]
            run = dp[i].get(step, 1) + 1
            if run > row.get(step, 0):
                row[step] = run
                if run > best:
                    best = run
    return best

The obvious version

Enumerate every subset of firings in log order, check whether its consecutive gaps are all identical, and keep the largest that passes. O(2^n * n).

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_ladder(readings):
    n = len(readings)
    best = 1
    for mask in range(1, 1 << n):
        pick = [readings[i] for i in range(n) if mask >> i & 1]
        if len(pick) == 1:
            continue
        step = pick[1] - pick[0]
        ok = True
        for t in range(len(pick) - 1):
            if pick[t + 1] - pick[t] != step:
                ok = False
                break
        if ok and len(pick) > best:
            best = len(pick)
    return best

How this problem was checked

Reference solution executed against 13 test cases — 13 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