Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

Solution

Method 1 - Iteration

Here is the approach:

  1. Initial Setup and Edge Case: Handle the edge case where nums is empty. If nums is empty, the range [lower, upper] is the only missing range.
  2. Identify Missing Ranges:
    • Compare lower with the first element in nums to determine if there is a missing range before the first element.
    • Iterate through nums to find missing ranges between consecutive elements.
    • Compare the last element in nums with upper to determine if there is a range missing after the last element.
  3. Result Collection: Collect all identified missing ranges in the result list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();

        if (n == 0) {
            ans.add(List.of(lower, upper));
            return ans;
        }

        // Check for missing range before the first element
        if (nums[0] > lower) {
            ans.add(List.of(lower, nums[0] - 1));
        }

        // Check for missing ranges between consecutive elements
        for (int i = 1; i < n; ++i) {
            if (nums[i] - nums[i - 1] > 1) {
                ans.add(List.of(nums[i - 1] + 1, nums[i] - 1));
            }
        }

        // Check for missing range after the last element
        if (nums[n - 1] < upper) {
            ans.add(List.of(nums[n - 1] + 1, upper));
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:
        n: int = len(nums)
        ans: List[List[int]] = []

        if n == 0:
            ans.append([lower, upper])
            return ans

        # Check for missing range before the first element
        if nums[0] > lower:
            ans.append([lower, nums[0] - 1])

        # Check for missing ranges between consecutive elements
        for i in range(1, n):
            if nums[i] - nums[i - 1] > 1:
                ans.append([nums[i - 1] + 1, nums[i] - 1])

        # Check for missing range after the last element
        if nums[-1] < upper:
            ans.append([nums[-1] + 1, upper])

        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums, as we iterate through the array once.
  • 🧺 Space complexity: O(1) for extra space, not considering the output list.