Saltar al contenido principal

Find All Duplicates in Array

Given an array of integers nums, each element in the array either appears once or twice. Return a list containing all the numbers that appear twice.

Note: Each element in nums is between one and nums.length (inclusive).

Example(s)​

Example 1:

Input: nums = [2, 3, 1, 5, 5]
Output: [5]
Explanation:
- 2 appears once
- 3 appears once
- 1 appears once
- 5 appears twice
Only 5 appears twice.

Example 2:

Input: nums = [1, 2, 3]
Output: []
Explanation:
All numbers appear exactly once, so no duplicates.

Example 3:

Input: nums = [7, 2, 2, 3, 3, 4, 4]
Output: [2, 3, 4]
Explanation:
- 2 appears twice
- 3 appears twice
- 4 appears twice
- 7 appears once

Solution​

The solution uses the array as a hash map:

Since values are between 1 and n (where n = array length), we can use indices as keys:

  1. Use array indices: For each value, use it as an index
  2. Mark visited: Negate the value at that index to mark it as seen
  3. Detect duplicates: If we see a negative value, we've seen this number before
  4. Collect duplicates: Add to result when we find a duplicate

JavaScript Solution - Array as Hash Map

/**
* Find all numbers that appear twice
* @param {number[]} nums - Array of integers (1 to n)
* @return {number[]} - Array of numbers that appear twice
*/
function findDuplicates(nums) {
const result = [];

for (let i = 0; i < nums.length; i++) {
  // Use absolute value since we might have negated it
  const index = Math.abs(nums[i]) - 1;
  
  // If value at index is negative, we've seen this number before
  if (nums[index] < 0) {
    result.push(Math.abs(nums[i]));
  } else {
    // Mark as seen by negating
    nums[index] = -nums[index];
  }
}

return result;
}

// Test cases
console.log('Example 1:', findDuplicates([2, 3, 1, 5, 5])); // [5]
console.log('Example 2:', findDuplicates([1, 2, 3])); // []
console.log('Example 3:', findDuplicates([7, 2, 2, 3, 3, 4, 4])); // [2, 3, 4]
console.log('Test 4:', findDuplicates([4, 3, 2, 7, 8, 2, 3, 1])); // [2, 3]
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Hash Set)​

Here's a simpler approach using a hash set:

/**
 * Hash set approach (simpler but uses O(n) space)
 */
function findDuplicatesHashSet(nums) {
  const seen = new Set();
  const result = [];
  
  for (const num of nums) {
    if (seen.has(num)) {
      result.push(num);
    } else {
      seen.add(num);
    }
  }
  
  return result;
}

Alternative: Frequency Counter​

Here's an approach using frequency counting:

/**
 * Frequency counter approach
 */
function findDuplicatesFrequency(nums) {
  const frequency = new Map();
  
  // Count frequencies
  for (const num of nums) {
    frequency.set(num, (frequency.get(num) || 0) + 1);
  }
  
  // Find all numbers that appear twice
  const result = [];
  for (const [num, count] of frequency.entries()) {
    if (count === 2) {
      result.push(num);
    }
  }
  
  return result;
}

Complexity​

  • Time Complexity:
    • Array as hash map: O(n) - Single pass through the array
    • Hash set: O(n) - Single pass through the array
    • Frequency counter: O(n) - Count frequencies, then filter
  • Space Complexity:
    • Array as hash map: O(1) - Only uses result array (not counted in space complexity)
    • Hash set: O(n) - For the hash set
    • Frequency counter: O(n) - For the frequency map

Approach​

The optimal solution uses the array as a hash map:

  1. Key insight: Since values are between 1 and n, we can use indices 0 to n-1
  2. Marking technique:
    • For value x, check index x - 1
    • If nums[x-1] is negative, we've seen x before → it's a duplicate
    • Otherwise, negate nums[x-1] to mark x as seen
  3. Absolute value: Use Math.abs() since we negate values
  4. Collect duplicates: Add to result when we detect a duplicate

Key Insights​

  • Array as hash map: Leverages the constraint that values are 1 to n
  • Negation trick: Use negative sign to mark visited without extra space
  • O(1) space: Optimal space complexity (excluding result array)
  • Single pass: Process array once
  • Index mapping: Value x maps to index x - 1

Step-by-Step Example​

Let's trace through Example 1: nums = [2, 3, 1, 5, 5]

Initial: nums = [2, 3, 1, 5, 5]
         result = []

i = 0: nums[0] = 2
  index = abs(2) - 1 = 1
  nums[1] = 3 (positive, not seen)
  nums[1] = -3 (mark as seen)
  nums = [2, -3, 1, 5, 5]

i = 1: nums[1] = -3
  index = abs(-3) - 1 = 2
  nums[2] = 1 (positive, not seen)
  nums[2] = -1 (mark as seen)
  nums = [2, -3, -1, 5, 5]

i = 2: nums[2] = -1
  index = abs(-1) - 1 = 0
  nums[0] = 2 (positive, not seen)
  nums[0] = -2 (mark as seen)
  nums = [-2, -3, -1, 5, 5]

i = 3: nums[3] = 5
  index = abs(5) - 1 = 4
  nums[4] = 5 (positive, not seen)
  nums[4] = -5 (mark as seen)
  nums = [-2, -3, -1, 5, -5]

i = 4: nums[4] = -5
  index = abs(-5) - 1 = 4
  nums[4] = -5 (negative, already seen!)
  result.push(5)
  result = [5]

Final: result = [5]

Visual Representation​

Example 1: nums = [2, 3, 1, 5, 5]

Value → Index mapping:
  2 → index 1
  3 → index 2
  1 → index 0
  5 → index 4

Process:
  See 2 → mark index 1
  See 3 → mark index 2
  See 1 → mark index 0
  See 5 → mark index 4
  See 5 → index 4 already marked → duplicate!

Result: [5]

Edge Cases​

  • No duplicates: Return empty array
  • All duplicates: If all appear twice, return all values
  • Single element: Return empty array (can't have duplicate of one)
  • All same value: If all are the same and appear twice, return that value
  • Large array: Works efficiently with O(n) time

Important Notes​

  • Values 1 to n: Constraint allows using indices as hash keys
  • In-place marking: Negation doesn't require extra space
  • Absolute value: Must use abs() since we negate values
  • Modifies input: The optimal solution modifies the input array
  • Result order: Order of duplicates in result may vary

Why Array as Hash Map Works​

Since values are between 1 and n:

  • Value x can be used as index x - 1
  • We have exactly n indices (0 to n-1)
  • Perfect hash function: no collisions
  • Can mark visited by negating the value at that index
  • Find the Duplicate Number: Find one duplicate (different constraint)
  • Contains Duplicate: Check if duplicates exist
  • First Missing Positive: Similar array manipulation
  • Set Mismatch: Find duplicate and missing number

Takeaways​

  • Array as hash map is powerful when values are 1 to n
  • Negation trick marks visited without extra space
  • O(1) space is achievable with careful manipulation
  • Single pass is optimal
  • Constraint utilization is key to optimization