Where do I really use a Deque Data Structure??

Src: https://springframework.guru/using-deque-in-java/

We often come across queues and their variants:

• Standard Queue — First-Come-First-Serve. Straightforward. Ideal for BFS, job scheduling, etc.
• Priority Queue — Like a regular queue, but prioritizes elements based on some cost/value/weight. Perfect for Dijkstra’s, Top K elements, Running Median, etc.

These are intuitive. But then there’s this lesser-used yet highly powerful structure: the Deque (Double-Ended Queue).

A deque allows:

• Insertion from both ends
• Deletion from both ends
• All in O(1) time

It’s extremely versatile, but its utility shines in problems that require maintaining a range of values dynamically, such as in sliding window problems.

I haven’t found it being used in a lot of problems until I stumbled over one today! And… today I realised that this is a powerful one! Let’s see how https://leetcode.com/problems/sliding-window-maximum/ can be a piece of cake after using deque

Problem Statement: You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Approach:

Here we need to keep some kind of data structure where we can store the most fresh (in range of k) maximum, but we can’t keep only one fresh value, because when it goes out of range of k, wee’ll have to reiterate. For example: [1 3 -1] here we can store 3 right? Then for next window [3 -1 -3] 3 still remains fresh max, now we strip off 3 as it is out of window and we don’t have any max element! :( So clearly 1 value is not sufficient, here we need some kind of data structure where, on top we have fresh maximum, but also other values that can be potential maximums

1. Some thing which remove elements only when they are out of range or in range but smaller.

2. Then we add our current element also

3. But at the time of removal have the best element on top only so that we get max element in O(1)

So you might have guessed we can add elements on back but remove from front, all of this with ….

YESSS: Deque

Now that you’ve understood the approach, coding it is just 4 lines, just translate thee above explaanation into code and you are done!

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int>resWindow(nums.size()-k+1);
        deque<pair<int,int>>dq; 
        int j = 0;
        for(int i = 0; i < nums.size(); ++i) {

            // STEP 1: cleanup all out of window elements
            while(dq.size() && dq.front().first <= i-k) dq.pop_front();

            // STEP 2: Remove all elements which are lesser than current element
            while(dq.size() && dq.back().second < nums[i]) dq.pop_back();

            // STEP 3: push the current element
            dq.push_back({i, nums[i]}); 

            // STEP 4: if you have a window, set the window's maximum element to the front element of deque
            if(i>=k-1) {
                resWindow[j] = dq.front().second;
                j++;
            }
        } 
        return resWindow;
    }
};

That’s how knowing deque’s properties can help you solve a LC hard in 4 steps!

A pro tip: we use Deque in problems where we need something like a smart queue in a store:

• If the person at the front has an expired ticket (out of range), they’re kicked out
• If someone new enters who is taller than everyone behind, those behind are asked to leave
• This ensures the tallest valid person is always at the front — and that’s your max

Happy Coding ❤️