Search code examples
c++stl

std::rotate for a right rotation gives me a heapoverflow

I'm trying to solve this leetcode question where i'm supposed to perform a right rotation on a vector by k positions. Since std::rotate does a left rotation I tried using reverse iterators to accomplish the opposite result:

    void rotate(vector<int>& nums, int k) 
    {
        std::rotate(nums.rbegin(), nums.rbegin() + k, nums.rend());
    }

Now this works for the first 2 test cases, but when I submit it, I get a runtime error saying i've got a heapoverflow, here's the error:

=21==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000034c at pc 0x000000369815 bp 0x7fff32cde700 sp 0x7fff32cde6f8
READ of size 4 at 0x60200000034c thread T0
    #3 0x7f55da0cc082  (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
0x60200000034c is located 4 bytes to the left of 4-byte region [0x602000000350,0x602000000354)

What gives? Is there a problem with my code? From what i've tested it seems fine. If this is a problem with the leetcode platform itself, i'll delete this question.

Solution

  • Your code will fail if the number of positions to rotate exceeds the size of the vector.

    std::rotate(nums.rbegin(), nums.rbegin() + k, nums.rend());

    If k >= nums.size(), then nums.rbegin() + k will be an invalid iterator, thus the runtime error you're seeing.

    The fix is to rotate a modulus of k with the size of the vector, and not actually k places.

    std::rotate(nums.rbegin(), nums.rbegin() + k % nums.size(), nums.rend());

    For example, if nums.size() is 10, and k is 20, 30, 40, the modulus will yield 0, thus no actual rotation is done. On the other hand, if k is 21, 22, etc., then an actual rotation of 1, 2, etc. will be done.