Competitive Programming Problems: Queues and Deques in Java

This document explores the use of Queues and Deques in solving competitive programming problems efficiently in Java. We will delve into specific problem examples, focusing on optimization techniques to achieve optimal performance.

Introduction to Queues and Deques

Before diving into problems, let's briefly review the fundamental properties of Queues and Deques:

• Queue: Follows the First-In, First-Out (FIFO) principle. Elements are added at the rear (enqueue) and removed from the front (dequeue). In Java, `java.util.Queue` is an interface, and common implementations include `java.util.LinkedList`.
• Deque (Double-Ended Queue): Allows insertion and removal of elements from both ends. In Java, `java.util.Deque` is an interface, and `java.util.ArrayDeque` is a commonly used implementation. ArrayDeque is usually preferred for its performance advantages.

Understanding these structures and their respective operations (enqueue, dequeue, peek, addFirst, addLast, removeFirst, removeLast) is crucial for solving many algorithmic problems effectively.

Problem 1: Sliding Window Maximum

 import java.util.ArrayDeque;
import java.util.Deque;
import java.util.ArrayList;
import java.util.List;

class SlidingWindowMaximum {
    public List maxSlidingWindow(int[] nums, int k) {
        Deque deque = new ArrayDeque<>(); // Stores indices
        List result = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            // Remove elements out of window
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // Remove smaller elements in deque
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }

            // Add current element index
            deque.offerLast(i);

            // Add to result if window is full
            if (i >= k - 1) {
                result.add(nums[deque.peekFirst()]);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        SlidingWindowMaximum solution = new SlidingWindowMaximum();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        List result = solution.maxSlidingWindow(nums, k);
        System.out.println("Maximums: " + result); // Output: Maximums: [3, 3, 5, 5, 6, 7]
    }
} 

Problem 2: First Negative Integer in Every Window of Size K

 import java.util.ArrayDeque;
import java.util.Deque;
import java.util.ArrayList;
import java.util.List;

class FirstNegativeInteger {
    public List firstNegativeInteger(int[] nums, int k) {
        Deque deque = new ArrayDeque<>(); // Stores indices of negative numbers
        List result = new ArrayList<>();

        // Process the first k elements
        for (int i = 0; i < k; i++) {
            if (nums[i] < 0) {
                deque.offerLast(i);
            }
        }

        // Process the remaining elements
        for (int i = k; i < nums.length; i++) {
            // Add the first negative number of the previous window to the result
            if (!deque.isEmpty()) {
                result.add(nums[deque.peekFirst()]);
            } else {
                result.add(0);
            }

            // Remove elements that are out of the current window
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // Add the current element to the deque if it's negative
            if (nums[i] < 0) {
                deque.offerLast(i);
            }
        }

        // Add the first negative number of the last window to the result
        if (!deque.isEmpty()) {
            result.add(nums[deque.peekFirst()]);
        } else {
            result.add(0);
        }

        return result;
    }

    public static void main(String[] args) {
        FirstNegativeInteger solution = new FirstNegativeInteger();
        int[] nums = {12, -1, -7, 8, -15, 30, 16, 28};
        int k = 3;
        List result = solution.firstNegativeInteger(nums, k);
        System.out.println("First Negative Integers: " + result); // Output: First Negative Integers: [-1, -1, -7, -15, -15, 0]
    }
} 

Problem 3: Minimum Cost to Connect Sticks

 import java.util.PriorityQueue;
import java.util.Queue;

class ConnectSticks {
    public int connectSticks(int[] sticks) {
        // Use a min heap (PriorityQueue) to store stick lengths.
        Queue minHeap = new PriorityQueue<>();
        for (int stick : sticks) {
            minHeap.offer(stick);
        }

        int totalCost = 0;
        while (minHeap.size() > 1) {
            // Take the two shortest sticks.
            int stick1 = minHeap.poll();
            int stick2 = minHeap.poll();

            // Connect them and add the cost to the total.
            int cost = stick1 + stick2;
            totalCost += cost;

            // Add the new stick back to the heap.
            minHeap.offer(cost);
        }

        return totalCost;
    }

    public static void main(String[] args) {
        ConnectSticks solution = new ConnectSticks();
        int[] sticks = {2, 4, 3};
        int minCost = solution.connectSticks(sticks);
        System.out.println("Minimum Cost: " + minCost); // Output: Minimum Cost: 14
    }
} 

Optimization Techniques

Here are some common optimization techniques when using Queues and Deques in competitive programming:

• Choose the Right Implementation: `ArrayDeque` is generally more efficient than `LinkedList` for `Deque` operations. For Queues where order matters by priority, use PriorityQueue.
• Space Optimization: Be mindful of the maximum size of the Queue/Deque, especially when dealing with large datasets. Avoid unnecessary object creation.
• Avoid Unnecessary Operations: Carefully analyze the problem to minimize the number of enqueue, dequeue, and peek operations.
• Pre-processing: If possible, pre-process the input data to reduce the workload during the main algorithm.
• Early Exit Conditions: Identify conditions under which the algorithm can terminate early to save time.

Conclusion

Queues and Deques are versatile data structures that can be used to solve a wide variety of competitive programming problems efficiently. Understanding their properties and applying appropriate optimization techniques is crucial for achieving optimal performance. The provided examples demonstrate how these data structures can be used effectively in Java.