Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/163.html
163. Missing Ranges
Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99,
return [“2”, “4->49”, “51->74”, “76->99”]
@tag-array
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()); } } }
-
// 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