LeetCode Solutions
163. Missing Ranges
Time: $O(n)$ Space: $O(n)$
class Solution {
public:
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
if (nums.empty())
return {getRange(lower, upper)};
vector<string> ans;
if (nums.front() > lower)
ans.push_back(getRange(lower, nums.front() - 1));
for (int i = 1; i < nums.size(); ++i)
if (nums[i] > nums[i - 1] + 1)
ans.push_back(getRange(nums[i - 1] + 1, nums[i] - 1));
if (nums.back() < upper)
ans.push_back(getRange(nums.back() + 1, upper));
return ans;
}
private:
string getRange(int lo, int hi) {
if (lo == hi)
return to_string(lo);
return to_string(lo) + "->" + to_string(hi);
}
};
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
if (nums.length == 0)
return new ArrayList<>(Arrays.asList(getRange(lower, upper)));
List<String> ans = new ArrayList<>();
if (nums[0] > lower)
ans.add(getRange(lower, nums[0] - 1));
for (int i = 1; i < nums.length; ++i)
if (nums[i] > nums[i - 1] + 1)
ans.add(getRange(nums[i - 1] + 1, nums[i] - 1));
if (nums[nums.length - 1] < upper)
ans.add(getRange(nums[nums.length - 1] + 1, upper));
return ans;
}
private String getRange(int lo, int hi) {
if (lo == hi)
return String.valueOf(lo);
return lo + "->" + hi;
}
}
class Solution:
def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
def getRange(lo: int, hi: int) -> str:
if lo == hi:
return str(lo)
return str(lo) + '->' + str(hi)
if not nums:
return [getRange(lower, upper)]
ans = []
if nums[0] > lower:
ans.append(getRange(lower, nums[0] - 1))
for prev, curr in zip(nums, nums[1:]):
if curr > prev + 1:
ans.append(getRange(prev + 1, curr - 1))
if nums[-1] < upper:
ans.append(getRange(nums[-1] + 1, upper))
return ans