[LeetCode / C++] 215. Kth Largest Element in an Array

1. Question

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

2. Thoughts

3. Tips learned

3.1 Copy Chunks

In C++, you can copy a chunk of elements from one part of a vector to another using std::copy(), which is part of the <algorithm> library. This allows you to copy a range of elements from one place to another in an efficient manner without doing it one-by-one manually.

Example: Copying Elements from Index 1-10 to Index 20-30

Here’s how you can achieve this using std::copy():

#include <iostream>
#include <vector>
#include <algorithm>  // For std::copy

int main() {
    // Create a vector with some example values
    std::vector<int> vec(40);
    
    // Fill the vector with values 1-40
    for (int i = 0; i < 40; ++i) {
        vec[i] = i + 1;
    }

    // Check if the destination range is large enough before copying
    if (vec.size() >= 30 && vec.size() >= 10) {
        // Use std::copy to copy elements from index 1-10 to 20-30
        std::copy(vec.begin() + 1, vec.begin() + 11, vec.begin() + 20);
    }

    // Print the vector to see the result
    for (int num : vec) {
        std::cout << num << " ";
    }

    return 0;
}

Explanation:

• std::copy(first, last, destination):
  • first: The starting iterator (inclusive).
  • last: The ending iterator (exclusive).
  • destination: The starting iterator where the elements will be copied to.

In the above example:

• We copy elements from index 1 (inclusive) to index 11 (exclusive), meaning we are copying the elements from index 1 to 10.
• The copied elements are placed starting at index 20 in the same vector.

Important Considerations:

• Ensure that the destination range (e.g., index 20-30) has enough space to accommodate the copied elements, as std::copy() does not handle out-of-bound accesses.
• If you need to copy elements from an overlapping region, use std::copy_backward() instead of std::copy(), as it handles overlapping ranges correctly.

Using std::copy_backward() (for overlapping ranges):

#include <iostream>
#include <vector>
#include <algorithm>  // For std::copy_backward

int main() {
    std::vector<int> vec(40);

    // Fill the vector with values 1-40
    for (int i = 0; i < 40; ++i) {
        vec[i] = i + 1;
    }

    // Copy elements from index 1-10 to 5-14 using copy_backward for overlapping regions
    std::copy_backward(vec.begin() + 1, vec.begin() + 11, vec.begin() + 15);

    // Print the result
    for (int num : vec) {
        std::cout << num << " ";
    }

    return 0;
}

In this case, std::copy_backward() is useful when source and destination ranges overlap, ensuring that the copy happens correctly from back to front.

3.2 Make new vector from subset of vector

In C++, you can create a new std::vector from a subset or part of another vector by using iterators. You can specify the start and end positions (using iterators) of the original vector to initialize a new vector.

Example: Creating a New Vector from Part of Another Vector

Here’s how you can create a new vector with elements from index 1 to 10 of an existing vector:

#include <iostream>
#include <vector>

int main() {
    // Original vector with some example values
    std::vector<int> original = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

    // Creating a new vector with a part of the original vector (from index 1 to 10)
    std::vector<int> newVector(original.begin() + 1, original.begin() + 11);

    // Print the new vector
    for (int num : newVector) {
        std::cout << num << " ";  // Output: 1 2 3 4 5 6 7 8 9 10
    }

    return 0;
}

Explanation:

• std::vector<int> newVector(original.begin() + 1, original.begin() + 11);
  • The constructor of std::vector allows initialization with a range of iterators.
  • original.begin() + 1: The starting iterator (inclusive, pointing to index 1).
  • original.begin() + 11: The ending iterator (exclusive, pointing to index 11 but stopping just before index 11, meaning it copies elements from index 1 to 10).

Key Points:

1. Iterators: We use original.begin() to get an iterator to the beginning of the vector. Adding an offset (+1, +11, etc.) helps us specify the range.
2. Range-based Initialization: The vector constructor allows you to initialize a vector from a range defined by two iterators, so you can easily extract a part of the vector.
3. Efficient Copying: This is more efficient than copying elements one by one in a loop.

Error Prevention:

Make sure that the range you are selecting (i.e., the start and end positions) is valid; otherwise, you will get out-of-bounds errors. Ensure that the begin() + n values do not exceed the vector’s size.

4. My solution

class Solution
{
public:
    void rotate(vector<int> &nums, int k)
    {
        k %= nums.size();
        vector<int> temp(nums.end() - k, nums.end());
        copy(nums.begin(), nums.end() - k, nums.begin() + k);
        copy(temp.begin(), temp.end(), nums.begin());
    }
};

38/38 cases passed (21 ms)
Your runtime beats 53.26 % of cpp submissions
Your memory usage beats 33.94 % of cpp submissions (28 MB)

5. AI Solution and Improvements

Your solution is efficient and clean! You're already utilizing std::vector, std::copy(), and taking advantage of slicing the vector by using iterators. There are, however, some ways to further optimize or simplify it in a more C++ style. Let’s discuss improvements and an alternative, optimal approach.

Key Improvements:

1. Avoiding Temporary Vector: Although your solution is efficient, it uses extra space (a temporary vector). There's a way to rotate the array in-place without needing additional space.
2. Using Reverse Algorithm: One of the most optimal approaches to rotating an array is to reverse parts of the array in-place. This can be done in O(n) time complexity with O(1) additional space.

Optimized In-Place Solution Using Reverse:

The idea behind the reverse-based approach is:
1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining elements.

This approach avoids the need for an additional temporary vector and runs in O(n) time with O(1) space.

Here’s the improved version:

#include <vector>
#include <algorithm>  // For std::reverse

class Solution
{
public:
    void rotate(std::vector<int> &nums, int k)
    {
        int n = nums.size();
        k %= n; // Handle cases where k is larger than the size of the array

        // Step 1: Reverse the entire array
        std::reverse(nums.begin(), nums.end());

        // Step 2: Reverse the first k elements
        std::reverse(nums.begin(), nums.begin() + k);

        // Step 3: Reverse the remaining elements
        std::reverse(nums.begin() + k, nums.end());
    }
};

Explanation:

1. Reverse the entire array: This places the last k elements at the start.
2. Reverse the first k elements: This brings the first k elements back into their correct order.
3. Reverse the remaining elements: This restores the remaining part of the array to its correct order.

Example Walkthrough:

For nums = [1,2,3,4,5,6,7] and k = 3:
1. After reversing the entire array: [7,6,5,4,3,2,1]
2. After reversing the first 3 elements: [5,6,7,4,3,2,1]
3. After reversing the rest: [5,6,7,1,2,3,4]

Advantages:

• Time complexity: O(n), where n is the size of the array.
• Space complexity: O(1), since it modifies the array in-place without needing extra space.

This approach is more efficient in terms of memory usage and follows an idiomatic C++ style by leveraging std::reverse from the STL for clean and simple operations.

Let me know if you need further clarification or adjustments!