Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/163.html
You are given an inclusive range [lower, upper]
and a sorted unique integer array nums
, where all elements are within the inclusive range.
A number x
is considered missing if x
is in the range [lower, upper]
and x
is not in nums
.
Return the shortest sorted list of ranges that exactly covers all the missing numbers. That is, no element of nums
is included in any of the ranges, and each missing number is covered by one of the ranges.
Example 1:
Input: nums = [0,1,3,50,75], lower = 0, upper = 99 Output: [[2,2],[4,49],[51,74],[76,99]] Explanation: The ranges are: [2,2] [4,49] [51,74] [76,99]
Example 2:
Input: nums = [-1], lower = -1, upper = -1 Output: [] Explanation: There are no missing ranges since there are no missing numbers.
Constraints:
-109 <= lower <= upper <= 109
0 <= nums.length <= 100
lower <= nums[i] <= upper
- All the values of
nums
are unique.
Algorithm
To find the missing intervals in an array nums
, we can follow the below approach:
- Traverse the
nums
array and compare each number with thelower
bound of the interval we are looking for. - If the current number
num
is greater thanlower
, it means that there is a missing interval at this time, and at least one lower number is missing. - If
num-1
is greater thanlower
, it means that the missing interval is[lower, num-1]
, so we add this missing interval to the result. - If
num-1
is not greater thanlower
, it means that there is only one missing number, so we add that to the result. - When there is an integer maximum value in the array, updating
lower
tonum+1
will cause an overflow. Therefore, before updating, we need to check ifnum
is already the maximum value of an integer. If it is, we return the result directly without updatinglower
. - After the for loop exits, there may still be a missing interval, that is, when
lower
is less than or equal toupper
, the lower number or the[lower, upper]
interval may be missing, and we add this interval to the result.
Finally, we return the list of missing intervals as the result.
Code
-
import java.util.ArrayList; import java.util.List; public class Missing_Ranges { public static void main(String[] args) { Missing_Ranges out = new Missing_Ranges(); Solution s = out.new Solution(); System.out.println(s.findMissingRanges(new int[]{0, 1, 3, 50, 75}, 0, 99)); System.out.println(s.findMissingRanges(new int[]{0, 1, 3, 50, 75}, -100, 50)); System.out.println(s.findMissingRanges(new int[]{0, 1, 3, 50, 75}, 49, 200)); } public class Solution { public List<String> findMissingRanges(int[] nums, int lower, int upper) { List<String> result = new ArrayList<String>(); if (nums == null || nums.length == 0) { outputToResult(lower, upper, result); return result; } // leading missing range if (nums[0] - lower > 0) { outputToResult(lower, nums[0] - 1, result); } for (int i = 1; i < nums.length; i++) { if (nums[i] - nums[i - 1] > 1) { // @note: nice catch outputToResult(nums[i - 1] + 1, nums[i] - 1, result); } } // trailing missage ranges if (upper - nums[nums.length - 1] > 0) { outputToResult(nums[nums.length - 1] + 1, upper, result); } return result; } private void outputToResult(int start, int end, List<String> result) { StringBuffer sb = new StringBuffer(); if (start == end) { sb.append(start); } else { sb.append(start + "->" + end); } result.add(sb.toString()); } } } ############ class Solution { public List<String> findMissingRanges(int[] nums, int lower, int upper) { int n = nums.length; List<String> ans = new ArrayList<>(); if (n == 0) { ans.add(f(lower, upper)); return ans; } if (nums[0] > lower) { ans.add(f(lower, nums[0] - 1)); } for (int i = 1; i < n; ++i) { int a = nums[i - 1], b = nums[i]; if (b - a > 1) { ans.add(f(a + 1, b - 1)); } } if (nums[n - 1] < upper) { ans.add(f(nums[n - 1] + 1, upper)); } return ans; } private String f(int a, int b) { return a == b ? a + "" : a + "->" + b; } }
-
// OJ: https://leetcode.com/problems/missing-ranges/ // Time: O(N) // Space: O(1) class Solution { string formatRange(int lower, int upper) { if (lower == upper) return to_string(lower); return to_string(lower) + "->" + to_string(upper); } public: vector<string> findMissingRanges(vector<int>& A, int lower, int upper) { vector<string> ans; int i = lower, j = 0, N = A.size(); while (j < N) { if (i == A[j]) { ++i; ++j; } else { int first = i, last = A[j] - 1; ans.push_back(formatRange(first, last)); i = A[j++] + 1; } } if (i <= upper) ans.push_back(formatRange(i, upper)); return ans; } };
-
class Solution: def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]: def f(a, b): return str(a) if a == b else f'{a}->{b}' n = len(nums) if n == 0: return [f(lower, upper)] ans = [] if nums[0] > lower: ans.append(f(lower, nums[0] - 1)) for a, b in pairwise(nums): if b - a > 1: ans.append(f(a + 1, b - 1)) if nums[-1] < upper: ans.append(f(nums[-1] + 1, upper)) return ans ############ class Solution(object): def findMissingRanges(self, nums, lower, upper): """ :type nums: List[int] :type lower: int :type upper: int :rtype: List[str] """ ans = [] nums = [lower - 1] + nums + [upper + 1] for i in range(0, len(nums) - 1): if nums[i] + 2 == nums[i + 1]: ans.append(str(nums[i] + 1)) if nums[i + 1] > nums[i] + 2: ans.append(str(nums[i] + 1) + "->" + str(nums[i + 1] - 1)) return ans
-
func findMissingRanges(nums []int, lower int, upper int) (ans []string) { f := func(a, b int) string { if a == b { return strconv.Itoa(a) } return strconv.Itoa(a) + "->" + strconv.Itoa(b) } n := len(nums) if n == 0 { ans = append(ans, f(lower, upper)) return } if nums[0] > lower { ans = append(ans, f(lower, nums[0]-1)) } for i := 1; i < n; i++ { a, b := nums[i-1], nums[i] if b-a > 1 { ans = append(ans, f(a+1, b-1)) } } if nums[n-1] < upper { ans = append(ans, f(nums[n-1]+1, upper)) } return }