Summary Ranges
Easy · Intervals · Array
Problem
You are given a sorted array nums of distinct integers. Describe it with the fewest ranges that cover every number in nums and nothing else, in increasing order.
Return the ranges as strings: a range from a to b is written "a->b" when a != b, and "a" when a == b.
Examples
Input: nums = [-2,-1,0,4,6,7] Output: ["-2->0","4","6->7"]
-2, -1, 0 and 6, 7 are runs of consecutive values; 4 stands alone.
Input: nums = [3,5,9] Output: ["3","5","9"]
No two values are consecutive, so every range is a single number.
Input: nums = [] Output: []
No numbers, no ranges.
Constraints
- 0 <= len(nums) <= 20
- -2^31 <= nums[i] <= 2^31 - 1
- All values are distinct
- nums is sorted in increasing order
Approaches
- Merge touching ranges until none are left — time O(n²), space O(n)
Follow-up
What if the numbers arrive one at a time and you must report the ranges after each one? Keep the ranges in a sorted structure keyed by their starts; a new number joins the range ending just before it, the one starting just after it, or both, in O(log n) each.
Related problems
Start free on Cariara · Coding problems · System design studio
