Longest increasing run with a step limit: A Sample Coding Interview Solution

The coding question

You're given a list of integers and a number k. Return the length of the longest subsequence where every element is bigger than the one before it, by at most k.

Ask a few questions first

Ask	What we'll assume
Subsequence or a run of neighbors?	Subsequence. You can skip elements, but you keep their order.
Does 'bigger' mean strictly bigger?	Yes. Each step goes up by 1 to k. Equal values don't count.
Can numbers be negative?	Yes, any integers. k is at least 1.
How long is the list?	Up to about 100,000, so O(n²) is too slow.
What about an empty list?	Return 0.

A couple of examples

Input	Output
nums = [4, 2, 1, 4, 3, 4, 5, 8, 15], k = 3	5 (1, 3, 4, 5, 8)
nums = [7, 4, 5, 1, 8, 12, 4, 7], k = 5	4 (4, 5, 8, 12)
nums = [1, 5], k = 1	1

Start with brute force

Classic dynamic programming: for each position i, the best run ending there is 1 plus the best run ending at any earlier j where nums[i] - nums[j] is between 1 and k. Check every earlier j.

Cost: O(n²) time and O(n) space. That's 10 billion steps for 100,000 numbers.

A better way

The usual fast trick for longest increasing subsequence uses binary search over 'smallest ending value per length'. That breaks here, because the step limit means a small ending value isn't always better. So we need something else.

Flip the question around. Instead of 'which earlier positions work?', ask 'what's the best run ending at any value from x - k to x - 1?' If we keep a table indexed by value, that's a max over a range of the table.

A segment tree answers 'max over a range' and 'update one spot' in O(log n) each. It's a tree where each node holds the max of its two children. Values can be huge or negative, so sort the distinct values first and index the tree by their position in that sorted list.

Sort the distinct values. Each value now has a slot from 0 to m - 1.
Build a segment tree over those slots, all zeros. Slot v will hold the longest run seen so far that ends at value v.
Walk nums in order. For each x, use binary search to find the slots for values from x - k up to x - 1.
Ask the tree for the max in that range, add 1, and save it in x's slot if it's bigger.
The answer is the biggest length we saved.

The code

solution.pypython

from bisect import bisect_left


def longest_run(nums, k):
    values = sorted(set(nums))
    size = len(values)
    tree = [0] * (2 * size)

    def query(lo, hi):
        # Best length among values[lo:hi].
        best = 0
        lo += size
        hi += size
        while lo < hi:
            if lo % 2 == 1:
                best = max(best, tree[lo])
                lo += 1
            if hi % 2 == 1:
                hi -= 1
                best = max(best, tree[hi])
            lo //= 2
            hi //= 2
        return best

    def update(i, length):
        i += size
        tree[i] = max(tree[i], length)
        i //= 2
        while i >= 1:
            tree[i] = max(tree[2 * i], tree[2 * i + 1])
            i //= 2

    answer = 0
    for x in nums:
        i = bisect_left(values, x)
        lo = bisect_left(values, x - k)
        length = query(lo, i) + 1
        update(i, length)
        answer = max(answer, length)
    return answer

	Cost	Why
Time	O(n log n)	Sorting, then one binary search, one query and one update per number
Space	O(n)	The sorted values and a tree twice that size

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

An empty list returns 0, and the loop never runs.
Repeated values like [3, 3, 3]: the range for 3 stops before 3 itself, so the answer is 1.
A list that only goes down returns 1.
Negative numbers work, since we only use positions in the sorted list.
A gap bigger than k breaks a run, like [1, 5] with k = 1.

Common mistakes

Using the patience sorting trick from plain longest increasing subsequence. It ignores the step limit and gives wrong answers.
Including x itself in the range, which lets equal values chain together.
Indexing the tree by raw value. With values up to a billion, or negatives, that won't fit.
Saving the new length without taking the max, which can overwrite a longer run from an earlier copy of the same value.

Follow-up questions

What if values are small, like 0 to 100,000?

Skip sorting and index the tree by value directly. Same complexity, a bit simpler.

Can you return the subsequence itself?

Store the position of the best run in the tree along with its length, keep a 'previous' pointer for each position, and walk back from the end.

What if the step can be up or down by at most k?

Then it's not increasing anymore. Query the range x - k to x + k excluding x, using the same tree.

How the time adds up

Minutes	What you're doing
0–5	Ask questions and agree on examples
5–10	Brute force O(n²) DP
10–20	Turn it into a range max over values
20–35	Write the segment tree and the loop
35–40	Test with the examples and edge cases
40–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Amazon.