Skip to content

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

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}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
}

Comments