Problem Description

The problem "Find the Start and End Number of Continuous Ranges" asks you to process a sorted array of unique integers and summarize all the consecutive number sequences (continuous ranges) within that array. For each range, you should return the starting and ending numbers.

For example, given nums = [0, 1, 2, 4, 5, 7], the ranges are [0,2], [4,5], and [7,7]. The output should be a list of pairs, each pair representing the start and end of a continuous range.

• The input array is sorted in ascending order and contains no duplicates.
• Each range must be as large as possible (maximal consecutive sequence).
• If a number is not part of any larger range, it's a range by itself (start and end are the same).

Thought Process

The first idea that might come to mind is to check every possible pair of numbers to see if they are consecutive, but that would be inefficient. Instead, since the array is sorted and contains unique numbers, we can simply look for "gaps" between numbers. When a gap is found (i.e., the difference between adjacent numbers is more than 1), it means a range has ended and a new one begins.

We can iterate through the array, keeping track of where the current range starts. When we find a gap, we record the current start and end, then start a new range. This approach is much more efficient and intuitive. The sorted, unique nature of the input makes this process straightforward.

Solution Approach

• Initialize: Use a variable to mark the start index of the current range.
• Iterate: Go through the array from the first to the last element.
  • For each element, check if the next number is not consecutive (i.e., nums[i] + 1 != nums[i+1]).
  • If so, record the range from the current start to the current element.
  • Then, set the start to the next index.
• Edge Case: After the loop, ensure the last range is recorded, since the array might end with a range.
• Output: Return a list of pairs (or arrays) where each pair contains the start and end of a continuous range.

This approach only requires a single pass through the array, making it efficient and easy to implement.

Example Walkthrough

Let's use the example nums = [0, 1, 2, 4, 5, 7]:

1. Start at index 0 (start = 0).
2. Compare nums[0] = 0 and nums[1] = 1: consecutive.
3. Compare nums[1] = 1 and nums[2] = 2: consecutive.
4. Compare nums[2] = 2 and nums[3] = 4: not consecutive (gap of 2).
5. Record range: [nums[0], nums[2]] = [0, 2].
6. Set start = 3.
7. Compare nums[3] = 4 and nums[4] = 5: consecutive.
8. Compare nums[4] = 5 and nums[5] = 7: not consecutive (gap of 2).
9. Record range: [nums[3], nums[4]] = [4, 5].
10. Set start = 5.
11. End of array: record final range [nums[5], nums[5]] = [7, 7].

Final output: [[0,2], [4,5], [7,7]]

Time and Space Complexity

• Brute-force approach: If you checked every possible pair or tried to build ranges from scratch, you might end up with O(n^2) time.
• Optimized approach (as above): Since we only scan the array once and perform constant work per element, the time complexity is O(n).
• Space complexity: We only use a small amount of extra space for the output list (proportional to the number of ranges, which is at most n), so space is O(n).

Summary

By leveraging the sorted and unique properties of the input array, we can efficiently find all continuous ranges by scanning for gaps. This approach is both simple and optimal, requiring only a single pass and minimal extra space. The key insight is to recognize that a new range starts whenever two adjacent numbers are not consecutive, allowing us to cleanly segment the array into its maximal consecutive ranges.

Code Implementation

def findContinuousRanges(nums):
    if not nums:
        return []
    ranges = []
    start = 0
    for i in range(1, len(nums)):
        if nums[i] != nums[i-1] + 1:
            ranges.append([nums[start], nums[i-1]])
            start = i
    ranges.append([nums[start], nums[-1]])
    return ranges
      

#include <vector>
using namespace std;

vector<vector<int>> findContinuousRanges(const vector<int>& nums) {
    vector<vector<int>> ranges;
    if (nums.empty()) return ranges;
    int start = 0;
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] != nums[i-1] + 1) {
            ranges.push_back({nums[start], nums[i-1]});
            start = i;
        }
    }
    ranges.push_back({nums[start], nums.back()});
    return ranges;
}
      

import java.util.*;

public class Solution {
    public List<List<Integer>> findContinuousRanges(int[] nums) {
        List<List<Integer>> ranges = new ArrayList<>();
        if (nums.length == 0) return ranges;
        int start = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1] + 1) {
                ranges.add(Arrays.asList(nums[start], nums[i-1]));
                start = i;
            }
        }
        ranges.add(Arrays.asList(nums[start], nums[nums.length-1]));
        return ranges;
    }
}
      

function findContinuousRanges(nums) {
    if (!nums || nums.length === 0) return [];
    const ranges = [];
    let start = 0;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] !== nums[i-1] + 1) {
            ranges.push([nums[start], nums[i-1]]);
            start = i;
        }
    }
    ranges.push([nums[start], nums[nums.length-1]]);
    return ranges;
}