Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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

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.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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.

>Solution :

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;
}
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading