Start learning free

LESSON 240 OF 347 · HASH TABLE

Distinct Values in C#: Counting with a HashSet in O(n)

Practice O(n) Read the full explanation

Given an array of integers, count how many distinct values exist in the array.

Example:

Input: [1, 5, -3, 1, -4, 2, -4, 7, 7]
Output: 6
Explanation: the distinct values in the array are [1, 5, -3, -4, 2, 7]

Note:

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


STEP 1 OF 6
    Ctrl + Enter to check

    C# · HASH TABLE

    Distinct Values in C#, explained

    Problem overview

    The method DistinctValues receives an int[] nums and returns how many different values it contains. Each value counts once, however often it appears.

    For [1, 5, -3, 1, -4, 2, -4, 7, 7] the distinct values are 1, 5, -3, -4, 2, 7, so the answer is 6. The array has nine elements, but 1, -4 and 7 each appear twice.

    The statement asks for O(n) time and O(n) extra space. Memory is allowed to grow with the input, and that is what makes a fast solution possible.

    Approach: remember what you have already seen

    The slow way compares every element with every other one, or counts how often each value occurs by scanning the array again and again. That is O(n²). Sorting first and counting where the value changes gives O(n log n) without extra memory. Spending O(n) memory buys a better time.

    The faster idea is to keep a HashSet<int> of the values seen so far. A hash set answers "is this value in the set?" in constant time on average, so each element costs one lookup. When a value is not in the set yet, it is new: add it and count it. When it is already there, skip it.

    The sorting version works like this: after Array.Sort(nums), equal values sit next to each other, so you count the positions where an element differs from the one before it. It needs no set, but it reorders the caller's array unless you copy it first. The set version leaves nums untouched, which is another reason to prefer it when memory is not a concern.

    Step by step

    1. Create an empty HashSet<int> called values. It is the memory of everything seen so far.
    2. Create answer, an int starting at 0. It counts the distinct values found.
    3. Loop over nums with foreach. The loop variable value takes each element in turn, and every element is examined once. The order does not matter for counting.
    4. Check !values.Contains(value). The ! flips the answer, so the body runs only the first time a number shows up.
    5. Inside the if, add the value and increment the counter. After values.Add(value), every later copy of that number is found in the set and skipped.
    6. Return answer.

    Walking through the example

    Take [1, 5, -3, 1, -4], the start of the example, with an empty set and answer = 0:

    1. 1 is not in the set, so it is added and answer becomes 1.
    2. 5 is new, so the set holds {1, 5} and answer is 2.
    3. -3 is new, so answer is 3.
    4. 1 is already in the set, so nothing changes.
    5. -4 is new, so answer is 4.

    The remaining elements 2, -4, 7, 7 add 2 and 7 and skip the repeats, which brings the total to 6. At every point, answer equals the number of elements in the set.

    The solution in C#

    class Solution {
    public int DistinctValues(int[] nums) {
        HashSet<int> values = new HashSet<int>();
        int answer = 0;
        foreach (int value in nums) {
            if (!values.Contains(value)) {
                values.Add(value);
                answer++;
            }
        }
        return answer;
    }
}

    Some C# details worth knowing:

    • Namespace. HashSet<T> lives in System.Collections.Generic. In a file of your own you need using System.Collections.Generic; at the top (new projects often include it automatically).
    • Add returns a bool. It returns true when the value was new and false when the set already held it. A set never stores a value twice.
    • The shorter form. Because of that return value, the Contains check and the Add can be merged: if (values.Add(value)) answer++;. The lesson keeps them separate so each step is visible.
    • Even shorter. The counter is redundant, since values.Count is the number of distinct values at the end. Many C# programmers write new HashSet<int>(nums).Count, which builds the set straight from the array. The lesson's version practises the loop.
    • Value equality. For int, the set compares the numbers themselves, so two equal numbers are always the same entry.

    Complexity

    Time: O(n). The loop runs n times. In each iteration Contains and Add take constant time on average, so the total is linear.

    Space: O(n). In the worst case every element is different and the set holds all n values. The sorting alternative needs no set, but it costs O(n log n) time.

    Edge cases and common mistakes

    • Empty array. The loop never runs and the method returns 0.
    • All values equal. [7, 7, 7] gives 1: the first 7 is counted and the others are skipped.
    • All values different. [4, 5, 6] gives 3, and the set ends up as large as the array.
    • Negative numbers. They are ordinary values to a hash set. -4 and 4 are two different entries.
    • Counting every element. If answer++ sits outside the if, the method returns the length of the array instead of the number of distinct values.
    • Forgetting Add. Without it the set stays empty, nothing is ever "seen", and again every element is counted.

    Testing

    • [1, 5, -3, 1, -4, 2, -4, 7, 7] gives 6.
    • [7, 7, 7] gives 1.
    • [] gives 0.
    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