Start learning free

LESSON 242 OF 347 · HASH TABLE

Find Duplicates in C#: Counting with a Dictionary

Practice O(n) Read the full explanation

Given an array of integers, return a new array containing only the duplicates.

The resulting array's values can be stored in any order.

Example:

Input: [2, 3, 1, 1, 4, 3, 2, 1]
Output: [2, 1, 3]

Note:

Your algorithm should run in O(n) time and use O(n) extra space.


STEP 1 OF 7
    Ctrl + Enter to check

    C# · HASH TABLE

    Find Duplicates in C#, explained

    Problem overview

    The method FindDuplicates receives an int[] nums and returns a new int[] containing every value that appears more than once. Each duplicated value is listed once, and the result may be in any order.

    For [2, 3, 1, 1, 4, 3, 2, 1] the values 1, 2 and 3 repeat, while 4 appears only once. The answer is those three numbers: [2, 1, 3] is one valid order. Note that 1 occurs three times but must appear in the result only once.

    The statement asks for O(n) time and O(n) extra space.

    Approach: count as you go

    Comparing every pair of elements would find the duplicates in O(n²). A faster way is to remember how many times each value has appeared so far. A Dictionary<int, int> does that: the key is the number, and the value is its count. Lookups and updates take constant time on average, so one pass over the array is enough.

    The key observation is when to record a duplicate. The moment a value's count reaches exactly 2, you know it is a duplicate, and you add it to the result. A third or fourth copy raises the count to 3 or 4, which never equals 2 again, so the value is not added twice. Testing for "greater than 1" instead would add it on every later copy.

    On the example, the counts evolve like this. After reading 2, 3, 1 every count is 1. The next 1 raises its count to 2, so 1 goes into the result. Then 4 arrives with count 1, the second 3 reaches 2 and is added, and the second 2 reaches 2 and is added. The last 1 raises its count to 3, which is ignored. The result is [1, 3, 2], the same three values in order of their second appearance.

    Step by step

    1. Create result, a List<int>. The number of duplicates is unknown in advance, and a list can grow, so it is the right place to collect them.
    2. Create freq, a Dictionary<int, int>. It maps each number to how many times it has been seen.
    3. Loop over nums with foreach, using value as the loop variable, so every number is counted.
    4. Increase the count. freq.GetValueOrDefault(value, 0) reads the old count, or 0 when the value has no entry yet. Add 1 and store the sum back with freq[value] = ....
    5. Test freq[value] == 2. This is the exact moment the value becomes a known duplicate.
    6. Add it to result. Every duplicate is recorded once, however many copies follow.
    7. Return result.ToArray(). The method's return type is int[], so the list is converted.

    The solution in C#

    class Solution {
    public int[] FindDuplicates(int[] nums) {
        List<int> result = new List<int>();
        Dictionary<int, int> freq = new Dictionary<int, int>();
        foreach (int value in nums) {
            freq[value] = freq.GetValueOrDefault(value, 0) + 1;
            if (freq[value] == 2) {
                result.Add(value);
            }
        }
        return result.ToArray();
    }
}

    The C# details behind these lines:

    • Missing keys. Reading freq[value] for a key that is not in the dictionary throws a KeyNotFoundException. Assigning to freq[value] is different: it adds the key when it is missing and replaces the value when it exists. The line freq[value] = freq.GetValueOrDefault(value, 0) + 1; relies on both facts. The read side uses GetValueOrDefault so it never throws, and the write side creates the entry.
    • The next line is safe. By the time freq[value] == 2 runs, the assignment above has created the key, so the plain read cannot fail.
    • TryGetValue is the other common pattern. freq.TryGetValue(value, out int count) returns false for a missing key and leaves count at 0. Both styles are fine; GetValueOrDefault is shorter.
    • List<T> versus arrays. An array has a fixed length, while a list grows as you call Add. Collecting into a list and converting once at the end is the usual way to build an array whose size is not known up front.
    • ToArray() on a list. List<T> has its own ToArray() method, so this call needs no using System.Linq;. The generic collections themselves need using System.Collections.Generic;.

    Complexity

    Time: O(n). Each element causes a constant number of dictionary operations (on average) and at most one list append.

    Space: O(n). The dictionary holds one entry per distinct value, which can be n entries, and the result list holds at most half of them.

    Edge cases and common mistakes

    • Empty array or one element. No count reaches 2, so the result is an empty array.
    • No duplicates. [1, 2, 3] returns an empty array.
    • A value repeated many times. [5, 5, 5, 5] returns [5], not four copies.
    • Using >= 2 or > 1. That adds the value again for each extra copy, so the result contains repeats.
    • Reading before writing. Writing freq[value]++ on a missing key throws KeyNotFoundException, because ++ reads first. Use the GetValueOrDefault line, or check ContainsKey first.
    • Depending on the order. The result lists values by their second appearance. The statement allows any order, so a correct solution may differ from the example output.

    Testing

    • [2, 3, 1, 1, 4, 3, 2, 1] gives [1, 3, 2] with this solution, which contains the same values as the example's [2, 1, 3].
    • [5, 5, 5, 5] gives [5].
    • [1, 2, 3] gives [].
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free