Queue and Deque Data Structure

Queue and Deque Data Structure | Let’s first see the Queue data structure, and then we will discuss the Deque data structure. Deque stands for double-ended queue.

Table of Contents

• Queue Implementation using Array
• LinkedList Implementation of Queue
• Queue in Java
• Implement Stack using Queue
• Reverse the Queue
• 1. Generate Numbers with Given Digits
• Deque Data Structure
• Array Implementation of Deque
• Deque in Java
• ArrayDeque in Java
• 2. Design a Data Structure with Min and Max Operations
• 3. Maximum of all Subarrays of Size K
• 4. Minimum of all Subarrays of Size K
• 5. First Circular Tour

---

Queue:- It is also known as FIFO (first in first out). The operations are:-

• enqueue(x): Insert element at rear.
• dequeue(): Remove the element at the front.
• getFront()
• getRear()
• size()
• isEmpty()

Applications of Queue

• Single Resource and Multiple Consumer.
• Synchronization between slow and fast devices.
• In Operating Systems (Semaphore, FCFS Scheduling, Spooling, buffers for devices like Keyboard).
• In Computer Networks (Router/Switches and Mail Queues).
• Variations: Deque, Priority Queue, Doubly Ended Priority Queue.

Queue Implementation using Array

Implement the following operations:- enqueue(), dequeue(), size(), getFront(), getRear(), isFull(), isEmpty().

public class Queue {
    int size, cap;
    int[] arr;

    public Queue(int c) {
        cap = c;
        size = 0;
        arr = new int[c];
    }

    boolean isFull() {
        return size == cap;
    }

    boolean isEmpty() {
        return size == 0;
    }

    void enqueue(int x) {
        if (isFull()) {
            return;
        }
        arr[size] = x;
        size++;
    }

    // O(n)
    void dequeue() {
        if (isEmpty()) {
            return;
        }
        for (int i = 0; i < size - 1; i++) {
            arr[i] = arr[i + 1];
        }
        size--;
    }

    int getFront() {
        return isEmpty() ? -1 : arr[0];
    }

    int getRear() {
        return isEmpty() ? -1 : arr[size - 1];
    }

    int size() {
        return size;
    }
}

The dequeue operations take O(n) time. For an efficient solution where dequeue also takes O(1) time we can use a Circular array. With this implementation, all the operations have O(1) time complexity.

public class Queue {
    int front, size, cap;
    int[] arr;

    public Queue(int c) {
        cap = c;
        size = 0;
        front = 0;
        arr = new int[c];
    }

    boolean isFull() {
        return size == cap;
    }

    boolean isEmpty() {
        return size == 0;
    }

    void enqueue(int x) {
        if (isFull()) {
            return;
        }
        int rear = (front + size - 1) % cap;
        rear = (rear + 1) % cap;
        arr[rear] = x;
        size++;
    }

    void dequeue() {
        if (isEmpty()) {
            return;
        }
        front = (front + 1) % cap;
        size--;
    }

    int getFront() {
        return isEmpty() ? -1 : arr[front];
    }

    int getRear() {
        return isEmpty() ? -1 : arr[(front + size - 1) % cap];
    }

    int size() {
        return size;
    }
}

LinkedList Implementation of Queue

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
    }
}

public class Queue {
    int size;
    Node front, rear;

    public Queue() {
        front = rear = null;
        size = 0;
    }

    boolean isEmpty() {
        return size == 0;
    }

    void enqueue(int x) {
        Node temp = new Node(x);
        if (front == null) {
            front = rear = temp;
        } else {
            rear.next = temp;
            rear = temp;
        }
        size++;
    }

    void dequeue() {
        if (front == null) {
            return;
        }
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
    }

    int getFront() {
        return isEmpty() ? -1 : front.data;
    }

    int getRear() {
        return isEmpty() ? -1 : rear.data;
    }

    int size() {
        return size;
    }

