Longest Unbroken Run
MediumArrays & Hashing
Problem
A ticket printer was supposed to issue consecutive serial numbers, but the stubs ended up in a shuffled pile. You want to know the longest stretch of serials that survived without a gap.
Given an unsorted array nums, return the length of the longest set of values that form a run of consecutive integers x, x + 1, …, x + L - 1. Duplicates count once. Aim for O(n) time.
Example 1
- Input:
- nums = [8, 3, 50, 5, 4, 7, 6, 1]
- Output:
- 6
3, 4, 5, 6, 7, 8 are all present: a run of length 6.
Example 2
- Input:
- nums = [9, 1, -1, 0, 2, 0]
- Output:
- 4
-1, 0, 1, 2; the second 0 adds nothing.
Example 3
- Input:
- nums = []
- Output:
- 0
Constraints
- 0 ≤ nums.length ≤ 10^5
- -10^9 ≤ nums[i] ≤ 10^9
Hint
Show the first hint
Sorting works in O(n log n). What would let you check 'is x + 1 present?' in O(1) without sorting?
Walkthrough
How to approach it
01Clarify before coding
- Do duplicates extend a run? No, a run uses distinct values.
- Must the run be contiguous in the array? No, only in value.
- Empty input? Return 0.
02Brute force
Sort the array, then scan counting adjacent values that differ by exactly 1, skipping equal neighbours.
Cost: O(n log n) time: acceptable in practice, but the problem asks for linear time. The naive 'for each x, look for x + 1 by scanning' is O(n²) or worse.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.