algoadvance

Leetcode 228. Summary Ranges

Problem Statement

You are given a sorted unique integer array nums.

A range [a,b] is the smallest interval that includes every number between a and b (inclusive). In this case, if a != b, “a->b” should be returned instead of “a”.

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Example

Input:

nums = [0,1,2,4,5,7]

Output:

["0->2","4->5","7"]

Input:

nums = [0,2,3,4,6,8,9]

Output:

["0","2->4","6","8->9"]

---

Clarifying Questions

1. Q: What should we return if the input list is empty? A: Return an empty list.

2. Q: Are the numbers in the input list always sorted in ascending order? A: Yes, they are always sorted and unique.

3. Q: Can elements in nums be negative or are they always non-negative? A: Elements can be negative.

Strategy

1. Initialization: Initialize an empty result vector ranges and two pointers, start and end, to traverse the list.
2. Traversal: Iterate through the array while keeping track of ranges.
   • If the current element continues the previous range (i.e., it is one more than the previous element), extend the current range.
   • If it doesn’t, close the current range and start a new one.
3. Range Closure: Add the current range to the result when you find the end of a range.
4. Final Check: If there’s any range left unadded after the loop, add it to the result.
5. Edge Cases: Handle scenarios where the array is empty or contains just one element.

Code

Here’s the C++ code to solve this problem:

#include <vector>
#include <string>

using namespace std;

vector<string> summaryRanges(vector<int>& nums) {
    vector<string> ranges;
    if (nums.empty()) return ranges;
    
    int n = nums.size();
    int start = 0;
    
    for (int i = 1; i <= n; ++i) {
        // Check if it's the end of the range
        if (i == n || nums[i] != nums[i - 1] + 1) {
            // Add the range to the result
            if (start == i - 1) {
                ranges.push_back(to_string(nums[start]));
            } else {
                ranges.push_back(to_string(nums[start]) + "->" + to_string(nums[i - 1]));
            }
            // Update start for the next range
            start = i;
        }
    }
    
    return ranges;
}

Time Complexity

• Time Complexity: O(n) where n is the number of elements in nums.
  • The list is traversed once, which gives a linear time complexity.
• Space Complexity: O(1) for the extra space used, not counting the space needed for the output, which is proportional to the number of ranges created.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?