Advanced Vector Manipulation Techniques in C++

Welcome to another pivotal lesson in your C++ interview preparation. In this lesson, we will concentrate on Advanced Vector Manipulation Techniques, focusing on the representation and manipulation of vectors directly, without relying on built-in functions. This topic is indispensable when preparing for technical interviews, as many problems often involve performing various operations on vectors.

Before diving into this lesson's example, let's quickly review In-Place Modification. In-place modification refers to changing the data structure (e.g., a vector) directly, without using extra space for another copy of the data structure. By modifying the original vector directly, we save on memory and may improve performance. This is often achieved by altering the elements within the vector itself rather than creating a new vector to hold the transformed elements.

Let's look at a common coding interview question. You are given a vector nums, and a number k. The task requires "rotating" the vector by k positions. Rotating a vector by k positions means that each element is shifted to the right by k positions, and elements that move past the end wrap around to the beginning. For example, rotating the vector [1, 2, 3, 4, 5, 6, 7] to the right by 3 positions results in [5, 6, 7, 1, 2, 3, 4]. Elements that move past the end of the vector wrap around to the beginning.

One approach is creating an empty vector and copying the elements of the original vector, calculating shifts to create a new rotated vector. However, in this challenge, we must rotate the vector in-place. We cannot create a new vector to aid in our algorithm.

Here, we'll use a four-step approach involving vector reversal to achieve this in-place and efficiently.

1. Adjust k to be within bounds: Calculate k = k % n to ensure k lies within the range [0, n-1]. Here, n is the size of the vector. This step handles cases where k is larger than n, effectively reducing unnecessary full rotations.

2. Reverse the entire vector: Reversing the entire vector will place the last k elements (which need to be moved to the front) in the first k positions, but in reverse order.

3. Reverse the first k elements: Reversing just these first k elements restores their original order.

4. Reverse the remaining elements: Finally, reversing the elements from position k to the end restores the order of the remaining elements.

Let's look at an example:

Given an initial vector nums=[1, 2, 3, 4, 5, 6, 7] and k = 3:

• Reverse the entire vector: nums = [7, 6, 5, 4, 3, 2, 1]
• Reverse the first 3 elements: nums = [5, 6, 7, 4, 3, 2, 1]
• Reverse the rest of the vector: nums = [5, 6, 7, 1, 2, 3, 4]

The nums vector has been successfully rotated to the right by 3.

Our solution will use the std::reverse function from the C++ Standard Library to achieve the reversals efficiently.

#include <iostream>
#include <vector>
#include <algorithm> // Include for std::reverse

void rotateVector(std::vector<int>& nums, int k) {
    int n = nums.size();
    k = k % n; // Ensure k is within the bounds of the vector length

    // Reverse the entire vector
    std::reverse(nums.begin(), nums.end());
    // Reverse the first k elements
    std::reverse(nums.begin(), nums.begin() + k);
    // Reverse the rest of the vector
    std::reverse(nums.begin() + k, nums.end());
}

// Example
int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    int k = 3;

    rotateVector(nums, k);

    for(int num : nums) {
        std::cout << num << " ";
    }
    // Output: 5 6 7 1 2 3 4

    return 0;
}