Start learning free

LESSON 237 OF 671 · SETS

Only in the First List in Java: Difference With HashSet

Practice Read the full explanation

You get two ArrayLists of integers, a and b.

Return a new ArrayList 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 ArrayList.

 

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

    JAVA · SETS

    Only In First in Java, explained

    Problem overview

    The method onlyInFirst receives 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 only once, and the values keep the order in which they first appear 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 result is [1, 3]. For a = [5, 6, 5, 7] and b = [7] the result is [5, 6]: 7 is in b, and 5 appears twice in a but only once in the result. For a = [1, 2] and b = [2, 3, 1] nothing is left, so the result is [].

    Approach

    There are two questions for each number of a: is it in b, and is it already in the result? Both are "is this value in a collection" questions, and a HashSet answers those quickly. Putting the values of b in a set makes the first question cheap. A second set, seen, remembers which values were already put in the result, which handles the repeats inside a. A list still holds the result, because it keeps the order.

    Step by step

    1. Create setB, a HashSet<Integer> built from b. Repeats in b collapse into one, which is fine for a membership check.
    2. Create an empty HashSet<Integer> named seen.
    3. Create an empty List<Integer> named result.
    4. Loop over a from left to right, with an int named num. Reading in order keeps the order of first appearance.
    5. Inside the loop, check that num is not in setB and not in seen, joined with &&. Both must be true.
    6. Inside the if, add num to result.
    7. Also add num to seen, so a later copy is skipped.
    8. After the loop, return result. It may be empty.

    The solution in Java

    class Solution {
    public List<Integer> onlyInFirst(List<Integer> a, List<Integer> b) {
        HashSet<Integer> setB = new HashSet<>(b);
        HashSet<Integer> seen = new HashSet<>();
        List<Integer> result = new ArrayList<>();
        for (int num : a) {
            if (!setB.contains(num) && !seen.contains(num)) {
                result.add(num);
                seen.add(num);
            }
        }
        return result;
    }
}

    The lists hold Integer objects, and the loop variable is an int. Java converts between them for you. In the condition, && stops as soon as the left side is false, so a value that is in b is rejected without looking at seen.

    Tracing the second example: 5 is not in setB (which holds only 7) and not in seen, so it goes in the result. 6 does the same. The second 5 is in seen and is skipped. 7 is in setB and is skipped. The result is [5, 6].

    The first example runs without the second set doing any work. 1 and 3 are not in setB, which holds 2 and 4, so they go in the result in that order. 2 and 4 are in setB, so they are skipped. The third example shows the empty case: both 1 and 2 are in setB, so nothing is added and the method returns an empty list.

    Edge cases and common mistakes

    • Skipping seen. Then the second 5 would be added again and the result would be [5, 6, 5].
    • Using b.contains directly. A list's contains scans its values one by one. Building setB once is faster for long lists.
    • Using || instead of &&. A number would be kept when only one of the two checks passes.
    • Removing from a. The method should build a new list and leave its inputs alone.

    Testing

    Running the solution on the three examples gives:

    [1, 3]
[5, 6]
[]
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free