163. Missing Ranges

• Difficulty: Medium

• Topics: Array

• Similar Questions:

  • Summary Ranges

Problem:

Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

Example:

Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]

Solutions:

class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<string> ret;
        int expected = lower;
        for (auto num : nums) {
            if (num <= expected) { // less and equal
                if (num == INT_MAX) return ret; // to prevent overflow
                expected = num + 1;
            } else {
                ret.push_back(missingRange(expected, num - 1));
                if (num == INT_MAX) return ret;
                expected = num + 1; // overflow
            }
        }

        if (expected <= upper) {
            ret.push_back(missingRange(expected, upper));
        }

        return ret;
    }

    string missingRange(int lower, int upper) {
        if (lower == upper) {
            return to_string(lower);
        } else {
            return to_string(lower) + "->" + to_string(upper);
        }
    }
};