Longest run of consecutive strike prices

Question

An options chain lists integer strike prices in no particular order and with possible duplicates. Find the length of the longest run of consecutive integers that all appear (for example, 100, 101, 102). The strikes need not be adjacent in the list.

strikes = [100, 4, 101, 3, 2, 102]
-> 3            # both {2,3,4} and {100,101,102} have length 3

Return the length of the longest consecutive run. Aim for $O(n)$ .

Accepted Answer

Put all strikes in a set for O(1) membership tests. A number starts a run only if its predecessor is absent from the set, otherwise some earlier number already covers this run. From each such start, walk upward while successors exist, measuring the run. Every number is visited by an inner walk at most once, so the total work is linear despite the nested loop. Tracing [100, 4, 101, 3, 2, 102]: 2 starts a run of 2, 3, 4 (length 3) and 100 starts 100, 101, 102 (length 3); the answer is 3. Time O(n), space O(n). The "only start at a run's beginning" check is what keeps it linear, without it, each…

Longest run of consecutive strike prices

Your answer

More Coding questions