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.

Answer 1

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;
}