logologo
  • AI Tools

    DB Query GeneratorMock InterviewResume BuilderLearning Path GeneratorCheatsheet GeneratorAgentic Prompt GeneratorCompany ResearchCover Letter Generator
  • XpertoAI
  • MVP Ready
  • Resources

    CertificationsTopicsExpertsCollectionsArticlesQuestionsVideosJobs
logologo

Elevate Your Coding with our comprehensive articles and niche collections.

Useful Links

  • Contact Us
  • Privacy Policy
  • Terms & Conditions
  • Refund & Cancellation
  • About Us

Resources

  • Xperto-AI
  • Certifications
  • Python
  • GenAI
  • Machine Learning

Interviews

  • DSA
  • System Design
  • Design Patterns
  • Frontend System Design
  • ReactJS

Procodebase © 2024. All rights reserved.

Level Up Your Skills with Xperto-AI

A multi-AI agent platform that helps you level up your development skills and ace your interview preparation to secure your dream job.

Launch Xperto-AI

Sliding Window Maximum Using Priority Queue

author
Generated by
Parveen Sharma

16/11/2024

Sliding Window

Sign in to read full article

Introduction

The Sliding Window Maximum problem is a classic algorithmic challenge that arises in various scenarios, especially in data analysis and streaming applications. The problem can be stated as follows:

Given an array of integers and a number k, find the maximum for each sliding window of size k across the array.

For example, if you have the array [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the sliding windows would be:

  • Window 1: [1, 3, -1] → Maximum = 3
  • Window 2: [3, -1, -3] → Maximum = 3
  • Window 3: [-1, -3, 5] → Maximum = 5
  • Window 4: [-3, 5, 3] → Maximum = 5
  • Window 5: [5, 3, 6] → Maximum = 6
  • Window 6: [3, 6, 7] → Maximum = 7

The expected output for the above example would be [3, 3, 5, 5, 6, 7].

Why Use a Priority Queue?

A naive approach would involve iterating through each window and determining the maximum for each, which takes O(k) time for every window in a total of O(n*k) time complexity where n is the number of elements in the array. This is not efficient, especially for larger inputs.

Instead, we can utilize a priority queue (or max-heap) to achieve much greater performance. A priority queue allows us to efficiently insert, delete, and extract maximum (or minimum) elements, leading to an overall time complexity of O(n log k) for this problem.

Implementation in Java

Let's get into the implementation details. Below is a Java code snippet demonstrating how to solve the Sliding Window Maximum problem using a priority queue:

import java.util.*; public class SlidingWindowMaximum { public static int[] maxSlidingWindow(int[] nums, int k) { if (nums == null || nums.length == 0 || k == 0) return new int[0]; int n = nums.length; int[] result = new int[n - k + 1]; PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]); // Max-Heap for maximum retrieval for (int i = 0; i < n; i++) { maxHeap.offer(new int[]{nums[i], i}); // Store both value and its index // Remove elements out of the current window if (i >= k - 1) { while (maxHeap.peek()[1] < i - k + 1) { maxHeap.poll(); // Remove old entries } result[i - k + 1] = maxHeap.peek()[0]; // The current maximum is at the top } } return result; } public static void main(String[] args) { int[] nums = {1, 3, -1, -3, 5, 3, 6, 7}; int k = 3; int[] result = maxSlidingWindow(nums, k); System.out.println("Sliding Window Maximum: " + Arrays.toString(result)); } }

Explanation of the Code

  1. Input and Initialization: The method maxSlidingWindow takes an integer array nums and an integer k. We initialize a result array of the size n - k + 1 to store maximum values and a priority queue to maintain the current window's maximum values.

  2. Iterating Over the Input Array:

    • For each element in the array, we add it along with its index to the priority queue.
    • After processing the first k elements, we begin to store results.
  3. Maintenance of the Sliding Window:

    • Before recording the current maximum, we ensure that we remove any elements from the top of the priority queue that are no longer in the current sliding window. This is achieved by checking if the index of the element at the top of the heap is less than the current window's starting index (i - k + 1).
  4. Storing the Maximum: The element at the top of the priority queue (maxHeap.peek()[0]) holds the maximum value of the current sliding window, which we store in the results array.

  5. Output: Finally, the resulting array of sliding window maximums is printed in the main method.

Conclusion

This approach harnesses the power of priority queues to efficiently compute the maximum values within sliding windows in an array. Using a max-heap allows us to maintain a running maximum in logarithmic time, making it a chic solution for handling this type of problem efficiently.

Feel free to experiment with different inputs and see how the algorithm performs! Happy coding!

Popular Tags

Sliding WindowPriority QueueJava

Share now!

Like & Bookmark!

Related Collections

  • Trees Interview Questions Using Java

    13/10/2024 | DSA

  • Advanced Recursion and Backtracking Problems Using Java

    13/10/2024 | DSA

  • Mastering Arrays : The Basic Data Structure

    06/12/2024 | DSA

  • Advanced Priority Queue and Heap Interview Questions in Java

    16/11/2024 | DSA

  • Advanced String-based Interview Techniques

    15/11/2024 | DSA

Related Articles

  • Detecting Cycles in Directed and Undirected Graphs

    16/11/2024 | DSA

  • Finding the Kth Smallest and Largest Element in a Binary Search Tree

    13/10/2024 | DSA

  • Array Challenges and Problem Solving in DSA

    06/12/2024 | DSA

  • Unraveling the Mystery of Finding Duplicates in Arrays

    06/12/2024 | DSA

  • Trie-Based Dynamic Programming

    15/11/2024 | DSA

  • Understanding Array Rotation

    06/12/2024 | DSA

  • Bit Shifting Operations

    08/12/2024 | DSA

Popular Category

  • Python
  • Generative AI
  • Machine Learning
  • ReactJS
  • System Design