Start learning free

LESSON 120 OF 667 · ARRAYS - CHALLENGES

Add If Missing: Avoiding Duplicates in a C++ Vector

Practice Read the full explanation

You get a shopping list items, a vector of strings, and a word item. Add item at the end only when it isn't in the list yet. Return the list.

When item is already there, the list stays as it is. The list may start empty.

 

Example 1:

Input: items = ["milk", "eggs"], item = "bread"
Output: ["milk", "eggs", "bread"]
Explanation: The word "bread" is not in the list yet.
It goes at the end.

Example 2:

Input: items = ["milk", "eggs"], item = "milk"
Output: ["milk", "eggs"]
Explanation: The word "milk" is already there.
Nothing is added.

Example 3:

Input: items = [], item = "apples"
Output: ["apples"]
Explanation: The list is empty, so "apples" is new.
It becomes the only item.

 

Constraints:

  • items has 0 to 9 words: it may be empty.
  • item and every word in items are made of lowercase English letters.
STEP 1 OF 3
    Ctrl + Enter to check

    C++ · ARRAYS - CHALLENGES

    Add If Missing in C++, explained

    Problem overview

    The method addIfMissing gets a shopping list items, a vector<string>, and a word item. It adds item at the end of the list only when the list does not have it yet, and returns the list. The list may start empty.

    With ["milk", "eggs"] and "bread", the answer is ["milk", "eggs", "bread"]. With "milk" instead, the list stays ["milk", "eggs"]. With an empty list and "apples", the answer is ["apples"].

    Approach

    This is the membership check with an action attached. find(items.begin(), items.end(), item) searches the vector for the word and returns the position of the first match, or items.end() when there is none. If the result equals items.end(), the word is missing, so you add it with push_back. Otherwise you do nothing.

    An empty list needs no special case: the search range is empty, so find returns items.end() straight away, and the word is added.

    Step by step

    1. Write an if whose condition is find(items.begin(), items.end(), item) == items.end(). It is true only when the word is not in the list.
    2. Inside the if, call items.push_back(item). This runs only for a new word, so the list never gets the same word twice.
    3. After the if, return items. When the word was already there, the list comes back as it was.

    The solution in C++

    class Solution {
public:
    vector<string> addIfMissing(vector<string> &items, string item) {
        if (find(items.begin(), items.end(), item) == items.end()) {
            items.push_back(item);
        }
        return items;
    }
};

    Running the method on the statement's examples, with the results printed in bracket notation:

    ["milk", "eggs", "bread"]
["milk", "eggs"]
["apples"]

    Calling it a second time with "apples" on the list that now holds ["apples"] returns ["apples"] again, so repeated calls never create duplicates. The list is passed by reference, so the caller's own vector changes too.

    Why not just push and remove duplicates later

    A tempting alternative is to always call push_back and clean up afterwards. That is more work and easy to get wrong: the check-then-add pattern keeps the list correct at every moment, so no other code ever sees a duplicate. The same pattern appears whenever you build a collection of unique values, such as names, tags or ids.

    If order does not matter and you need many lookups, a set is a better fit than a vector, but this lesson keeps the order of insertion, which a vector does naturally.

    Complexity

    Time is O(n) for a list of n words, because find may look at every word. Space is O(1) extra, apart from the one word that may be added.

    Edge cases and common mistakes

    • Wrong comparison. With != instead of ==, the word is added only when it is already there, which is the opposite of the task.
    • Different letter case. The match is exact. Adding "Milk" to ["milk"] adds it, giving ["milk", "Milk"]. The constraints say all words are lowercase, so this does not come up in the tests.
    • Adding before the check. If you call push_back first and check afterwards, the word is always found.
    • Forgetting the return. The method must return the vector in both cases, not only when it added a word, so put the return after the if.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free