    public static void main(String[] args) {
        Queue q = new Queue();
        q.enqueue(10);
        q.enqueue(20);
        q.enqueue(30);

        System.out.println("Front element: " + q.getFront()); // Output: 10
        System.out.println("Rear element: " + q.getRear());   // Output: 30
        System.out.println("Queue size: " + q.size());        // Output: 3

        q.dequeue();
        System.out.println("Front element after dequeue: " + q.getFront()); 
        // Output: 20
    }
}

Queue in Java

In Java, the Queue interface includes several essential operations, though the exact method names differ slightly. Here’s how the operations we listed correspond to the methods provided by the Queue interface:-

• enqueue(x): Insert element at rear. In Java, this is done using add(x) or offer(x).
• dequeue(): Remove element at the front. This is achieved using remove() or poll().
• getFront(): Retrieve the front element. We can use peek() or element().
• getRear(): Retrieve the rear element. Java’s Queue interface does not have a direct method to retrieve the rear element. Typically, you would have to use a Deque (double-ended queue) to efficiently access the rear element with peekLast().

It also contains size() and isEmpty() methods.

The following classes mainly implement Queue interface:-

1. LinkedList
2. ArrayDeque (Preferred)

import java.util.LinkedList;
import java.util.Queue;

public class Test {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        // Queue<Integer> queue = new ArrayDeque<>();

        // enqueue
        queue.offer(10);
        queue.offer(20);

        // dequeue
        System.out.println(queue.poll()); // 10

        // getFront()
        System.out.println(queue.peek()); // 20

        System.out.println(queue.size()); // 1
        System.out.println(queue.isEmpty()); // false
    }
}

Operation	Methods that Do not Throw Exceptions	Methods that Throw Exceptions
Retrieve Element	peek()	element()
Add Element	offer()	add()
Remove Element	poll()	remove()

All these operations have O(1) time complexity whether we use the LinkedList class or the ArrayDeque class.

Implement Stack using Queue

Consider a situation where we have a library available for Queue and we need a Stack library. How to implement the Stack?

The idea is to use two queues to simulate the behavior of a stack, where the push and pop operations are the main focus.

Push Operation: The push method adds an element to q2, then transfers all elements from q1 to q2, effectively reversing the order. After that, q1 and q2 are swapped, making q1 the main queue holding the stack’s elements.

import java.util.Queue;
import java.util.LinkedList;

public class Stack {
    Queue<Integer> q1, q2;

    public Stack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public int top() {
        return q1.peek();
    }

    public int size() {
        return q1.size();
    }

    public boolean isEmpty() {
        return q1.isEmpty();
    }

    public void push(int x) {
        q2.add(x);
        // Transfer all elements from q1 to q2
        while (!q1.isEmpty()) {
            q2.add(q1.poll());
        }
        // Swap q1 and q2
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

    public void pop() {
        if (q1.isEmpty()) {
            throw new IllegalStateException("Stack is Empty");
        }
        q1.remove();
    }
}

public class Test {
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("Top element: " + stack.top()); // 30
        System.out.println("Stack size: " + stack.size()); // 3
        stack.pop();
        System.out.println("Top element after pop: " + stack.top()); // 20
    }
}

Reverse the Queue

Given a queue, we need to reverse it.

Iterative Approach:- Use stack. Traverse through the queue, pull elements and put them into the stack. Then pop elements from the stack and store them back to the queue.

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class Test {
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(10);
        queue.add(20);
        queue.add(30);

        reverse(queue);
        System.out.println(queue); // [30, 20, 10]
    }

    private static void reverse(Queue<Integer> queue) {
        Stack<Integer> stack = new Stack<>();
        // store elements to stack
        while (!queue.isEmpty()) {
            stack.push(queue.poll());
        }
        // store elements back to queue
        while (!stack.isEmpty()) {
            queue.add(stack.pop());
        }
    }
}

Recursive Approach

import java.util.ArrayDeque;
import java.util.Queue;

public class Test {
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(10);
        queue.add(20);
        queue.add(30);

        reverse(queue);
        System.out.println(queue); // [30, 20, 10]
    }

    private static void reverse(Queue<Integer> queue) {
        if (queue.isEmpty()) {
            return;
        }
        int temp = queue.poll();
        reverse(queue);
        queue.add(temp);
    }
}

