6 lines in Python


  • 47

    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)
    

    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:] = 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).


  • 0

    excellent solution!


  • 0
    F

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


  • 0
    E

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


  • 0
    E

    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 :)


  • 0

    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.


  • 0
    E

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


  • 0

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


  • 1

    @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).


  • 0

    @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.


  • 0

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


  • 2

    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).


  • 0

    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?


  • 1

    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


  • 0

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


  • 0

    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.


  • 0

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


  • 0
    L

    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?


  • 0

    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).


  • 0
    L

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


Log in to reply
 

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