Write a function to find all duplicate elements in a list of integers. Return a list of unique duplicates (each duplicate should appear only once in the result).

Overview

Finding duplicates in a list is a fundamental problem that tests your understanding of hash-based data structures and algorithmic efficiency. The challenge is to identify elements that appear more than once while ensuring each duplicate appears only once in the result.

This problem commonly appears in data processing, deduplication tasks, and detecting anomalies in datasets.

Approach 1: Hash Set (Optimal)

Track seen elements with a Set for O(n) time complexity.

dartCopy
List<int> findDuplicates(List<int> nums) {
  Set<int> seen = {};
  Set<int> duplicates = {};

  for (int num in nums) {
    if (seen.contains(num)) {
      duplicates.add(num);
    } else {
      seen.add(num);
    }
  }

  return duplicates.toList();
}

void main() {
  print(findDuplicates([1, 2, 3, 2, 4, 5, 1, 6]));
  // Output: [2, 1]

  print(findDuplicates([5, 5, 5, 5]));
  // Output: [5]

  print(findDuplicates([1, 2, 3, 4, 5]));
  // Output: []
}

Time Complexity: O(n) - single pass through the list Space Complexity: O(n) - Set storage for seen elements

Approach 2: Frequency Map

Use a Map to count occurrences, then filter duplicates.

dartCopy
List<int> findDuplicatesMap(List<int> nums) {
  Map<int, int> frequency = {};

  // Count occurrences
  for (int num in nums) {
    frequency[num] = (frequency[num] ?? 0) + 1;
  }

  // Extract elements with count > 1
  return frequency.entries
      .where((entry) => entry.value > 1)
      .map((entry) => entry.key)
      .toList();
}

void main() {
  print(findDuplicatesMap([1, 2, 3, 2, 4, 5, 1, 6]));
  // Output: [1, 2]

  print(findDuplicatesMap([7, 7, 8, 8, 8, 9]));
  // Output: [7, 8]
}

Time Complexity: O(n) Space Complexity: O(n) - Map storage

Approach 3: Sorted List (Space Optimized)

Sort first, then find adjacent duplicates. Uses less memory if in-place sorting is acceptable.

dartCopy
List<int> findDuplicatesSorted(List<int> nums) {
  if (nums.isEmpty) return [];

  List<int> sorted = List.from(nums)..sort();
  Set<int> duplicates = {};

  for (int i = 1; i < sorted.length; i++) {
    if (sorted[i] == sorted[i - 1]) {
      duplicates.add(sorted[i]);
    }
  }

  return duplicates.toList();
}

void main() {
  print(findDuplicatesSorted([1, 2, 3, 2, 4, 5, 1, 6]));
  // Output: [1, 2]
}

Time Complexity: O(n log n) - sorting dominates Space Complexity: O(1) - if in-place sort, otherwise O(n)

Approach 4: Functional Style

Using Dart's functional methods for concise code.

dartCopy
List<int> findDuplicatesFunctional(List<int> nums) {
  return nums
      .toSet()
      .where((element) => nums.where((x) => x == element).length > 1)
      .toList();
}

void main() {
  print(findDuplicatesFunctional([1, 2, 3, 2, 4, 5, 1]));
  // Output: [1, 2]
}

Time Complexity: O(n²) - nested where operations Space Complexity: O(n)

Note: Less efficient but more readable for small datasets.

Complete Solution Class

dartCopy
class DuplicateFinder {
  static List<int> find(List<int> nums) {
    if (nums.isEmpty) return [];

    Set<int> seen = {};
    Set<int> duplicates = {};

    for (int num in nums) {
      if (seen.contains(num)) {
        duplicates.add(num);
      } else {
        seen.add(num);
      }
    }

    return duplicates.toList();
  }

  static Map<int, int> findWithCounts(List<int> nums) {
    Map<int, int> frequency = {};

    for (int num in nums) {
      frequency[num] = (frequency[num] ?? 0) + 1;
    }

    return Map.fromEntries(
      frequency.entries.where((e) => e.value > 1),
    );
  }

  static List<int> findPreservingOrder(List<int> nums) {
    Set<int> seen = {};
    List<int> duplicates = [];

    for (int num in nums) {
      if (seen.contains(num) && !duplicates.contains(num)) {
        duplicates.add(num);
      } else {
        seen.add(num);
      }
    }

    return duplicates;
  }
}

Comparison

*Assumes in-place sorting

Edge Cases

dartCopy
void testEdgeCases() {
  // Empty list
  assert(findDuplicates([]).isEmpty);

  // No duplicates
  assert(findDuplicates([1, 2, 3, 4, 5]).isEmpty);

  // All duplicates
  assert(findDuplicates([1, 1, 1, 1]) == [1]);

  // Single element
  assert(findDuplicates([5]).isEmpty);

  // Two elements - duplicate
  assert(findDuplicates([3, 3]) == [3]);

  // Negative numbers
  assert(findDuplicates([-1, -2, -1]).contains(-1));

  // Mixed positive and negative
  assert(findDuplicates([1, -1, 1, -1]).length == 2);
}

Best Practices

1. Use Hash Set for Optimal Performance

dartCopy
// ✅ Recommended
List<int> findDups(List<int> nums) {
  Set<int> seen = {}, dups = {};
  for (int n in nums) {
    seen.contains(n) ? dups.add(n) : seen.add(n);
  }
  return dups.toList();
}

2. Handle Null Safety

dartCopy
List<int> findDuplicatesSafe(List<int>? nums) {
  if (nums == null || nums.isEmpty) return [];
  // ... rest of logic
}

3. Preserve Insertion Order If Needed

dartCopy
// Use LinkedHashSet to maintain order
Set<int> duplicates = LinkedHashSet<int>();

4. Consider Generic Implementation

dartCopy
List<T> findDuplicates<T>(List<T> items) {
  Set<T> seen = {}, duplicates = {};
  for (T item in items) {
    seen.contains(item) ? duplicates.add(item) : seen.add(item);
  }
  return duplicates.toList();
}

// Works with any type
print(findDuplicates(['a', 'b', 'a', 'c'])); // [a]

Real-World Applications

1. Data Validation

dartCopy
bool hasNoDuplicateEmails(List<String> emails) {
  return findDuplicates(emails.map((e) => e.toLowerCase()).toList()).isEmpty;
}

2. Detecting Duplicate IDs

dartCopy
List<int> findDuplicateUserIds(List<User> users) {
  return findDuplicates(users.map((u) => u.id).toList());
}

3. Remove Duplicate Form Submissions

dartCopy
List<FormSubmission> removeDuplicates(List<FormSubmission> submissions) {
  Set<String> seen = {};
  return submissions.where((s) => seen.add(s.id)).toList();
}

Resources

• Set Class - Dart API
• Map Class - Dart API
• Hash Table - Wikipedia