Sliding window using deque (runtime error)

Question

In the following program, I am trying to find the maximum in window size of k in an array of length n. For reference, the question is from LeetCode.

For example, if the array is [2 5 3 1 2] and window size is 3, then I have windows as [2 5 3], [5 3 1], [3 1 2] and corresponding maximums are 5, 5, 3.

I am using std::deque for this purpose but it is giving runtime error, I don't think any pointer invalidations are happening, I cannot find any. Please help me, I am stuck for a long time on this.

Here's my code:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> d;
        for (int i = 0; i < k; ++i) {
            while (!d.empty() && d.front() < nums[i]) {
                d.pop_front();
            }
            d.push_front(nums[i]);
        }
        vector<int> ans;
        ans.push_back(d.back());

        int n = nums.size();
        for (int i = k; i < n; ++i) {
            while (1) {
                int elem = d.back();
                d.pop_back();
                if (elem == nums[i-k]) {
                    break;
                }
            }
            while (!d.empty() && d.front() < nums[i]) {
                d.pop_front();
            }
            d.push_front(nums[i]);
            ans.push_back(d.back());
        }
        return ans;
    }
};

Error message shown is this:

Line 157: Char 16: runtime error: reference binding to misaligned address 0xbebebebebebec0ba for type 'int', which requires 4 byte alignment (stl_deque.h)
0xbebebebebebec0ba: note: pointer points here
<memory cannot be printed>
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_deque.h:162:16

Answer 1

Observe this part of your code:

while (1) {
    int elem = d.back();         // get element
    d.pop_back();                // pop element

    if (elem == nums[i-k]) {     // compare element
        break;                   // and break on success
    }                            // What happens on failure???
}                                // Inifinite loop and UB!

The while loop is not exiting.

With its every iteration, you're accessing and popping an element from deque until it is empty because elem is not equal to nums[i-k].

Change while (1) to:

while ( !d.empty() )

Because you can get and pop an element from the deque only when it's not empty!

And, calling back() and pop_back() on an empty deque is Undefined Behavior:

From the documentation of std::deque::back():

Calling back on an empty container causes undefined behavior.

Same goes for std::deque::pop_back():

Calling pop_back on an empty container is undefined.