Recursion internally uses Stack to trace the method call. Therefore both approaches are using the stack.

1. Generate Numbers with Given Digits

Given a number N, print the first N numbers (in increasing order) such that all these numbers have digits in set {5, 6}.

N = 10
Output: 5, 6, 55, 56, 65, 66, 555, 556, 565, 566

N = 4
Output: 5, 6, 55, 56

Note: N can be a big number and the result values might not fit in basic data type like long, int, or long long int.

We will use the Queue data structure and will consider numbers as String. We will store 5, and 6 into the queue. Then we will run a loop, and one by one pop a number from the queue, print the number, append 5 and 6 to the number, and enqueue the new numbers back to the Queue.

import java.util.Queue;
import java.util.ArrayDeque;

public class Test {
    public static void main(String[] args) {
        generateNumbers(10);
    }

    private static void generateNumbers(int n) {
        Queue<String> queue = new ArrayDeque<>();
        queue.add("5");
        queue.add("6");
        for (int count = 0; count < n; count++) {
            String curr = queue.poll();
            System.out.println(curr);
            queue.add(curr + "5");
            queue.add(curr + "6");
        }
    }
}

Time complexity: O(n)

Deque Data Structure

Deque stands for doubly-ended queue means we can do insertions and deletions at both the front and rear ends. Operations are:- insertFront(), insertRear(), deleteFront(), deleteRear(). Additional operations are:- getFront(), getRear(), isFull(), isEmpty(), size().

We can implement Deque through one of these data structures:-

1. Doubly Linked List
2. Circular Array

Using these data structures we can perform all operations in O(1).

Why do we use a doubly linked list for Deque implementation but not the singly linked list? If we use singly linked list then for insertion/deletion at the rear/tail end will require traversal throughout the linked list and the operation will have O(n) time complexity.

Why do we use the circular array for Deque implementation but not the simple array? Using a normal array we can’t do insertion and deletion from both ends. Therefore we use a circular array with front and rear indexes.

Applications of Deque Data Structure:-

1. A Deque can be used as both Stack and Queue.
2. Maintaining a history of action.
3. A Steal Process Scheduling Algorithm.
4. Implementing a Priority Queue with two types of priorities.
5. Maximum/minimum of all subarrays of size k in an array.

Array Implementation of Deque

Simple implementation

public class Deque {
    int[] arr;
    int size, cap;

    public Deque(int c) {
        size = 0;
        cap = c;
        arr = new int[c];
    }

    boolean isFull() {
        return size == cap;
    }

    boolean isEmpty() {
        return size == 0;
    }

    void insertRear(int x) {
        if (isFull()) {
            return;
        }
        arr[size++] = x;
    }

    void deleteRear() {
        if (isEmpty()) {
            return;
        }
        size--;
    }

    int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return arr[size - 1];
    }

    void insertFront(int x) {
        if (isFull()) {
            return;
        }
        for (int i = size - 1; i > 0; i--) {
            arr[i + 1] = arr[i];
        }
        arr[0] = x;
        size++;
    }

    void deleteFront() {
        if (isEmpty()) {
            return;
        }
        for (int i = 0; i < size - 1; i++) {
            arr[i] = arr[i + 1];
        }
        size--;
    }

    int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return arr[0];
    }

}

In this simple implementation, insertFront() and deleteFront() operations are O(n) whereas the remaining other operations are O(1). To perform all operations in O(1) we can use a circular array.

Efficient Implementation Using Circular Array

The rear is always (front + size -1) % cap.

public class Deque {
    int[] arr;
    int front, size, cap;

    public Deque(int c) {
        size = front = 0;
        cap = c;
        arr = new int[c];
    }

    boolean isFull() {
        return size == cap;
    }

    boolean isEmpty() {
        return size == 0;
    }

    void insertRear(int x) {
        if (isFull()) {
            return;
        }
        int new_rear = (front + size) % cap;
        arr[new_rear] = x;
        size++;
    }

    void deleteRear() {
        if (isEmpty()) {
            return;
        }
        size--;
    }

