The seed tray ladder

A propagation bench is sown one tray at a time, and every tray gets a sprout count. The open-day shelf wants a run of trays whose counts climb by the same amount each time.

The problem

Trays are sown in a fixed order, and once they germinate the technician counts the sprouts in each and writes the numbers down in that order. For the open day she lines up a run of trays on the front shelf: every tray she puts up must hold exactly step more sprouts than the tray to its left.

She may skip trays, but she may not reorder them — a tray sown later can never sit to the left of a tray sown earlier. step may be negative, giving a run that falls, or zero, giving a run of identical counts.

Report the largest number of trays the shelf can hold.

Input. counts — a list of integers, sprouts per tray in sowing order. step — an integer, the difference every neighbouring pair on the shelf must show.

Output. The length of the longest such run.

Example.

counts = [14, 11, 17, 20, 8, 23], step = 3  ->  4

14, 17, 20, 23 — four trays, skipping 11 and 8. Adding 11 would make five, but 11 was sown after 14, so it cannot sit to the left of it.

Example, with a falling step and with no step at all:

counts = [5, 9, 4, 3, 8, 2], step = -1  ->  4
counts = [6, 6, 6], step = 0            ->  3

5, 4, 3, 2 falls by one each time and keeps its sowing order. With step = 0 every tray holding the same count joins the same run, so all three go up.

Constraints.

• 0 <= len(counts) <= 10^5
• 0 <= counts[i] <= 10^4
• -10^4 <= step <= 10^4

Hints

Approach

Brute force

For each tray, look back over every earlier tray, keep the best run whose last count is v - step, and add one. That is about n²/2 comparisons — five billion on a bench of 100,000 trays. Trying every subset is far worse: 2^n shelves.

The insight

The predecessor is not a choice, it is a value, so the table can be keyed on the sprout count instead of the tray index.

A run ending on a tray of v must have a tray of v - step immediately to its left, so there is nothing to search for — the best run ending on v is one more than the best run ending on v - step. Sweeping in sowing order is what makes that legal: anything the dictionary holds for v - step was written by a tray sown earlier, so the ordering constraint is kept for free.

Algorithm

1. Start with an empty dictionary ladder and longest = 0.
2. Take the trays in sowing order. For a tray holding v:
3. Set ladder[v] = ladder.get(v - step, 0) + 1.
4. Fold ladder[v] into longest.
5. Return longest. An empty bench returns 0.

Complexity

Time O(n) — one dictionary read and one write per tray. Space O(d), where d is the number of distinct counts on the bench, never more than n.

Solution

"""The seed tray ladder — one dictionary entry per sprout count seen so far."""


def solve(counts, step):
    """Longest run of trays, in sowing order, each exactly `step` above the last."""
    # invariant: ladder[v] = length of the longest chain ending on value v
    # among the trays read so far. A chain ending on v extends the best chain
    # that ended on v - step, and nothing else can precede v.
    ladder = {}
    longest = 0
    for sprouts in counts:
        ladder[sprouts] = ladder.get(sprouts - step, 0) + 1
        longest = max(longest, ladder[sprouts])
    return longest

TESTS = [
    (([14, 11, 17, 20, 8, 23], 3), 4),
    (([5, 9, 4, 3, 8, 2], -1), 4),
    (([6, 6, 6], 0), 3),
    (([2, 4, 6, 8], 5), 1),
    (([], 3), 0),
    (([7], 4), 1),
    (([20, 17, 14, 11], 3), 1),
]

Pitfalls

• Reading v + step instead of v - step. That looks forward, so a run is built from trays not yet sown. On the first example it reports 3 (8, 11, 14 read backwards) instead of 4.
• Sorting the counts first. It looks harmless because the run climbs anyway, and it throws away the ordering constraint: sorted, the first example becomes [8, 11, 14, 17, 20, 23] and reports 6.
• Finishing with max(ladder.values()). On an empty bench the dictionary is empty and the call raises instead of returning 0. Track the maximum as you go.

Variants

• Chop on the river gauge — the contiguous cousin: nothing may be skipped, so the state is the direction of the last step rather than a value.
• The bead strand mirror — another longest-subsequence question, but there the predecessor is a real choice, so one dictionary is not enough and the table needs two indices.