C++ 0ms 6 lines clean solution


  • 2

    Using binary search to find the start index in nums:

    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
            vector<string> ans;
            
            // Using binary search to find the start index in nums
            for (int i = lower_bound(nums.begin(), nums.end(), lower) - nums.begin(), l = lower, r; l <= upper; i++, l = r + 2) {
                r = i < nums.size() ? min(upper, nums[i] - 1) : upper;  // [l, r] is the missing range
                if (l <= r) { ans.push_back(to_string(l) + (l == r ? "" : "->" + to_string(r))); }
            }
            
            return ans;
    }
    

    We don't actually need to use binary search to find the start index in nums. We can simply start with index=0. The code becomes simpler. But the downside is if nums contains lots of elements smaller than lower, we are wasting time searching those small elements. But anyway, here's the more basic version:

    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
            vector<string> ans;
            
            for (int i = 0, l = lower, r; l <= upper; i++, l = r + 2) {
                r = i < nums.size() ? min(upper, nums[i] - 1) : upper;  // [l, r] is the missing range
                if (l <= r) { ans.push_back(to_string(l) + (l == r ? "" : "->" + to_string(r))); }
            }
            
            return ans;
    }
    

Log in to reply
 

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