Question

163. Missing Ranges

中文文档

Description

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.

Solutions

Solution 1: Simulation

We can simulate the problem directly according to the requirements.

The time complexity is $O(n)$, where $n$ is the length of the array $nums$. Ignoring the space consumption of the answer, the space complexity is $O(1)$.

class Solution:
  def findMissingRanges(
    self, nums: List[int], lower: int, upper: int
  ) -> List[List[int]]:
    n = len(nums)
    if n == 0:
      return [[lower, upper]]
    ans = []
    if nums[0] > lower:
      ans.append([lower, nums[0] - 1])
    for a, b in pairwise(nums):
      if b - a > 1:
        ans.append([a + 1, b - 1])
    if nums[-1] < upper:
      ans.append([nums[-1] + 1, upper])
    return ans

class Solution {
  public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper) {
    int n = nums.length;
    if (n == 0) {
      return List.of(List.of(lower, upper));
    }
    List<List<Integer>> ans = new ArrayList<>();
    if (nums[0] > lower) {
      ans.add(List.of(lower, nums[0] - 1));
    }
    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));
      }
    }
    if (nums[n - 1] < upper) {
      ans.add(List.of(nums[n - 1] + 1, upper));
    }
    return ans;
  }
}

class Solution {
public:
  vector<vector<int>> findMissingRanges(vector<int>& nums, int lower, int upper) {
    int n = nums.size();
    if (n == 0) {
      return {{lower, upper}};
    }
    vector<vector<int>> ans;
    if (nums[0] > lower) {
      ans.push_back({lower, nums[0] - 1});
    }
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] - nums[i - 1] > 1) {
        ans.push_back({nums[i - 1] + 1, nums[i] - 1});
      }
    }
    if (nums[n - 1] < upper) {
      ans.push_back({nums[n - 1] + 1, upper});
    }
    return ans;
  }
};

func findMissingRanges(nums []int, lower int, upper int) (ans [][]int) {
  n := len(nums)
  if n == 0 {
    return [][]int{{lower, upper}}
  }
  if nums[0] > lower {
    ans = append(ans, []int{lower, nums[0] - 1})
  }
  for i, b := range nums[1:] {
    if a := nums[i]; b-a > 1 {
      ans = append(ans, []int{a + 1, b - 1})
    }
  }
  if nums[n-1] < upper {
    ans = append(ans, []int{nums[n-1] + 1, upper})
  }
  return
}

function findMissingRanges(nums: number[], lower: number, upper: number): number[][] {
  const n = nums.length;
  if (n === 0) {
    return [[lower, upper]];
  }
  const ans: number[][] = [];
  if (nums[0] > lower) {
    ans.push([lower, nums[0] - 1]);
  }
  for (let i = 1; i < n; ++i) {
    if (nums[i] - nums[i - 1] > 1) {
      ans.push([nums[i - 1] + 1, nums[i] - 1]);
    }
  }
  if (nums[n - 1] < upper) {
    ans.push([nums[n - 1] + 1, upper]);
  }
  return ans;
}