C++ : easy trick to avoid checking conner cases, with explanation


  • 0
    G
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        // key here: make inclusive range exclusive to avoid corner cases
        // now problem becomes finding inclusive ranges between the pair of numbers: 
        // {lower, nums[0], ..., nums[n], upper} 
        lower--;    
        upper++;
        vector<string> res;
        nums.push_back(upper);      
        int pre = lower;
        for (int i=0; i<nums.size(); ++i) {
            // case 1: pair (x, x) or (x, x+1) has no range between them
            if (nums[i] <= pre+1) {
                pre = nums[i];
                continue;
            }
            // case 2: pair (x, x+2) use one single integer to represent the range
            if (nums[i] == pre+2) {
                res.push_back(to_string(pre+1));
            }
            // case 3: regular ranges
            else {
                res.push_back(to_string(pre+1)+"->"+to_string(nums[i]-1));
            }
            pre = nums[i];
        }
        // recover the input if needed
        nums.pop_back();
        return res;
    }

  • 0
    J

    what if lower is INT_MIN and upper is INT_MAX?


Log in to reply
 

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