Start learning free

LESSON 236 OF 667 · SETS

Only in the First in C++: Difference of Two Vectors

Practice Read the full explanation

You get two vectors of integers, a and b.

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

 

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 function onlyInFirst gets two vectors of integers, a and b, and returns a new vector 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 empty.

    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 answer is empty. The tests print a vector as its values separated by spaces.

    Approach

    Two questions are asked about each number of a: is it in b, and is it already in the result? A vector answers each question by scanning it. A set answers with one lookup, so the code uses two sets:

    • setB holds the values of b. Repeats in b collapse into one, which doesn't matter for a membership test.
    • seen holds the values already put in the result, which stops a repeated value of a from going in twice. It is the same idea as removing repeats from a single vector.

    The result vector itself keeps the order.

    Two sets are not always needed. If the task allowed the result in any order, one set would be enough. The order requirement is the reason the result is a vector, and the vector is the reason the second set exists.

    Step by step

    1. Build setB from b.begin() and b.end().
    2. Create an empty seen set of int.
    3. Create an empty result vector of int.
    4. Loop over a from left to right with an int named num, so the first appearance decides the order.
    5. Test both conditions: setB.count(num) == 0 and seen.count(num) == 0, joined with &&. Both must hold.
    6. Add num to the end of result with push_back.
    7. Add num to seen with insert.
    8. Return result after the loop. It can be empty.

    The solution in C++

    class Solution {
public:
    vector<int> onlyInFirst(vector<int>& a, vector<int>& b) {
        unordered_set<int> setB(b.begin(), b.end());
        unordered_set<int> seen;
        vector<int> result;
        for (int num : a) {
            if (setB.count(num) == 0 && seen.count(num) == 0) {
                result.push_back(num);
                seen.insert(num);
            }
        }
        return result;
    }
};

    Notes on the C++:

    • If the numbers 5, 6, 5 and 7 are checked against b = {7}, the first 5 and the 6 pass both tests; the second 5 fails the seen test; the 7 fails the setB test.
    • && stops at the first false test, so seen is only consulted for values that are not in b.

    Complexity

    Time is O(n + m) on average, where n is the size of a and m the size of b: building setB costs m inserts and the loop costs n constant-time lookups. Space is O(n + m) for the two sets and the result.

    Edge cases and common mistakes

    • Dropping the seen check. For {5, 6, 5, 7} and {7} the result would be 5 6 5, which breaks "each value once".
    • Using || instead of &&. A value that is in b but not yet seen would still be added.
    • Checking a against b with nested loops. It gives the right answer but scans b for every number.
    • Everything removed. When all values of a are in b, nothing is added and the empty vector is returned, which is correct.

    Testing

    • a = {1, 2, 3, 4}, b = {2, 4} gives 1 3.
    • a = {5, 6, 5, 7}, b = {7} gives 5 6.
    • a = {1, 2}, b = {2, 3, 1} gives an empty vector.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free