    int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return arr[(front + size - 1) % cap];
    }

    void insertFront(int x) {
        if (isFull()) {
            return;
        }
        front = (front + cap - 1) % cap;
        arr[front] = x;
        size++;
    }

    void deleteFront() {
        if (isEmpty()) {
            return;
        }
        front = (front + 1) % cap;
        size--;
    }

    int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return arr[front];
    }

}

Deque in Java

The Deque interface in Java extends the Queue interface. Therefore it supports both Queue and Deque functionalities. But we are supposed to use specific methods provided for that data structure.

The LinkedList class implements both List and Deque interfaces.

import java.util.Deque;
import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
        Deque<Integer> d = new LinkedList<>();
        d.offerFirst(10);
        d.offerFirst(20);

        d.offerLast(5);
        d.offerLast(15);

        System.out.println(d.peekFirst()); // 20
        System.out.println(d.peekLast()); // 15

        d.pollFirst();
        d.pollLast();
        System.out.println(d.peekFirst()); // 10
        System.out.println(d.peekLast()); // 5
    }
}

Java provides two sets of methods one throws the exception, and another doesn’t. The methods used in the above program won’t throw exceptions. But the methods used in the below program throw an exception.

import java.util.Deque;
import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
        Deque<Integer> d = new LinkedList<>();
        d.addFirst(10);
        d.addFirst(20);

        d.addLast(5);
        d.addLast(15);

        System.out.println(d.getFirst()); // 20
        System.out.println(d.getLast()); // 15

        d.removeFirst();
        d.removeLast();
        System.out.println(d.getFirst()); // 10
        System.out.println(d.getLast()); // 5
    }
}

Operation	Methods that Do not Throw Exceptions	Methods that Throw Exceptions
Add Element at Front	offerFirst()	addFirst()
Add Element at Rear	offerLast()	addLast()
Get Element from Front	peekFirst()	getFirst()
Get Element from Rear	peekLast()	getLast()
Delete Element from Front	pollFirst()	removeFirst()
Delete Element from Rear	pollLast()	removeLast()

Traversing a Deque

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
        Deque<Integer> d = new LinkedList<>();
        d.addFirst(10);
        d.addFirst(20);
        d.addLast(5);
        d.addLast(15);

        // iterator (first to last)
        Iterator<Integer> it = d.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println();

        // for-each loop (first to last)
        for (int k : d) {
            System.out.print(k + " ");
        }
        System.out.println();

        // iterator (last to first)
        Iterator<Integer> dec = d.descendingIterator();
        while (dec.hasNext()) {
            System.out.print(dec.next() + " ");
        }
        System.out.println();
    }
}

ArrayDeque in Java

Collection <= Queue <= Deque <– ArrayDeque

ArrayDeque is faster than LinkedList on average, and it can be used as a Stack/Queue/Deque. It contains methods for Stack/Queue/Deque data structures. In fact when we want to use Stack then ArrayDeque is more preferred in a single thread environment because of non-thread-safe (Stack class is thread safe because it is inherited from Vector class).

import java.util.ArrayDeque;

public class Test {
    public static void main(String[] args) {
        ArrayDeque<Integer> ad = new ArrayDeque<>();
        ad.add(10);
        ad.add(20);
        ad.add(30);
        System.out.println(ad); // 10 20 30
    }
}

ArrayDeque as a Stack

Stack follows LIFO (Last In First Out) where items are added from the rear/end and also removed from the rear/end.

import java.util.ArrayDeque;

public class Test {
    public static void main(String[] args) {
        ArrayDeque<Integer> ad = new ArrayDeque<>();
        ad.push(10);
        ad.push(20);
        System.out.println(ad.peek()); // 20
        System.out.println(ad.pop()); // 20
        System.out.println(ad.peek()); // 10
        ad.push(30);
        System.out.println(ad.peek()); // 30
    }
}

ArrayDeque as a Queue

Queue follows FIFO (First In First Out) where items are added from the rear/end and removed from the front.

import java.util.ArrayDeque;

