163. Missing Ranges
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"]
string getString(int num1, int num2) {
return (num1 == num2) ? to_string(num1) : (to_string(num1) + "->" + to_string(num2));
}
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) { // time: O(n); space: O(n)
vector<string> res;
long next = lower;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] < next) continue;
if (nums[i] == next) {
++next;
} else {
res.push_back(getString(next, nums[i] - 1));
next = (long)nums[i] + 1;
}
}
if (next <= upper) {
res.push_back(getString(next, upper));
}
return res;
}
Last updated
Was this helpful?