# 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.

- Remove elements from the front of the Deque that are out of the current window (
- 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.

- Remove elements from the front of the deque that are out of the current window (
- 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.

- Remove elements from the front of the deque that are out of the current window (
- 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.