public class Test {
    public static void main(String[] args) {
        ArrayDeque<Integer> ad = new ArrayDeque<>();
        ad.offer(10);
        ad.offer(20);
        System.out.println(ad.peek()); // 10
        System.out.println(ad.poll()); // 10
        System.out.println(ad.peek()); // 20
        ad.offer(30);
        System.out.println(ad.peek()); // 20
    }
}

Operation	Methods that Do not Throw Exceptions	Methods that Throw Exceptions
Retrieve Element	peek()	element()
Add Element	offer()	add()
Remove Element	poll()	remove()

If we call poll()/peek() on empty queue then it returns null but remove()/element() throws java.util.NoSuchElementException. Both add() and offer() methods return true if the element is successfully added. The primary difference is how they handle capacity constraints.

• add(): Throws an IllegalStateException if the capacity limit is reached (although ArrayDeque does not impose a fixed limit, other queue implementations might).
• offer(): Returns false if the capacity limit is reached, instead of throwing an exception.

ArrayDeque as Deque

It is a double-ended queue where we can insert/remove from both ends (front and rear).

import java.util.ArrayDeque;

public class Test {
    public static void main(String[] args) {
        ArrayDeque<Integer> ad = new ArrayDeque<>(1);
        ad.offerFirst(10);
        ad.offerLast(20);
        ad.offerFirst(30);
        ad.offerLast(40);
        System.out.println(ad); // 30 10 20 40

        System.out.println(ad.peekFirst()); // 30
        System.out.println(ad.peekLast()); // 40

        System.out.println(ad.pollFirst()); // 30
        System.out.println(ad.peekFirst()); // 10

        System.out.println(ad.pollLast()); // 40
        System.out.println(ad.peekLast()); // 20
    }
}

Operation	Methods that Do not Throw Exceptions	Methods that Throw Exceptions
Add First	offerFirst()	addFirst()
Add Last	offerLast()	addLast()
Remove First	pollFirst()	removeFirst()
Remove Last	pollLast()	removeLast()
Get First	peekFirst()	getFirst()
Get Last	peekLast()	getLast()

If we call pollFirst()/pollLast()/peekFirst()/peekLast() on empty queue then it returns null but removeFirst()/removeLast()/getFirst()/getLast() throws java.util.NoSuchElementException.

The offerFirst()/offerLast()/addFirst()/addLast() methods return true if the element is successfully added. The primary difference is how they handle capacity constraints.

• addFirst()/addLast(): Throws an IllegalStateException if the capacity limit is reached (although ArrayDeque does not impose a fixed limit, other queue implementations might).
• offerFirst()/offerLast(): Returns false if the capacity limit is reached, instead of throwing an exception.

Redundant Methods (for Queue):-

