Skip to content

4101. Find All Numbers Disappeared in an Array III πŸ”’

DifficultyMedium

Description

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

An integer is missing if it lies in the inclusive range [lower, upper] and does not appear in nums.

Return a 2D integer array representing all missing integers grouped into contiguous ranges. Represent each range as [start, end], including both endpoints, and return the ranges in increasing order of start.

Consecutive missing integers must belong to the same range. If there are no missing integers, return an empty array.

 

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,1000000000], lower = 5, upper = 1000000000

Output: [[5,999999999]]

Explanation:

  • The value 1 lies outside [lower, upper], so it does not cover any integer in the range.
  • The only integer of the range that appears in nums is 1000000000.
  • Every integer from 5 to 999999999 is missing, and they are consecutive, so they form the single range [5, 999999999].

Example 3:

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

Output: []

Explanation:

  • Both 2 and 3 appear in nums, so there are no missing integers.
  • Therefore, the answer is [].

 

Constraints:

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

Solutions

Thinking

The upper bound \(\textit{upper}\) can be up to \(10^9\), so checking each integer in \([\textit{lower}, \textit{upper}]\) one by one will time out.

Since \(\textit{nums}\) has at most \(10^5\) elements, only the elements that fall within \([\textit{lower}, \textit{upper}]\) split the range into missing segments. After sorting \(\textit{nums}\), binary search locates the index range \([l, r)\) of elements in \([\textit{lower}, \textit{upper}]\), and each gap between consecutive elements forms a contiguous range of missing integers.

Maintain \(\textit{pre}\) as the smallest uncovered integer (initially \(\textit{lower}\)) and scan each element \(\textit{cur}\) in \([l, r)\): whenever \(\textit{pre} < \textit{cur}\), \([\textit{pre}, \textit{cur} - 1]\) is a missing range, then advance \(\textit{pre}\) to \(\textit{cur} + 1\), and finally append \([\textit{pre}, \textit{upper}]\) if \(\textit{pre} \le \textit{upper}\).

We first sort the array \(\textit{nums}\) in ascending order, and then use binary search to find the first index \(l\) where \(\textit{nums}[l] \ge \textit{lower}\) and the first index \(r\) where \(\textit{nums}[r] \ge \textit{upper} + 1\). The elements in the index range \([l, r)\) are all the numbers in \(\textit{nums}\) that fall within \([\textit{lower}, \textit{upper}]\).

We maintain a variable \(\textit{pre}\) representing the smallest integer not yet covered, initialized to \(\textit{pre} = \textit{lower}\). We iterate through \(i \in [l, r)\) and let \(\textit{cur} = \textit{nums}[i]\):

  • If \(\textit{pre} < \textit{cur}\), all integers in \([\textit{pre}, \textit{cur} - 1]\) are missing, so we append \([\textit{pre}, \textit{cur} - 1]\) to the answer list \(\textit{ans}\);
  • We then update \(\textit{pre} = \textit{cur} + 1\) (duplicate values naturally have \(\textit{pre} > \textit{cur}\) and are skipped).

After the loop, if \(\textit{pre} \le \textit{upper}\), the trailing range \([\textit{pre}, \textit{upper}]\) is also missing, so we append it to \(\textit{ans}\). Finally, we return \(\textit{ans}\).

The time complexity is \(O(n \log n)\), and the space complexity is \(O(\log n)\), where \(n\) is the length of the array \(\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]]:
        nums.sort()
        l = bisect_left(nums, lower)
        r = bisect_left(nums, upper + 1)
        ans = []
        pre = lower
        for i in range(l, r):
            cur = nums[i]
            if pre < cur:
                ans.append([pre, cur - 1])
            pre = cur + 1
        if pre <= upper:
            ans.append([pre, 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
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int[][] findDisappearedNumbers(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        int l = lowerBound(nums, lower);
        int r = lowerBound(nums, upper + 1);
        List<int[]> ans = new ArrayList<>();
        int pre = lower;
        for (int i = l; i < r; i++) {
            int cur = nums[i];
            if (pre < cur) {
                ans.add(new int[] {pre, cur - 1});
            }
            pre = cur + 1;
        }
        if (pre <= upper) {
            ans.add(new int[] {pre, upper});
        }
        return ans.toArray(new int[ans.size()][]);
    }

    private int lowerBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}

 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());
        int l = lower_bound(nums.begin(), nums.end(), lower) - nums.begin();
        int r = lower_bound(nums.begin(), nums.end(), upper + 1) - nums.begin();
        vector<vector<int>> ans;
        int pre = lower;
        for (int i = l; i < r; i++) {
            int cur = nums[i];
            if (pre < cur) {
                ans.push_back({pre, cur - 1});
            }
            pre = cur + 1;
        }
        if (pre <= upper) {
            ans.push_back({pre, upper});
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func findDisappearedNumbers(nums []int, lower int, upper int) [][]int {
    sort.Ints(nums)
    l := sort.SearchInts(nums, lower)
    r := sort.Search(len(nums), func(i int) bool {
        return nums[i] > upper
    })
    ans := [][]int{}
    pre := lower
    for i := l; i < r; i++ {
        cur := nums[i]
        if pre < cur {
            ans = append(ans, []int{pre, cur - 1})
        }
        pre = cur + 1
    }
    if pre <= upper {
        ans = append(ans, []int{pre, upper})
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function findDisappearedNumbers(nums: number[], lower: number, upper: number): number[][] {
    nums.sort((a, b) => a - b);
    const l = _.sortedIndex(nums, lower);
    const r = _.sortedIndex(nums, upper + 1);
    const ans: number[][] = [];
    let pre = lower;

    for (let i = l; i < r; i++) {
        const cur = nums[i];
        if (pre < cur) {
            ans.push([pre, cur - 1]);
        }
        pre = cur + 1;
    }

    if (pre <= upper) {
        ans.push([pre, upper]);
    }
    return ans;
}

Comments