[Top Interview 150] 228. Summary Ranges

Solution)

def summaryRanges(self, nums: List[int]) -> List[str]:
        if not nums: return []

        res = []
        l, r = 0, 0

        while r < len(nums)-1:
            if nums[r+1] != nums[r]+1:
                if l == r:
                    res.append(str(nums[r]))
                else:
                    res.append(str(nums[l]) + "->" + str(nums[r]))
                
                l = r+1
            
            r += 1
        
        
        if l == r:
            res.append(str(nums[r]))
        else:
            res.append(str(nums[l]) + "->" + str(nums[r]))

        return res

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)

Explanation)

I used two pointers that will determine small ranges within nums.
 
Since we're comparing nums[r+1] with nums[r], we have to be cautious of index-out-of-range error. Thus, we'll only determine the ranges until r is less than len(nums)-1.
 
After the loop above, we need to check the last element's range and add it to a list accordingly.

Initialization)

Since my approach does not address a case where nums is empty, I'll simply return an empty list if nums is empty.
 
We'll make res an empty list which will save string ranges.
left and right pointers will indicate the ends of small ranges.
 

def summaryRanges(self, nums: List[int]) -> List[str]:
        if not nums: return []

        res = []
        l, r = 0, 0

while loop)

To check if certain numbers are continuous, there are multiple ways of doing it but I'm going to check if nums[r+1] is the same as nums[r]+1.
 
If they are the same, [l, r+1] is a small range. Thus r will be increased by 1 until a number out of the small range is found.
 
If a number that is out of the small range is found (if nums[r+1] != nums[r]+1), then we'll check how many elements are in that small range. If l and r are the same, that means there only exists one element in that range. If l and r are not the same, that means there are multiple elements in that range. 
 

how many elements in a small range

 
If there is a single element in a small range, we simply append string version of nums[r].
If there are multiple elements, we need to append start of the range(nums[l) and the end of the range(nums[r]) with an arrow sign.
 
We continue doing this until r < len(nums)-1 to prevent index-out-of-range error.
 

def summaryRanges(self, nums: List[int]) -> List[str]:
        if not nums: return []

        res = []
        l, r = 0, 0

        while r < len(nums)-1:
            if nums[r+1] != nums[r]+1:
                if l == r:
                    res.append(str(nums[r]))
                else:
                    res.append(str(nums[l]) + "->" + str(nums[r]))
                
                l = r+1
            
            r += 1

Checking the last element in nums)

To prevent an index-out-of-range error, we only checked the ranges until the -2nd element. Now we need to check -1st element.
 
There are two cases regarding the last element.
1) It's the only element consisting the small range
2) It's one of the multiple elements consisting the small range
 
We need to distinguish these, because there is a difference in appending the ranges to res.
 
To distinguish these, we'll check if l is the same as r.
If they are the same, it means the last element is the only element in a small range.
If they are not the same, the last element is part of the elements in a small range.
 

Distinguishing the last element

 
After we completed the res, we'll return res.
 

def summaryRanges(self, nums: List[int]) -> List[str]:
        if not nums: return []

        res = []
        l, r = 0, 0

        while r < len(nums)-1:
            if nums[r+1] != nums[r]+1:
                if l == r:
                    res.append(str(nums[r]))
                else:
                    res.append(str(nums[l]) + "->" + str(nums[r]))
                
                l = r+1
            
            r += 1
        
        
        if l == r:
            res.append(str(nums[r]))
        else:
            res.append(str(nums[l]) + "->" + str(nums[r]))

        return res

 
 
I'm not a fan of this problem. Unlike other problems, this felt more like a hard coding instead of using algorithms and data structures. There may be other smart ways to solve this, but the solutions that got top votes in LeetCode also used similar approaches.