Standard Method (throw Exception)	Equivalent Method (Don’t throw Exception
add()	addLast()
remove()	removeFirst()
poll()	pollFirst()
offer()	offerLast()
element()	getFirst()
peek()	peekFirst()

Redundant Methods (for Stack):-

Standard Method (throw Exception)	Equivalent Method (Don’t throw Exception
push()	addFirst()
pop()	removeFirst()

The time complexity of all these methods of the ArrayDeque class is amortized O(1) [on average] not the worst case. Amortized analysis considers the average time per operation over a sequence of operations, rather than the worst-case time for a single operation. The O(1) amortized time complexity means that while individual operations might occasionally be more costly, the average time per operation is constant over a series of operations. This makes ArrayDeque an efficient data structure for most practical applications.

2. Design a Data Structure with Min and Max Operations

Design a data structure that supports the following operations in O(1) time complexity.

1. insertMin(x): The element to be inserted is always less than the existing items.
2. insertMax(x): The element to be inserted is always greater than existing items.
3. getMin(): Find the current minimum.
4. getMax(): Find the current maximum.
5. extractMin(): Remove minimum.
6. extractMax(): Remove maximum.

Input:

• insertMin(5)
• insertMax(10)
• insertMin(3)
• insertMax(15)
• insertMin(2)
• getMin()
• getMax()
• insertMin(1)
• getMin()
• insertMax(20)
• getMax()

Output: 2 15 1 20

To solve this we will use Deque data structure.

import java.util.ArrayDeque;
import java.util.Deque;

public class MyDS {
    Deque<Integer> dq;

    public MyDS() {
        dq = new ArrayDeque<>();
    }

    void insertMin(int x) {
        dq.offerFirst(x);
    }

    void insertMax(int x) {
        dq.offerLast(x);
    }

    int getMin() {
        return dq.peekFirst();
    }

    int getMax() {
        return dq.peekLast();
    }

    int extractMin() {
        return dq.pollFirst();
    }

    int extractMax() {
        return dq.pollLast();
    }
}

public class Test {
    public static void main(String[] args) {
        MyDS my = new MyDS();
        my.insertMin(5);
        my.insertMax(10);
        my.insertMin(3);
        my.insertMax(15);
        my.insertMin(2);

        System.out.println("Min: " + my.getMin()); // Output: 2
        System.out.println("Max: " + my.getMax()); // Output: 15

        my.insertMin(1);
        System.out.println("Min: " + my.getMin()); // Output: 1

        my.insertMax(20);
        System.out.println("Max: " + my.getMax()); // Output: 20
    }
}

3. Maximum of all Subarrays of Size K

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. Problem: 239*

Input: arr[ ] = {20, 5, 3, 8, 6, 15}, k = 4
Output: 20 8 15

Input: arr[ ] = {10, 8, 5, 12, 15, 7, 6}, k = 3
Output: 10 12 15 15

We will use a deque of size k in such a way that the front of the queue stores the maximum of the current windows. We will store the index of the array in deque rather than array elements.

• Whenever we see an upcoming element is larger than the last element then remove the last element.
• Insert the element at the end. In this way, elements are stored in decreasing order in the queue (through its indexes).

For elements: 5, 8, 10

• We store the index of 5 in the deque. Deque = [0]
• While storing 8, the existing element is less than 8 so remove the index of 5 and insert an index of 8. Deque = [1]
• While storing 10, the existing element is less than 10 so remove the index of 8 and insert the index of 10. Deque = [2]

import java.util.ArrayDeque;
import java.util.Deque;

public class Test {
    public static void main(String[] args) {
        int arr[] = { 10, 8, 5, 12, 15, 7, 6 };
        int k = 3;
        maxSubArraySizeK(arr, k);
    }

    private static void maxSubArraySizeK(int[] arr, int k) {
        Deque<Integer> dq = new ArrayDeque<>(); 

        // Process the first sub-array of size k
        for (int i = 0; i < k; i++) {
            // Remove elements that are smaller than the current element
            while (!dq.isEmpty() && arr[i] >= arr[dq.peekLast()]) {
                dq.removeLast();
            }
            // Add the current element's index at the end of the deque
            dq.addLast(i);
        }

        // Process the rest of the array
        for (int i = k; i < arr.length; i++) {
            // Print the maximum element of the previous sub-array
            System.out.print(arr[dq.peekFirst()] + " ");

            // Remove the element from the front if it is out of this window
            while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.removeFirst();
            }

            // Remove elements from the back of the deque if they are smaller 
            // than the current element
            while (!dq.isEmpty() && arr[i] >= arr[dq.peekLast()]) {
                dq.removeLast();
            }

            // Add the current element's index at the end of the deque
            dq.addLast(i);
        }
        // Print the maximum element of the last sub-array
        System.out.println(arr[dq.peekFirst()]);
    }
}

Time complexity O(n). All elements from the array will go to the queue exactly once and come out of the queue almost once.

4. Minimum of all Subarrays of Size K

import java.util.ArrayDeque;
import java.util.Deque;

public class Test {
    public static void main(String[] args) {
        int arr[] = { 10, 8, 5, 12, 15, 7, 6 };
        int k = 3;
        minSubArraySizeK(arr, k);
    }

    private static void minSubArraySizeK(int[] arr, int k) {
        int n = arr.length;
        Deque<Integer> dq = new ArrayDeque<>();

        for (int i = 0; i < k; i++) {
            // Remove larger elements from end
            while (!dq.isEmpty() && arr[i] <= arr[dq.peekLast()]) {
                dq.removeLast();
            }
            dq.addLast(i);
        }

        for (int i = k; i < n; i++) {
            System.out.print(arr[dq.peekFirst()] + " ");

            while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.removeFirst();
            }

            while (!dq.isEmpty() && arr[i] <= arr[dq.peekLast()]) {
                dq.removeLast();
            }

            dq.addLast(i);
        }

        System.out.println(arr[dq.peekFirst()]);
    }
}

