Algorithm of Summarizing Contiguous Intervals

You are given a list of unique integers nums. Return a sorted two dimensional list of integers where each list represents an inclusive interval summarizing integers that are contiguous in nums.

Constraints

n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 3, 2, 7, 6]
Output

1 2 3 4

[     [1, 3],     [6, 7] ]

[
    [1, 3],
    [6, 7]
]

Algorithm to Summarize/Merge Contiguous Intervals

We can use the similar algorithm as described here: Linear Algorithm to Merge Intervals – which also requires us to sort the numbers first.

Then, we can iterate the numbers, and expand the previous interval if next number can be attached to it otherwise, push the next single number interval to the result.

1
2
3
4
5
6
7
8
9
10
11
12

vector<vector<int>> mergeContiguousIntervals(vector<int>& nums) {
    sort(begin(nums), end(nums));    
    vector<vector<int>> ans;
    for (auto &n: nums) {
        if ((!ans.empty()) && (ans.back().back() + 1 == n)) {
            ans.back().back() += 1;
        } else {
            ans.push_back({n, n});
        }
    }
    return ans;
}

vector<vector<int>> mergeContiguousIntervals(vector<int>& nums) {
    sort(begin(nums), end(nums));    
    vector<vector<int>> ans;
    for (auto &n: nums) {
        if ((!ans.empty()) && (ans.back().back() + 1 == n)) {
            ans.back().back() += 1;
        } else {
            ans.push_back({n, n});
        }
    }
    return ans;
}

The time complexity is O(N) and the space complexity is also O(N) where N is the number of elements in the array.

–EOF (The Ultimate Computing & Technology Blog) —