448. Find All Numbers Disappeared in an Array
Find All Numbers Disappeared in an Array (LeetCode 448) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Array - Cyclic Sort subpattern.
How to solve Find All Numbers Disappeared in an Array
Find All Numbers Disappeared in an Array is a Cyclic Sort Algorithm problem, part of Array/Matrix Manipulation Patterns. Master cyclic sort pattern to find missing, duplicate, or misplaced numbers in arrays with O(n) time and O(1) space.
Work towards the solution in these steps:
- This is a really easy problem if you decide to use additional memory. For those trying to write an initial solution using additional memory, think <b>counters!</b>
- However, the trick really is to not use any additional space than what is already available to use. Sometimes, multiple passes over the input array help find the solution. However, there's an interesting piece of information in this problem that makes it easy to re-use the input array itself for the solution.
- The problem specifies that the numbers in the array will be in the range [1, n] where n is the number of elements in the array. Can we use this information and modify the array in-place somehow to find what we need?
The reference solution runs in O(n) time and O(1) space.
The Find All Numbers Disappeared in an Array solution and editorial walks through the full approach with reference code.
Problem statement
Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1] Output: [5,6]
Example 2:
Input: nums = [1,1] Output: [2]
Constraints:
- n == nums.length
- 1 <= n <= 10^5
- 1 <= nums[i] <= n
Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Topics and companies
Topics: Array, Hash Table.
Reported in interviews at Amazon.
How to practise Find All Numbers Disappeared in an Array on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Find All Numbers Disappeared in an Array in the code editor, or read the Find All Numbers Disappeared in an Array editorial for a worked solution with its approach and complexity analysis.
Where Find All Numbers Disappeared in an Array sits in the DSA pattern sheet
- Array/Matrix Manipulation Patterns pattern guide
- Array - Cyclic Sort subpattern
- The full DSA patterns sheet
Problems related to Find All Numbers Disappeared in an Array
Other problems that use the same Array - Cyclic Sort and Array/Matrix Manipulation Patterns techniques:
- Find All Duplicates in an Array — Medium, same subpattern
- First Missing Positive — Hard, same subpattern
- Add Binary — Easy, same pattern
- Add to Array-Form of Integer — Easy, same pattern
- Concatenation of Array — Easy, same pattern
- Contains Duplicate — Easy, same pattern
Find All Numbers Disappeared in an Array FAQ
What is the LeetCode number of Find All Numbers Disappeared in an Array?
Find All Numbers Disappeared in an Array is LeetCode problem 448, rated Easy.
What pattern is used to solve Find All Numbers Disappeared in an Array?
Find All Numbers Disappeared in an Array is a Cyclic Sort Algorithm problem. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Array - Cyclic Sort subpattern.
What is the time complexity of Find All Numbers Disappeared in an Array?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Find All Numbers Disappeared in an Array?
Find All Numbers Disappeared in an Array has been reported in interviews at Amazon.