Deque - Data Structure

Опубликовано: 13 Октябрь 2024
на канале: Gaurav Sen

60,718

715

The Deque is a double ended queue which comes in handy when we are working with continuous ranges. The problem solved here is finding all maximum elements in ranges of size R for a given array.

The brute force approach takes O(N^2) time to find the largest amongst all segments of size R. A heap does much better, taking O(N*logR) time.

The best solution uses a Deque data structure to bring down the complexity to O(N). This is possible because we keep track of which elements should be compared with the one being currently inserted.

Problem statement with solution:
www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/

Practice Problems:
https://www.codechef.com/MAY15/proble...
https://www.codechef.com/FEB17/proble...
https://www.codechef.com/JUNE16/probl...