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

Find All Duplicates in an Array (LeetCode #442) 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: Use the properties of the input to optimize space and time.

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

The brute force approach for Find All Duplicates in an Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach checks each pair of elements to find duplicates. This is straightforward but inefficient, as it requires checking every combination of numbers. The optimal Optimal Solution approach improves this to O(n).

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

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

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

Explain your thought process clearly. Consider edge cases, like arrays with only one element. Practice identifying patterns in problems.

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

Not handling the negative values correctly. Forgetting to check if a duplicate has already been added.

#442

Find All Duplicates in an Array

Medium

ArrayHash TableSortingHash 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, using the indices to mark visited numbers. This way, we can identify duplicates without extra space for counting.

⚙️

Algorithm

3 steps

1Step 1: Iterate through the array, using the absolute value of each number as an index.
2Step 2: Mark the number at that index by negating it.
3Step 3: If the number at that index is already negative, it means we've seen this number before, so add it to the duplicates list.

solution.py9 lines

1def findDuplicates(nums):
2    duplicates = []
3    for num in nums:
4        index = abs(num) - 1
5        if nums[index] < 0:
6            duplicates.append(abs(num))
7        else:
8            nums[index] = -nums[index]
9    return duplicates

ℹ

Complexity note: This solution runs in linear time because we make a single pass through the array, and we use constant space since we modify the array in place.

1Use the properties of the input to optimize space and time.
2Negating values can help track visited indices without extra space.

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