Group Consecutive Badges
EasyIntervals
Problem
A security desk scanned visitor badge numbers in no particular order, and some badges were scanned more than once. To print a compact report, the desk wants the scanned numbers as ranges.
Return the maximal runs of consecutive integers among badges as [first, last] pairs, sorted by first. A number with no neighbours forms the range [x, x].
Example 1
- Input:
- badges = [4, 2, 3, 9, 7, 8, 12]
- Output:
- [[2, 4], [7, 9], [12, 12]]
2, 3, 4 form one run, 7, 8, 9 another, and 12 stands alone.
Example 2
- Input:
- badges = [5, 5, 6]
- Output:
- [[5, 6]]
The duplicate 5 does not break or extend the run.
Constraints
- 0 ≤ badges.length ≤ 10^5
- -10^9 ≤ badges[i] ≤ 10^9
Hint
Show the first hint
Consecutive numbers are easy to spot once they sit next to each other.
Walkthrough
How to approach it
01Clarify before coding
- Are duplicates possible? Yes; they must not create extra ranges.
- What order should the output use? Ascending by the first number of each range.
- Can the list be empty? Yes → return an empty list.
02Brute force
For each number, repeatedly check whether x + 1 is in the list by scanning it, building runs.
Cost: O(n²) time with linear scans; still O(n log n) at best once the output must be sorted.
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.