runtime error: addition of unsigned offset to 0x6030000000d0 overflowed to 0x6030000000cc (stl_vector.h)

Question

Problem Name: Peak Index in Mountain Array

The problem requires finding the index of the peak element in a mountain array. The peak element is defined as an element that is greater than its neighbors. The array is guaranteed to have a mountain pattern.

Such that: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] & arr[i] > arr[i + 1] > ... > arr[arr.length - 1] where i is the needed index.

Here's a simplified version of my code:

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size() - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                return mid;
            } else if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }  
};

I tried some test cases on it, few are working fine, but when I use the input {3, 5, 3, 2, 0}, the code triggers the runtime error. runtime error: addition of unsigned offset to 0x6030000000d0 overflowed to 0x6030000000cc (stl_vector.h)

I am able to run it on my own compiler, but getting this error on Leetcode after submiting the code.

The code seem to be some kind of binary search. If you have studied standard algorithms you should have known that binary search *requires* the input to be ordered (sorted). — Some programmer dude, Aug 20 '23 at 11:07
@Someprogrammerdude Yes, the input is needed to be sorted. But the input does have a pattern `arr[0] < arr[1] < ... < arr[i - 1] < arr[i] ` & `arr[i] > arr[i + 1] > ... > arr[arr.length - 1]` where `i` is the needed index. I searched a bit about this and Binary Search is used to solve this problem. It's just that my implementation might need some debugging. — Nikhil Kumar, Aug 20 '23 at 11:14
`arr[mid + 1]` is going to peek at `arr[arr.size()]` which is out of bounds — Ted Lyngmo, Aug 20 '23 at 11:21
Create a proper [mre], with the input hard-coded into the `main` function. Then you can easily debug it locally om your own system. Use tools such as compiler sanitizers or memory debuggers like Valgrind. Or simply change all vector access using `[]` to use the `at` function, which will throw an exception when you go out of bounds. — Some programmer dude, Aug 20 '23 at 11:21
Have you tried to compile your code locally and test it with a debugger attached? Being able to debug your own code is a required skill and not something leetcode will teach you (in fact leetcode will probably teach you a lot of bad C++ habits instead) — Pepijn Kramer, Aug 20 '23 at 11:27
Much better sources to learn c++ from are : A [recent C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) or have a go at https://www.learncpp.com/ (that's pretty decent, and pretty up-to-date). For C++ reference material use : [cppreference](https://en.cppreference.com/w/). And after you learned the C++ basics from those sources, look at the [C++ coreguidelines](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines) regularely to keep up-to-date with the latest guidelines. — Pepijn Kramer, Aug 20 '23 at 11:28

score 1 · Accepted Answer · answered Aug 20 '23 at 11:41

You never check if mid is 0 before accessing arr[mid-1] and you never check if mid is arr.size() - 1 before accessing arr[mid+1]. Both these failures will lead to accesses out of bounds.

Adding checks before accesses should make it work according to the intended design.

int peakIndexInMountainArray(const std::vector<int>& arr) {
    int left = 0, right = arr.size();
    int mid;
    while (left < right) {
        mid = (left + right) / 2;

        bool low = (mid == 0) || (arr[mid] > arr[mid - 1]);
//                 ^^^^^^^^^^
        bool high = (mid == (arr.size() - 1)) || (arr[mid] > arr[mid + 1]);
//                  ^^^^^^^^^^^^^^^^^^^^^^^^^
        if (low && high) {
            return mid;
        } else if (low) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return -1;
}

runtime error: addition of unsigned offset to 0x6030000000d0 overflowed to 0x6030000000cc (stl_vector.h)

1 Answers1