Double Ended Queue

 

Double Ended Queue (Deque): A Double Ended Queue, also known as Deque, is a data structure that allows insertion and deletion of elements from both ends. It combines the features of a stack and a queue, providing efficient insertion and removal operations at both ends of the queue.

Implementation: We can implement a Deque using a linked list. Each node in the linked list represents an element in the Deque and contains a value and references to the previous and next nodes. We maintain references to the front and rear nodes of the Deque to facilitate efficient operations.

Here's an example of implementing a Deque using a linked list in Python:

# Node class to represent a node in the Deque
class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

# Deque class
class Deque:
    def __init__(self):
        self.front = None
        self.rear = None

    def is_empty(self):
        return self.front is None

    def add_front(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.front = self.rear = new_node
        else:
            new_node.next = self.front
            self.front.prev = new_node
            self.front = new_node

    def add_rear(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.front = self.rear = new_node
        else:
            new_node.prev = self.rear
            self.rear.next = new_node
            self.rear = new_node

    def remove_front(self):
        if self.is_empty():
            return None
        value = self.front.value
        if self.front == self.rear:
            self.front = self.rear = None
        else:
            self.front = self.front.next
            self.front.prev = None
        return value

    def remove_rear(self):
        if self.is_empty():
            return None
        value = self.rear.value
        if self.front == self.rear:
            self.front = self.rear = None
        else:
            self.rear = self.rear.prev
            self.rear.next = None
        return value

    def get_front(self):
        return self.front.value if self.front else None

    def get_rear(self):
        return self.rear.value if self.rear else None

 

Explanation:

• The Node class represents a node in the Deque. It has attributes for storing the value and references to the previous and next nodes.
• The Deque class implements the Deque data structure using a linked list. It has methods for checking if the Deque is empty, adding elements at the front and rear, removing elements from the front and rear, and getting the front and rear elements.
• The is_empty method checks if the Deque is empty by checking if the front attribute is None.
• The add_front method adds an element at the front of the Deque. If the Deque is empty, the new element becomes both the front and rear. Otherwise, the new node is inserted before the current front node.
• The add_rear method adds an element at the rear of the Deque. If the Deque is empty, the new element becomes both the front and rear. Otherwise, the new node is inserted after the current rear node.
• The remove_front method removes and returns the element from the front of the Deque. If the Deque is empty, it returns None. If the Deque has only one element, both the front and rear become None. Otherwise, the front is updated to the next node, and the previous reference of the new front node is set to None.
• The remove_rear method removes and returns the element from the rear of the Deque. If the Deque is empty, it returns None. If the Deque has only one element, both the front and rear become None. Otherwise, the rear is updated to the previous node, and the next reference of the new rear node is set to None.
• The get_front and get_rear methods return the value of the front and rear elements, respectively. If the Deque is empty, they return None.

Now, let's solve a question from LeetCode using the Deque concept.

Problem: Sliding Window Maximum (LeetCode #239) Description: Given an array of integers nums and an integer k, return the maximum sliding window of size k. Example:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Maximum
---------------               -------
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

def maxSlidingWindow(nums, k):
    if not nums or k == 0:
        return []
    n = len(nums)
    result = []
    deque = Deque()  # Creating an instance of the Deque class
    for i in range(n):
        # Remove elements that are out of the current window from the front of the Deque
        if not deque.is_empty() and deque.get_front() < i - k + 1:
            deque.remove_front()
        # Remove elements that are smaller than the current element from the rear of the Deque
        while not deque.is_empty() and nums[deque.get_rear()] < nums[i]:
            deque.remove_rear()
        # Add the current element index to the rear of the Deque
        deque.add_rear(i)
        # If the window has reached the size k, add the maximum element to the result
        if i >= k - 1:
            result.append(nums[deque.get_front()])
    return result

Explanation:

• The maxSlidingWindow function takes an array of integers nums and an integer k as input and returns the maximum sliding window of size k.
• We initialize an empty list result to store the maximum elements.
• We create an instance of the Deque class to store the indices of the elements in the current window.
• We iterate over the elements of nums using the variable i.
• At each iteration, we perform the following steps:
  • Remove elements from the front of the Deque that are out of the current window (i - k + 1).
  • Remove elements from the rear of the Deque that are smaller than the current element nums[i].
  • Add the current element index i to the rear of the Deque.
  • If the window has reached the size k, add the maximum element (the element at the front of the Deque) to the result list.
• Finally, we return the result list.

Time Complexity: The time complexity of this solution is O(n), where n is the number of elements in the input array nums. We iterate over each element once and perform constant-time operations for each element.

Space Complexity: The space complexity is O(k), where k is the size of the sliding window. We store the indices of at most k elements in the Deque.

Overall, this approach provides an efficient solution for finding the maximum sliding window using a Double Ended Queue (Deque).

Sliding Window Minimum 

Description: Given an array of integers nums and an integer k, return the minimum sliding window of size k. Example:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [-1,-3,-3,-3,3,3]
Explanation:
Window position                Minimum
---------------               -------
[1  3  -1] -3  5  3  6  7       -1
 1 [3  -1  -3] 5  3  6  7       -3
 1  3 [-1  -3  5] 3  6  7       -3
 1  3  -1 [-3  5  3] 6  7       -3
 1  3  -1  -3 [5  3  6] 7        3
 1  3  -1  -3  5 [3  6  7]       3

Solution :

from collections import deque

def minSlidingWindow(nums, k):
    n = len(nums)
    result = []
    dq = deque()

    for i in range(n):
        # Remove elements that are out of the current window from the front of the deque
        if dq and dq[0] <= i - k:
            dq.popleft()

        # Remove elements that are larger than the current element from the rear of the deque
        while dq and nums[dq[-1]] >= nums[i]:
            dq.pop()

        dq.append(i)

        # If the window has reached the size k, add the minimum element to the result
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Explanation:

• We define a function minSlidingWindow that takes an array of integers nums and an integer k as input and returns the minimum sliding window of size k.
• We initialize an empty list result to store the minimum elements.
• We create a deque dq to store the indices of the elements in the current window.
• We iterate over the elements of nums using the variable i.
• At each iteration, we perform the following steps:
  • Remove elements from the front of the deque that are out of the current window (i - k).
  • Remove elements from the rear of the deque that are larger than the current element nums[i].
  • Add the current element index i to the rear of the deque.
  • If the window has reached the size k, add the minimum element (the element at the front of the deque) to the result list.
• Finally, we return the result list.

Time Complexity: The time complexity of this solution is O(n), where n is the number of elements in the input array nums. We iterate over each element once and perform constant-time operations for each element.

Space Complexity: The space complexity is O(k), where k is the size of the sliding window. We store the indices of at most k elements in the deque.

Overall, this approach provides an efficient solution for finding the minimum sliding window using a deque.

One without using deque library.

Here's the modified version of the code that solves the problem of finding the minimum sliding window without using the deque library. We'll provide an explanation of the code and analyze its time and space complexity.

def minSlidingWindow(nums, k):
    n = len(nums)
    result = []
    dq = []

    for i in range(n):
        # Remove elements that are out of the current window from the front of the deque
        if dq and dq[0] <= i - k:
            dq.pop(0)

        # Remove elements that are larger than the current element from the rear of the deque
        while dq and nums[dq[-1]] >= nums[i]:
            dq.pop()

        dq.append(i)

        # If the window has reached the size k, add the minimum element to the result
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

def minSlidingWindow(nums, k):
    n = len(nums)
    result = []
    dq = []

    for i in range(n):
        # Remove elements that are out of the current window from the front of the deque
        if dq and dq[0] <= i - k:
            dq.pop(0)

        # Remove elements that are larger than the current element from the rear of the deque
        while dq and nums[dq[-1]] >= nums[i]:
            dq.pop()

        dq.append(i)

        # If the window has reached the size k, add the minimum element to the result
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result


# Test the code
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(minSlidingWindow(nums, k))

In this code, we define the minSlidingWindow function that takes an array nums and an integer k as input. The function returns a list containing the minimum elements in each sliding window of size k.

We initialize an empty list result to store the minimum elements, and a list dq to act as a deque. We iterate over the elements of nums using the variable i.

At each iteration, we perform the following steps:

• We remove elements from the front of the deque that are out of the current window (i - k).
• We remove elements from the rear of the deque that are larger than the current element nums[i].
• We add the current element index i to the rear of the deque.
• If the window has reached the size k, we add the minimum element (the element at the front of the deque) to the result list.

Finally, we call the minSlidingWindow function with a sample input array nums and window size k and print the result.

The expected output for the sample input [1, 3, -1, -3, 5, 3, 6, 7] with a window size of 3 is [-1, -3, -3, -3, 3, 3].

The time and space complexity for this code are the same as explained in the previous answer.

Explanation:

• The approach is similar to the previous solution, but instead of using the deque library, we use a list dq to mimic a deque.
• We initialize an empty list result to store the minimum elements.
• We create an empty list dq to act as a deque to store the indices of the elements in the current window.
• We iterate over the elements of nums using the variable i.
• At each iteration, we perform the following steps:
  • Remove elements from the front of the deque that are out of the current window (i - k).
  • Remove elements from the rear of the deque that are larger than the current element nums[i].
  • Add the current element index i to the rear of the deque.
  • If the window has reached the size k, add the minimum element (the element at the front of the deque) to the result list.
• Finally, we return the result list.

Time Complexity: The time complexity of this solution is O(n), where n is the number of elements in the input array nums. We iterate over each element once and perform constant-time operations for each element.

Space Complexity: The space complexity is O(k), where k is the size of the sliding window. We store at most k indices in the dq list.

Overall, this approach provides an efficient solution for finding the minimum sliding window without using the deque library.

Here's the code for a custom Deque class that can be used to find the minimum in a sliding window: 

class Deque:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push_back(self, item):
        self.items.append(item)

    def push_front(self, item):
        self.items.insert(0, item)

    def pop_back(self):
        if self.is_empty():
            raise Exception("Deque is empty")
        return self.items.pop()

    def pop_front(self):
        if self.is_empty():
            raise Exception("Deque is empty")
        return self.items.pop(0)

    def back(self):
        if self.is_empty():
            raise Exception("Deque is empty")
        return self.items[-1]

    def front(self):
        if self.is_empty():
            raise Exception("Deque is empty")
        return self.items[0]

    def size(self):
        return len(self.items)


def minSlidingWindow(nums, k):
    n = len(nums)
    result = []
    dq = Deque()

    for i in range(n):
        # Remove elements that are out of the current window from the front of the deque
        if not dq.is_empty() and dq.front() <= i - k:
            dq.pop_front()

        # Remove elements that are larger than the current element from the rear of the deque
        while not dq.is_empty() and nums[dq.back()] >= nums[i]:
            dq.pop_back()

        dq.push_back(i)

        # If the window has reached the size k, add the minimum element to the result
        if i >= k - 1:
            result.append(nums[dq.front()])

    return result


# Test the code
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(minSlidingWindow(nums, k))

In this code, we define a Deque class with methods to perform operations such as push_back, push_front, pop_back, pop_front, back, front, and size. The class is implemented using a list.

The minSlidingWindow function is similar to the previous implementation. However, instead of using a list as a deque, we create an instance of the Deque class and use its methods to perform deque operations.

The expected output for the sample input [1, 3, -1, -3, 5, 3, 6, 7] with a window size of 3 is [-1, -3, -3, -3, 3, 3].

The time and space complexity for this code are the same as explained in the previous answer.