#442

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find All Duplicates in an Array

Find all integers that appear twice in an array with O(n) time and constant space complexity.

Problem Statement

Given an integer array nums of length n, where every element is in the range [1, n], the task is to return an array of all integers that appear exactly twice. Each number can only appear once or twice in the array.

The algorithm must operate in O(n) time and use constant auxiliary space, not counting the space needed to store the output array. Efficient scanning and hash lookup strategies are key to achieving this.

Examples

Example 1

Input: nums = [4,3,2,7,8,2,3,1]

Output: [2,3]

Example details omitted.

Example 2

Input: nums = [1,1,2]

Output: [1]

Example details omitted.

Example 3

Input: nums = [1]

Output: []

Example details omitted.

Constraints

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
Each element in nums appears once or twice.

Solution Approach

Array Scanning with Sign Modification

One effective approach is to use the values in the array itself to track seen elements. By modifying the sign of elements at the index corresponding to each value, we can detect duplicates during the array traversal.

Hash Set Tracking

Alternatively, a hash set can be used to store elements as we iterate through the array. If an element is already in the set, it's a duplicate. This approach requires linear time, but also uses extra space for the hash set.

Optimized Hash Lookup with Index Mapping

Another method involves using index mapping by treating each value as an index. By manipulating the values, we can track duplicates in constant space and ensure linear time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this problem depends on the approach used. The optimal solution requires a single pass through the array, ensuring O(n) time complexity. The space complexity varies: using a hash set will take O(n) space, while in-place array modifications reduce space usage to O(1).

What Interviewers Usually Probe

Candidates should demonstrate an understanding of space optimization while solving the problem.
Look for candidates who can explain trade-offs between hash set and in-place modification techniques.
Assess if the candidate can explain how to meet the O(n) time and constant space requirements.

Common Pitfalls or Variants

Common pitfalls

Failing to achieve constant auxiliary space by using extra arrays or hash sets.
Misunderstanding the need for O(n) time complexity, resulting in inefficient solutions.
Incorrectly handling edge cases, such as when the array contains no duplicates.

Follow-up variants

Modify the problem to return only the first duplicate found.
Alter the constraints to allow for numbers appearing more than twice.
Ask for the solution to be implemented without modifying the input array.

FAQ

What is the primary approach for solving 'Find All Duplicates in an Array'?

The primary approach is array scanning using sign modification or hash set tracking to identify duplicates while meeting the time and space requirements.

How do I optimize my solution for constant space?

Optimizing for constant space involves using the array itself to track seen elements, modifying the sign of values at the corresponding index.

Can I use a hash set to solve this problem?

Yes, using a hash set is a valid approach, but it requires extra space and might not meet the constant space constraint.

What if there are no duplicates in the array?

If no duplicates exist, the output should be an empty array, as no values meet the 'appears twice' condition.

How does the pattern 'array scanning plus hash lookup' apply here?

This pattern is used to efficiently scan the array while tracking seen elements, either by modifying the array or using a hash set to detect duplicates.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            while nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        return [v for i, v in enumerate(nums) if v != i + 1]

Continue Practicing

#447 number of boomerangs #448 find all numbers disappeared in an array #454 4sum ii