5. First Circular Tour

You are given two arrays: petrol[ ] and dist[ ], where petrol[i] represents the amount of petrol available at petrol pump i, and dist[i] represents the distance from petrol pump i to the next petrol pump. Problem: 134

Your task is to find the starting petrol pump index from which you can travel around the circular tour and return to the same petrol pump, provided that you have enough storage to store the petrol. Using 1 unit of petrol you can travel 1 unit of distance.

If there are multiple such petrol pumps, then we have to return the first petrol pump. If it’s not possible to complete the tour, return -1.

Example 1:
Input: petrol[ ] = {4, 8, 7, 4}, dist[ ] = {6, 5, 3, 5}
Output: 2. Starting from index 2, the petrol available and distance are sufficient to complete the circular tour.

Example 2:
Input: petrol[ ] = {4, 8}, dist[ ] = {5, 6}
Output: 2

Example 3:
Input: petrol[ ] = {8, 9, 4}, dist[ ] = {5, 10, 12}
Output: -1

Naive Solution: O(n^2)

Consider every petrol pump as a starting point. Move from one petrol pump to another petrol pump and observe how much petrol we have now.

public class Test {
    public static void main(String[] args) {
        int petrol[] = { 4, 8, 7, 4 }, dist[] = { 6, 5, 3, 5 };
        System.out.println(circularTour(petrol, dist));
    }

    private static int circularTour(int[] petrol, int[] dist) {
        int n = petrol.length;
        for (int start = 0; start < n; start++) {
            int currPetrol = 0;
            int end = start;
            while (true) {
                currPetrol += (petrol[end] - dist[end]);
                if (currPetrol < 0) {
                    break;
                }
                end = (end + 1) % n;
                if (start == end) {
                    return start + 1;
                }
            }
        }
        return -1;
    }
}

Time complexity: O(n^2) in the worst case and auxiliary space O(1).

Better Solution: O(n)

We can use the Deque data structure. Approach:-

• Keep adding petrol pumps to the end of the deque while currPetrol is greater than equal to 0.
• Keep removing petrol pumps from the front of the deque while currPetrol is negative.

In this solution, we added every element at most once to the deque and removed almost once from the deque. Therefore it requires O(n) auxiliary space and has time complexity O(n).

Efficient Solution

It has time complexity O(n) and auxiliary space O(1). We can avoid using Deque and will use the original array as a Deque. Here are some facts:-

• If the currentPetrol becomes negative at P_i, then none of the petrol pumps from P₀ to P_i can be the solution.

public class Test {
    public static void main(String[] args) {
        int petrol[] = { 4, 8, 7, 4 }, dist[] = { 6, 5, 3, 5 };
        System.out.println(circularTour(petrol, dist));
    }

    private static int circularTour(int[] petrol, int[] dist) {
        int start = 0, currPetrol = 0, prevPetrol = 0;

        for (int i = 0; i < petrol.length; i++) {
            // Calculate the net petrol after visiting the current petrol pump
            currPetrol += (petrol[i] - dist[i]);

            // If currPetrol is negative, we cannot complete the tour starting from 'start'
            if (currPetrol < 0) {
                start = i + 1;
                // Store the petrol shortfall
                prevPetrol += currPetrol;
                // Reset the current petrol to 0 as we start afresh from the next pump
                currPetrol = 0;
            }
        }

        // Check if the total petrol (current + previous shortfall) is enough to
        // complete the tour
        // Return the start index if possible, otherwise return -1
        return ((currPetrol + prevPetrol) >= 0) ? start + 1 : -1;
    }
}

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search