runtime error: addition of unsigned offset to 0x603000000040 overflowed to 0x603000000034 (stl_vector.h)

Question

I was solving the Sliding Window Maximum problem but I'm receiving the following error on Leetcode but it's working on my local compiler [VSCode]

Line 1034: Char 34: runtime error: addition of unsigned offset to 0x603000000040 overflowed to 0x603000000034 (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34

Here's the code:

#include <deque>

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& A, int k) {
        
        int _max = INT_MIN;
        vector<int> ans;
        for (int i = 0; i < k; ++i)
        {
            _max = max(_max, A[i]);
        }
        if (k == A.size()){
            return {_max};
        }
        
        ans.push_back(_max);
        deque<int> dq;
        dq.push_back(_max);

        for (int i = k; i < A.size(); ++i)
        {
            if (dq.empty())
            {
                dq.push_back(i);
                _max = A[i];
            }
            else
            {
                while (!dq.empty() && A[dq.front()] < A[i])
                {
                    dq.pop_front();
                }
                if (dq.empty())
                {
                    _max = A[i];
                }
                else
                {
                    _max = max(_max, A[i]);
                }
                dq.push_front(A[i]);
                ans.push_back(_max);
            }
        }

        return ans;
    }
};

Answer 1

Looks like problem is here: A[dq.front()] < A[i];

As I see during runtime dq.front() takes the value of -3 which is not fine, due it is negative index. Actual crash is here A[dq.front()]. So there is a programming error in your code.

Also looks like you make the push of wrong index here: dq.push_front(A[i]), which means that input does have negative values, which you didn't expect.

And probably you wanted to write dq.push_front(i) instead of dq.push_front(A[i]).

Fixed program looks like this for you:

#include <deque>

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& A, int k) {
        
        int _max = INT_MIN;
        vector<int> ans;
        for (int i = 0; i < k; ++i)
        {
            _max = max(_max, A[i]);
        }
        if (k == A.size()){
            return {_max};
        }
        
        ans.push_back(_max);
        deque<int> dq;
        dq.push_back(_max);

        for (int i = k; i < A.size(); ++i)
        {
            if (dq.empty())
            {
                dq.push_back(i);
                _max = A[i];
            }
            else
            {
                while (!dq.empty() && A[dq.front()] < A[i])
                {
                    dq.pop_front();
                }
                if (dq.empty())
                {
                    _max = A[i];
                }
                else
                {
                    _max = max(_max, A[i]);
                }
                dq.push_front(i);
                ans.push_back(_max);
            }
        }

        return ans;
    }
};