Leetcode – Summary Ranges Solution in Python

Spread the love

Introduction

The Summary Ranges problem is a popular coding question found on LeetCode. In this article, we will explore the problem statement, analyze different approaches to solve this problem, and implement solutions using Python. We will also discuss time and space complexity and take a look at potential optimizations.

Problem Statement

The problem is as follows:

Given a sorted integer array nums, without duplicates, return the summary of its ranges.

For example, given nums = [0,1,2,4,5,7], return ["0->2","4->5","7"].

Input

  • An array of n integers nums where 0 <= n <= 100. The array is sorted in ascending order and does not contain duplicates.

Output

  • A list of strings representing the ranges.

Approach 1: Simple Linear Iteration

One of the simplest ways to solve this problem is by iterating through the array and keeping track of the start of a range. As we iterate through the array, if the current number is not exactly one more than the previous number, this indicates the end of the current range. We can then add the range to our result list and update the start of the new range to the current number.

def summaryRanges(nums):
    # If the input array is empty, return an empty array
    if not nums:
        return []

    # Initialize the result array
    result = []
    
    # Initialize the start of the range to the first number
    start = nums[0]

    # Iterate through the array starting from the second number
    for i in range(1, len(nums)):
        # If the current number is not one more than the previous number,
        # this is the end of the current range
        if nums[i] != nums[i-1] + 1:
            # If the start is less than the previous number, the range contains
            # multiple numbers
            if start < nums[i-1]:
                result.append(f"{start}->{nums[i-1]}")
            # Otherwise, the range only contains one number
            else:
                result.append(str(start))
            # Update the start of the range
            start = nums[i]

    # Add the final range to the result array
    if start < nums[-1]:
        result.append(f"{start}->{nums[-1]}")
    else:
        result.append(str(start))

    return result

Time Complexity

The time complexity of this algorithm is O(n) since we iterate through the array once.

Space Complexity

The space complexity is O(n) as the result list can have a size proportional to the input array in the worst case.

Approach 2: Two Pointers

Another way to solve this problem is by using two pointers. One pointer keeps track of the start of a range, and the other pointer keeps track of the end of a range. While iterating through the array, if the difference between the end and start pointers is equal to the difference between the numbers at these indices, we move the end pointer one step ahead. Otherwise, we add the current range to the result list and move both pointers to the current position.

def summaryRanges(nums):
    # If the input array is empty, return an empty array
    if not nums:
        return []

    # Initialize the result array
    result = []
    
    # Initialize two pointers at the start of the array
    start = end = 0

    # Iterate through the array
    while end < len(nums):
        # Move the end pointer ahead while the difference between the indices
        # is equal to the difference between the numbers at these indices
        while end < len(nums) - 1 and nums[end+1] - nums[start] == end+1 - start:
            end += 1
        # Add the current range to the result array
        if start == end:
            result.append(str(nums[start]))
        else:
            result.append(f"{nums[start]}->{nums[end]}")
        # Move both pointers to the next position
        end += 1
        start = end

    return result

Time Complexity

This algorithm also has a time complexity of O(n), as it iterates through the array once.

Space Complexity

The space complexity remains O(n) for the same reasons as the first approach.

Optimizations and Variations

While the time complexity of O(n) is optimal for this problem, one could attempt minor optimizations. For instance, pre-allocating the result list with an upper bound on its size can lead to minor performance gains. Additionally, using deque from collections for the result list may offer performance improvements when appending ranges.

Conclusion

In this article, we delved into the Summary Ranges problem on LeetCode, examined two different algorithms that employ simple linear iteration and two pointers respectively, and implemented them in Python. Both approaches have linear time and space complexity, which is quite efficient for this problem. The key insight is recognizing when a range ends, and this is effectively done by comparing adjacent elements in the sorted array.

Leave a Reply