How do you solve Find All Numbers Disappeared in an Array on LeetCode?

Find All Numbers Disappeared in an Array (LeetCode #448) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The input array can be modified to track the presence of numbers without using extra space.

What is the brute force solution for Find All Numbers Disappeared in an Array?

The brute force approach for Find All Numbers Disappeared in an Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each number from 1 to n and sees if it exists in the input array. This is straightforward but inefficient as it requires multiple passes over the data. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Find All Numbers Disappeared in an Array?

Find All Numbers Disappeared in an Array uses the following concepts: Array, Hash Table. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Find All Numbers Disappeared in an Array?

Always clarify if modifying the input array is allowed. Think about how you can use the properties of the input data to simplify your solution. Practice explaining your thought process as you code; it helps in interviews.

What are common mistakes when solving Find All Numbers Disappeared in an Array?

Not considering the possibility of modifying the input array. Overcomplicating the problem by using additional data structures when it's not necessary.

#448

Find All Numbers Disappeared in an Array

Easy

ArrayHash TableHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages the properties of the input array itself to mark the presence of numbers. By using the indices of the array, we can identify which numbers are missing without using extra space.

⚙️

Algorithm

3 steps

1Step 1: Iterate through the array and for each number, mark its corresponding index as negative to indicate that the number exists.
2Step 2: Iterate through the array again. The indices that remain positive correspond to the missing numbers.
3Step 3: Collect these indices (adjusted for 1-based indexing) into the result list.

solution.py7 lines

1# Full working Python code
2
3def findDisappearedNumbers(nums):
4    for num in nums:
5        index = abs(num) - 1
6        nums[index] = -abs(nums[index])
7    return [i + 1 for i in range(len(nums)) if nums[i] > 0]

ℹ

Complexity note: The time complexity is O(n) because we traverse the array a constant number of times. The space complexity is O(1) since we modify the input array in place without using additional data structures.

1The input array can be modified to track the presence of numbers without using extra space.
2The range of numbers is guaranteed to be from 1 to n, which allows us to use the indices directly.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.