Advanced Vector Manipulation in C++

In this lesson, we'll tackle Advanced Vector Manipulation, a crucial topic in any technical interview. C++ vectors are versatile and powerful data structures used in almost every aspect of programming. Mastering advanced manipulation techniques can streamline your code, optimize time complexity, and solve complex problems efficiently.

Merge Sort is one of the most common sorting algorithms tested in coding interviews. Merge Sort takes in two vectors sorted in ascending order. The output should efficiently merge them into a single sorted vector. For example, merging {1, 3, 5, 7} and {2, 4, 6, 8} yields {1, 2, 3, 4, 5, 6, 7, 8}.

The mergeSortedVectors algorithm is designed to merge two sorted vectors into a single sorted vector. The algorithm employs the Two Pointer Technique to efficiently accomplish this task with a linear time complexity of O(n + m), where n and m are the sizes of the two input vectors. Here is an overview of the algorithm:

1. Initialization: Create an empty vector mergedVector to store the result. Initialize two pointers (or indices), i and j, to zero; these pointers will traverse vec1 and vec2, respectively.

2. Traverse Both Vectors: Use a while loop to iterate through both vectors until one of the pointers reaches the end of its respective vector.

   • Comparison: In each iteration, compare the elements pointed to by i and j.
   • Appending Smaller Element: Append the smaller element to mergedVector and increment the corresponding pointer.

3. Append Remaining Elements: Once one vector is fully traversed, append the remaining elements of the other vector to mergedVector.

   • Remaining Elements of vec1: Use a while loop to append remaining elements of vec1, if any.
   • Remaining Elements of vec2: Use a while loop to append remaining elements of vec2, if any.

4. Return Result: The mergedVector now contains all elements from vec1 and vec2 in sorted order.

This approach ensures that the merging process is performed in an efficient manner, taking advantage of the pre-sorted nature of the input vectors.

Here's how to implement this in C++:

#include <iostream>
#include <vector>

std::vector<int> mergeSortedVectors(const std::vector<int>& vec1, const std::vector<int>& vec2) {
    std::vector<int> mergedVector;
    size_t i = 0, j = 0;

    while (i < vec1.size() && j < vec2.size()) {
        if (vec1[i] < vec2[j]) {
            mergedVector.push_back(vec1[i]);
            i++;
        } else {
            mergedVector.push_back(vec2[j]);
            j++;
        }
    }

    // Append remaining elements of vec1, if any
    while (i < vec1.size()) {
        mergedVector.push_back(vec1[i]);
        i++;
    }

    // Append remaining elements of vec2, if any
    while (j < vec2.size()) {
        mergedVector.push_back(vec2[j]);
        j++;
    }

    return mergedVector;
}

int main() {
    std::vector<int> vec1 = {1, 3, 5, 7};
    std::vector<int> vec2 = {2, 4, 6, 8};

    std::vector<int> mergedVector = mergeSortedVectors(vec1, vec2);

    std::cout << "Merged Vector: ";
    for (int num : mergedVector) {
        std::cout << num << " ";
    }
    
    return 0;
}