More general algorithm makes no assumption on the range of elements.


  • 0
    H
    // misunderstood the problem. following solution make no assumption about
    // the elements of sorted array are in the range of [lower, upper].
    class Solution {
    public:
        // generate a string representing [begin, end].
        string GenerateRange(const int begin, const int end) {
            if (begin == end) {
                return to_string(begin);
            } else {
                return to_string(begin)
                       + "->"
                       + to_string(end);
            }
        }
        
        vector<string> findMissingRanges(vector<int>& nums,
                                         int lower, int upper) {
            vector<string> ret;
            int begin = 0;
            
            // locate the smallest index satisfying nums[begin] >= lower.
            while (begin < nums.size() && nums[begin] < lower) {
                ++begin;
            }
            if (begin == nums.size()) {
                return {GenerateRange(lower, upper)};
            }
            
            // 1. process lower bound case.
            if (lower < nums[begin]) {
                ret.push_back(GenerateRange(lower, nums[begin] - 1));
            }
            for (int end = begin + 1; end < nums.size(); ++end) {
                if (nums[end] > upper) {
                    break;
                }
                if (nums[end] == nums[begin] + 1) {
                    ++begin;
                    continue;
                }
                // here we detect a gap.
                ret.push_back(GenerateRange(nums[begin] + 1, nums[end] - 1));
                begin = end;
            }
            // 2. process upper bound case.
            if (nums[begin] < upper) {
                ret.push_back(GenerateRange(nums[begin] + 1, upper));
            }
            
            return ret;
        }
    };
    

    Example Input/Output:

    Your input

    [0,2,4,6,8]
    4
    6

    Your answer

    ["5"]

    Expected answer

    ["1","3","5","7"]

    Runtime: 0 ms


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.