Find All Numbers Disappeared in an Array II - Solution & Explanation

Medium6 min read

Problem Statement

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 <= 10⁵
1 <= nums[i] <= 10⁵
1 <= lower <= upper <= 10⁵

Solution

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

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

After the scan, if prev < upper, append the trailing range [prev + 1, upper].

The time complexity is O(n times log n) and the space complexity is O(log n), where n is the length of nums.