Skip to main content
Talentd

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

MediumArrayBinary SearchSorting7 min read
Practice this problem

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

Approach Overview

Problem Overview: You receive an array of n integers where each value is between 1 and n. Some numbers appear twice, others once, and some are missing. Your task is to return all numbers from 1 to n that are absent from the array.

Approach 1: Brute Force (O(n²) time, O(1) space)
Check every number from 1 to n by scanning the entire array for each candidate. This uses two nested loops and no extra memory. Prefer only when the array is extremely small or you need a trivial baseline.

Approach 2: Sorting (O(n log n) time, O(1) space)
Sort the array first, then iterate to find gaps between consecutive elements. After sorting, missing numbers are easy to spot by comparing the expected value with the current element. This is a simple solution when you are allowed to modify the input and want to avoid extra memory.

Approach 3: Hash Set (O(n) time, O(n) space)
Insert every element into a hash set, then loop from 1 to n and check which numbers are not present. The set gives O(1) lookups, making the overall time linear. Use this when you can afford extra memory and want the most straightforward linear-time solution.

Approach 4: In-Place Marking (O(n) time, O(1) space)
Iterate through the array and for each value v, mark the index v-1 as negative (or add n) to flag that v exists. Then a second pass collects indices where the value is still positive – those correspond to missing numbers. This is the optimal solution because it uses no extra space beyond the input array and runs in linear time.

Recommended for interviews: Start with the hash set to show you can solve it in O(n) time, then optimize to the in-place marking technique. The brute force shows you understand the problem, but the in-place approach demonstrates deep understanding of array manipulation and constant-space constraints – exactly what interviewers look for.

Related topics: Arrays, Hash Table, Sorting

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n²)O(1)Only for tiny arrays or educational baseline
SortingO(n log n)O(1) (if in-place sort)When you can modify the array and want no extra memory
Hash SetO(n)O(n)When extra memory is acceptable and you need linear time
In-Place MarkingO(n)O(1)Optimal for interviews; memory-constrained environments

Video Solutions (6)

Leetcode : 4031. Find All Numbers Disappeared in an Array II ( Weekly Contest 516 )

Web Fusion with Bharadwaj23:4361 views
Video 1 of 6

Frequently Asked Questions

Is Find All Numbers Disappeared in an Array II easy or hard?
It is rated as a medium difficulty problem on LeetCode. The brute-force and hash set solutions are straightforward, but the optimal in-place solution requires a clever insight. Most candidates can solve it with a hash set, but the constant-space approach sets apart stronger candidates.
Find All Numbers Disappeared in an Array II Python/Java solution
Python and Java solutions typically use the in-place marking method. In Python, you can negate values with `nums[abs(val)-1] = -abs(nums[abs(val)-1])`. In Java, use `int idx = Math.abs(nums[i])-1; if(nums[idx] > 0) nums[idx] = -nums[idx];`. Then collect indices where the value is positive. Both run in O(n) time and O(1) space.
How to solve Find All Numbers Disappeared in an Array II in O(n)?
Use the in-place marking technique. For each value v in the array, mark the index v-1 by making it negative (or adding n). Then a second pass collects all indices i where the value at i is still positive – those indices correspond to missing numbers. This runs in O(n) time and O(1) space.
What is the best approach for Find All Numbers Disappeared in an Array II?
The in-place marking approach is best because it runs in O(n) time and uses O(1) extra space. You iterate through the array, mark each seen number by negating the value at its index, then collect indices that remain positive. This avoids any extra data structures and is the most memory-efficient solution.
Is Find All Numbers Disappeared in an Array II asked at Google/Amazon/Meta?
Yes, this problem (or its close variant LeetCode 448) is frequently asked at top tech companies like Google, Amazon, and Meta. It tests your ability to manipulate arrays in-place and optimize space usage, which are common interview skills. Expect it in phone screens or as a warm-up question.
What data structure is used in Find All Numbers Disappeared in an Array II?
The optimal solution uses no extra data structure – it modifies the input array in-place. A simpler approach uses a hash set to store seen numbers. Sorting also uses the array itself. The in-place technique leverages the array indices as a natural mapping from value to position.
What is the time complexity of Find All Numbers Disappeared in an Array II?
The optimal solution runs in O(n) time, where n is the length of the array. A sorting-based solution runs in O(n log n), while a brute-force approach takes O(n²). The in-place marking and hash set methods both achieve O(n) time, but the in-place version uses only O(1) space.

Ready to solve this problem?

Practice Find All Numbers Disappeared in an Array II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find All Numbers Disappeared in an Array