Start learning free

LESSON 119 OF 667 · ARRAYS - CHALLENGES

Move an Item to the Front of a Vector in C++

Practice Read the full explanation

You get a to-do list items, a vector of strings, and a number index. Return the list with the item at index moved to the front.

Take the item out of its place and put it at index 0. The other items keep their order.

 

Example 1:

Input: items = ["wash", "shop", "cook", "read"], index = 2
Output: ["cook", "wash", "shop", "read"]
Explanation: The item at index 2 is "cook". It moves to the front.
Then "wash" and "shop" move one place to the right.

Example 2:

Input: items = ["tea", "coffee"], index = 0
Output: ["tea", "coffee"]
Explanation: The item at index 0 is already at the front.
Nothing changes.

Example 3:

Input: items = ["call", "pay", "call", "walk"], index = 2
Output: ["call", "call", "pay", "walk"]
Explanation: The "call" at index 2 moves to the front.
The other "call" and "pay" move one place to the right.

 

Constraints:

  • items has 1 to 10 words.
  • index is from 0 to the length of items minus 1.
  • Every word is made of lowercase English letters.
  • The same word may appear more than once.
STEP 1 OF 4
    Ctrl + Enter to check

    C++ · ARRAYS - CHALLENGES

    Move To Front in C++, explained

    Problem overview

    The method moveToFront gets a to-do list items, a vector<string>, and a number index. It returns the list with the item at index moved to index 0. The other items keep their order.

    For ["wash", "shop", "cook", "read"] and index = 2, the item at index 2 is "cook". It goes to the front, and "wash" and "shop" each move one place to the right, giving ["cook", "wash", "shop", "read"]. If index is 0, nothing visible changes.

    Approach

    A vector has no "move" operation, but you can do it in three moves: take a copy of the item, erase it from its old place, and insert the copy at the front. Both erase and insert take positions built from items.begin().

    The order of these moves matters. The copy must be saved before the erase, since after the erase the item is gone from the vector.

    Step by step

    1. Save items[index] in a string named item.
    2. Call items.erase(items.begin() + index). The items behind that place shift one place to the left.
    3. Call items.insert(items.begin(), item). The front place is items.begin(). Every other item shifts one place to the right. When index is 0, the item goes back where it was.
    4. Return items.

    The solution in C++

    class Solution {
public:
    vector<string> moveToFront(vector<string> &items, int index) {
        string item = items[index];
        items.erase(items.begin() + index);
        items.insert(items.begin(), item);
        return items;
    }
};

    string item is a copy, not a reference. A reference such as string& item = items[index]; would point into the vector, and it would not be valid after the erase.

    The vector is passed by reference, so the method changes the caller's vector as well as returning it. For example, with ["a", "b", "c"] and index = 1, the caller's own vector becomes ["b", "a", "c"] afterwards.

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

    ["cook", "wash", "shop", "read"]
["tea", "coffee"]
["call", "call", "pay", "walk"]

    The third one has two "call" items. Only the one at index 2 moves, so the other one stays right behind it. That works because the code uses the index, not the word.

    Another way

    The standard library has rotate, which does the whole move in one call: rotate(items.begin(), items.begin() + index, items.begin() + index + 1);. It would pass the tests too, but the erase-and-insert version shows each step.

    Trying more inputs

    Try ["a", "b", "c"] with index = 2: the last item moves to the front and the result is ["c", "a", "b"]. With index = 1 the middle item moves and the result is ["b", "a", "c"]. A one-item list comes back unchanged.

    Complexity

    Time is O(n): both erase and insert shift up to n items. Space is O(1) extra, since the changes are made in the vector itself.

    Edge cases and common mistakes

    • Inserting before saving. Insert first and the indexes change, so items[index] may be a different item. Save, then erase, then insert.
    • Erasing by value. Removing the word instead of the position would be wrong for duplicates: the first "call" could go instead of the one at index 2.
    • Passing a number to erase. erase and insert need a position, such as items.begin() + index.
    • One item or index 0. The item is erased and put back at the same place. The result is the same list.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free