Welcome to Subscribe On Youtube

4031. Find All Numbers Disappeared in an Array II

Description

You are given an integer array nums and two integers lower and upper.

A missing integer is an integer in the inclusive range [lower, upper] that does not appear in nums.

Return a 2D integer array where each element is of the form [start, end], representing a contiguous range of missing integers. Return the ranges in increasing order. If there are no missing integers, return an empty array.

Note: Consecutive missing integers should be grouped into a single range.

 

Example 1:

Input: nums = [3,9,7], lower = 1, upper = 12

Output: [[1,2],[4,6],[8,8],[10,12]]

Explanation:

• The missing integers are [1, 2, 4, 5, 6, 8, 10, 11, 12].
• Grouping the missing integers into the minimum number of contiguous ranges, we get [1, 2], [4, 6], [8, 8], and [10, 12].
• Therefore, the answer is [[1, 2], [4, 6], [8, 8], [10, 12]].

Example 2:

Input: nums = [1,1], lower = 5, upper = 7

Output: [[5,7]]

Explanation:

• The missing integers are [5, 6, 7].
• Grouping the missing integers into the minimum number of contiguous ranges, we get [5, 7].
• Therefore, the answer is [[5, 7]].

Example 3:

Input: nums = [2,3,5], lower = 2, upper = 3

Output: []

Explanation:

• There are no missing integers.
• Therefore, the answer is [].

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• 1 <= lower <= upper <= 105

Solutions

Solution 1: Sorting

Thinking

The missing pieces are the contiguous gaps of $[\textit{lower},\textit{upper}]$ that never appear. Testing every integer in that range would follow the value range rather than $n$.

After sorting and uniquifying the present values, each gap between two consecutive in-range numbers is a missing interval; the two ends relative to $\textit{lower}$ and $\textit{upper}$ are filled in the same way.

Scanning with $\textit{prev}=\textit{lower}-1$, we emit $[\textit{prev}+1,x-1]$ whenever $x-\textit{prev}>1$.

We sort $\textit{nums}$ and then scan it. Let $\textit{prev}$ be the previous number that appears in $[\textit{lower}, \textit{upper}]$, initially $\textit{lower} - 1$.

Iterate over the sorted array and skip values outside $[\textit{lower}, \textit{upper}]$. If there is a gap between the current number $x$ and $\textit{prev}$, i.e. $x - \textit{prev} > 1$, append the missing range $[\textit{prev} + 1, x - 1]$ to the answer, then set $\textit{prev}$ to $x$.

After the scan, if $\textit{prev} < \textit{upper}$, append the trailing range $[\textit{prev} + 1, \textit{upper}]$.

The time complexity is $O(n \times \log n)$ and the space complexity is $O(\log n)$, where $n$ is the length of $\textit{nums}$.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public List<List<Integer>> findDisappearedNumbers(int[] nums, int lower, int upper) {
          Arrays.sort(nums);
          List<List<Integer>> ans = new ArrayList<>();
          int prev = lower - 1;
          for (int x : nums) {
              if (x < lower || x > upper) {
                  continue;
              }
              if (x - prev > 1) {
                  ans.add(List.of(prev + 1, x - 1));
              }
              prev = x;
          }
          if (prev < upper) {
              ans.add(List.of(prev + 1, upper));
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      vector<vector<int>> findDisappearedNumbers(vector<int>& nums, int lower, int upper) {
          sort(nums.begin(), nums.end());
          vector<vector<int>> ans;
          int prev = lower - 1;
          for (int x : nums) {
              if (x < lower || x > upper) {
                  continue;
              }
              if (x - prev > 1) {
                  ans.push_back({prev + 1, x - 1});
              }
              prev = x;
          }
          if (prev < upper) {
              ans.push_back({prev + 1, upper});
          }
          return ans;
      }
  };
  
  

• class Solution:
      def findDisappearedNumbers(
          self, nums: List[int], lower: int, upper: int
      ) -> List[List[int]]:
          ans = []
          prev = lower - 1
          for x in sorted(set(nums)):
              if x < lower:
                  continue
              if x > upper:
                  break
              if x - prev > 1:
                  ans.append([prev + 1, x - 1])
              prev = x
          if prev < upper:
              ans.append([prev + 1, upper])
          return ans
  
  

• func findDisappearedNumbers(nums []int, lower int, upper int) (ans [][]int) {
  	sort.Ints(nums)
  	prev := lower - 1
  	for _, x := range nums {
  		if x < lower || x > upper {
  			continue
  		}
  		if x-prev > 1 {
  			ans = append(ans, []int{prev + 1, x - 1})
  		}
  		prev = x
  	}
  	if prev < upper {
  		ans = append(ans, []int{prev + 1, upper})
  	}
  	return
  }
  
  

• function findDisappearedNumbers(nums: number[], lower: number, upper: number): number[][] {
      nums.sort((a, b) => a - b);
      const ans: number[][] = [];
      let prev = lower - 1;
      for (const x of nums) {
          if (x < lower || x > upper) {
              continue;
          }
          if (x - prev > 1) {
              ans.push([prev + 1, x - 1]);
          }
          prev = x;
      }
      if (prev < upper) {
          ans.push([prev + 1, upper]);
      }
      return ans;
  }
  
  

All Problems

All Solutions