6 lines in Python

• Three versions of the same algorithm, all take O(n) time.

Solution 1

Just collect the ranges, then format and return them.

``````def summaryRanges(self, nums):
ranges = []
for n in nums:
if not ranges or n > ranges[-1][-1] + 1:
ranges += [],
ranges[-1][1:] = n,
return ['->'.join(map(str, r)) for r in ranges]
``````

Solution 2

A variation of solution 1, holding the current range in an extra variable `r` to make things easier. Note that `r` contains at most two elements, so the `in`-check takes constant time.

``````def summaryRanges(self, nums):
ranges, r = [], []
for n in nums:
if n-1 not in r:
r = []
ranges += r,
r[1:] = n,
return ['->'.join(map(str, r)) for r in ranges]
``````

Solution 3

A tricky short version.

``````def summaryRanges(self, nums):
ranges = r = []
for n in nums:
if `n-1` not in r:
r = []
ranges += r,
r[1:] = `n`,
return map('->'.join, ranges)
``````

Three people asked about them in the comments, so I'll also explain it here as well. I have these two basic cases:

``````ranges += [],
r[1:] = n,
``````

Why the trailing commas? Because it turns the right hand side into a tuple and I get the same effects as these more common alternatives:

``````ranges += [[]]
or
ranges.append([])

r[1:] = [n]
``````

Without the comma, ...

• `ranges += []` wouldn't add `[]` itself but only its elements, i.e., nothing.
• `r[1:] = n` wouldn't work, because my `n` is not an iterable.

Why do it this way instead of the more common alternatives I showed above? Because it's shorter and faster (according to tests I did a while back).

• excellent solution!

• Thanks for your share .sorry I'm a noob. Could you tell me how those commas work?

• Backquotes calls the `__repr__()` , so the result would be a string rather than a int. TIL.

• So brilliant solutions. Even better if complexity analysis provided. I think it is O(N) for solution 1 and O(N^2) for solution 2 & 3. Excuse me if I was wrong :)

• Hi, everbird. I think all the 3 solutions are of `O(n)` time complexity since each element in `nums` is visited exactly once in all of them.

• @jianchao Yes each element in `nums` is visited only once but `in` operation for a list is also O(N)

• Hi, everbird. I miss that part. I guess you are correct :)

• @feiyuzhang Which commas? Like in `ranges += r,`? That creates a tuple so that `r` is added as an element itself rather than its elements being added. Same as `ranges += [r]` or `ranges.append(r)`, but shorter and faster (according to some tests I did a while back).

• @everbird and @jianchao.li.fighter All three are O(n). The `in` operator does take linear time, but note that my list is at most two elements long! So the `in` takes O(1) for it. I have added a note to the question.

• Hi, StefanPochmann. Thank you for your explanations. What about `r[1:] = n,`?

• That's the best part of the whole solution :-). It replaces the slice on the left side by the (elements of the) tuple on the right side. So it replaces everything after the first element in `r` (or everything, in case `r` is empty) by just `n`. That is, `[]` becomes `[n]` (setting the start value of the range), and `[x]` and `[x,y]` both become `[x,n]` (adding/updating the end value of the range).

• Hi, StefanPochmann. Thank you for your nice explanations. In fact, I have experimented with your code for some time and find it to be really clever and involve some subtle Python features.

Well, I have once replaced `ranges += r,` to be `ranges += [],` and found it to be wrong. Well, is it a subtle python feature about reference?

• You mean you did only that change? Well that means you add an empty list to `ranges` and then never touch it again (until the final "stringification"), instead only touching the `r` which has nothing to do with the added list. No, that's not subtle, that's a misunderstanding of Python basics :-P

• Hi, StefanPochman. I guess that the `r` added to `ranges` will also be altered once `r` itself is altered, right? Thank you.

• Well, kinda. But it won't "also" be altered. It's not a second list, magically connected to the first. It's the exact same list. The same object.

• Ok, I got it. Great thanks for your patient guidance :-)

• for solution one, the code ranges[-1][1:] = n is very strange, if len(ranges[-1]) == 0， why can you do that? isn't it out of range?

• That's part of why I like it so much :-) Yes, it's out of range, but like this page puts it, "out of range slice indexes are handled gracefully" (search that text on that page to see examples).

• thanks for replaying, if i remove the comma (,), the program will dump by out of range

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.