How to Summary Ranges using O(N) Two Pointer Algorithm?

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

Example 1:
Input: [0,1,2,4,5,7]
Output: [“0->2″,”4->5″,”7”]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

Example 2:
Input: [0,2,3,4,6,8,9]
Output: [“0″,”2->4″,”6″,”8->9”]
Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.

Two Pointer Algorithm to Summary the Ranges

Since the array is already sorted, we can start scanning from left to the right, then continuously jump the pointer to the furthest if the next numbers are the neighbors. We then can generate the ranges for two cases: the single value (disjoint) or sub-ranges.

O(N) time and O(1) space requirement excluding the return vector. Each numbers in the array will be visited exactly once – the pointer will jump to the next range.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int i = 0, n = nums.size();
        vector<string> r;
        while (i < n) {
            int j = i;
            while ((j + 1 < n) && (nums[j] + 1 == nums[j + 1])) j ++;
            if (i == j) {
                r.push_back(std::to_string(nums[i]));
            } else {
                r.push_back(std::to_string(nums[i]) + "->" + std::to_string(nums[j]));
            }
            i = j + 1;
        }
        return r;
    }
};

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int i = 0, n = nums.size();
        vector<string> r;
        while (i < n) {
            int j = i;
            while ((j + 1 < n) && (nums[j] + 1 == nums[j + 1])) j ++;
            if (i == j) {
                r.push_back(std::to_string(nums[i]));
            } else {
                r.push_back(std::to_string(nums[i]) + "->" + std::to_string(nums[j]));
            }
            i = j + 1;
        }
        return r;
    }
};

We are using two pointers – the second pointer always is spawned from the first one. The above C++ solution implements this idea.

–EOF (The Ultimate Computing & Technology Blog) —