Start learning free

LESSON 240 OF 674 · SETS

Only In First in C#: List Difference With HashSets

Practice Read the full explanation

You get two Lists of integers, a and b.

Return a new List with the values of a that are not in b.

Each value goes into the result only once. Keep the values in the order they first appear in a.

If every value of a is also in b, return an empty List.

 

Example 1:

Input: a = [1, 2, 3, 4], b = [2, 4]
Output: [1, 3]
Explanation: 2 and 4 are in b, so they are left out.

Example 2:

Input: a = [5, 6, 5, 7], b = [7]
Output: [5, 6]
Explanation: 7 is in b.
5 appears twice in a, but only once in the result.

Example 3:

Input: a = [1, 2], b = [2, 3, 1]
Output: []
Explanation: Both values of a are also in b, so nothing is left.

 

Constraints:

  • a and b each have at least one number.
  • Every number is between -109 and 109.
STEP 1 OF 8
    Ctrl + Enter to check

    C# · SETS

    Only In First in C#, explained

    Problem overview

    The method OnlyInFirst gets two lists of integers, a and b. It returns a new list with the values of a that are not in b. Each value goes into the result once, in the order it first appears in a. If every value of a is also in b, the result is an empty list.

    For a = [1, 2, 3, 4] and b = [2, 4] the answer is [1, 3]. For a = [5, 6, 5, 7] and b = [7] it is [5, 6]: 7 is in b, and 5 appears twice in a but once in the result. For a = [1, 2] and b = [2, 3, 1] the result is empty.

    Approach

    The method has two jobs, and each gets a set:

    • "Is this value in b?" A set built from b, named setB, answers this quickly. Repeats in b collapse into one, which doesn't matter for a membership check.
    • "Is this value already in the result?" A second set, seen, remembers what was added. This is the same idea as removing repeats from a list.

    The list result keeps the order. Read a from left to right, and keep a value when it is not in setB and not in seen.

    Step by step

    1. Build setB with new HashSet<int>(b).
    2. Create an empty set seen and an empty list result.
    3. Loop over a with foreach, so values are met in their first-appearance order.
    4. Join two tests with &&: !setB.Contains(num) and !seen.Contains(num). Both must be true.
    5. Inside the if, add num to result and to seen.
    6. Return result after the loop. It may be empty.

    The solution in C#

    class Solution {
    public List<int> OnlyInFirst(List<int> a, List<int> b) {
        HashSet<int> setB = new HashSet<int>(b);
        HashSet<int> seen = new HashSet<int>();
        List<int> result = new List<int>();
        foreach (int num in a) {
            if (!setB.Contains(num) && !seen.Contains(num)) {
                result.Add(num);
                seen.Add(num);
            }
        }
        return result;
    }
}

    The details worth knowing:

    • && stops as soon as its left side is false, so a value found in setB never reaches the second test.
    • An empty List<int> is a valid return value; there is no need for null.
    • The method doesn't change a or b.

    Why sets here

    The same task works with only lists, by calling b.Contains(num) and result.Contains(num) for every number of a. That is correct, but each of those calls scans a list. A set finds a value directly, so each check stays fast however long the lists are. The lists in this lesson are small, but the habit of turning "is it in there?" into a set pays off as soon as the data grows.

    Notice also that the two sets play different roles. setB never changes after it is built. seen starts empty and grows as the loop goes, always matching the values already in result.

    Tracing the second example

    Here setB holds only 7, and seen starts empty.

    numkept?result after
    5yes[5]
    6yes[5, 6]
    5no, already in seen[5, 6]
    7no, in setB[5, 6]

    Testing

    On the statement's three examples, the method returns:

    [1, 3]
[5, 6]
[]

    Edge cases and common mistakes

    • Forgetting seen. Without it, the second example returns [5, 6, 5], because the second 5 is also not in b.
    • Using lists for the checks. b.Contains(num) works, but it compares against the values of b one by one for every number; a set avoids that.
    • Using || instead of &&. With || a value in b but not yet in seen would be kept.
    • Losing the order. Building the answer from a set operation alone gives no promise about order; looping over a in order does.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free