Three versions of the same algorithm, all take O(n) time.
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]
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]
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)
About the commas :-)
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:] = nwouldn't work, because my
nis 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).
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)
@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.
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,
[n] (setting the start value of the range), 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.
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).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.