DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Summary Ranges

easyIntervals

Problem statement

You get a sorted array nums of unique integers. Describe it as the shortest list of ranges that covers every number exactly once and nothing else.

Write a range covering a through b as "a->b" when a != b, and as just "a" when it holds a single number. Return the ranges in ascending order. An empty array gives an empty list.

Examples

Example 1

Input: nums = [0, 1, 2, 5, 7, 8]

Output: ["0->2", "5", "7->8"]

Explanation: 0, 1, 2 are consecutive; 5 stands alone; 7 and 8 are consecutive.

Example 2

Input: nums = [-3, -1, 0, 1, 4]

Output: ["-3", "-1->1", "4"]

Explanation: Negative numbers work the same way.

Hints

Approach

Walk the sorted array once with a pointer to the start of the current range.

  1. Let i index the start of the current range.
  2. Move j forward from i while nums[j + 1] == nums[j] + 1.
  3. nums[i]..nums[j] is one range. Format it as "a" or "a->b".
  4. Set i = j + 1 and repeat until i passes the end.

Each element is visited once and only the output list is allocated.

ComplexityTime O(n)Space O(1) extra
Python
class Solution:
def summaryRanges(self, nums: list[int]) -> list[str]:
out = []
i = 0
while i < len(nums):
j = i
while j + 1 < len(nums) and nums[j + 1] == nums[j] + 1:
j += 1
out.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
i = j + 1
return out

Follow-up questions

  • Do the reverse: parse "0->2,5,7->8" back into the list of numbers.
  • Given the range [lower, upper], return the ranges that are missing from nums.

Frequently asked questions

Compressing lists of numbers for humans: turning a list of open ports into 8000->8010, 9090, summarising which host indices in a fleet failed a check, or printing allocated IP octets. Tools like taskset and cgroup cpuset files use the same range notation for CPU lists.

With x = Integer.MAX_VALUE, x + 1 overflows to Integer.MIN_VALUE. If the minimum value is also in the input, an int version would join the two extremes into one range. Widening to long avoids it.

For the one-pass version, yes: it only compares neighbours. The set-based version works on unsorted input too, as long as you sort the output ranges afterwards.