Algorithms and Data Structures · Middle · Question 23 of 75
Which structure gives O(1) insertion and removal at both ends?
- 1A balanced binary search tree
- ✓Correct answer: A deque (double-ended queue)
- 3A sorted array with binary search
Explanation
A deque is usually a ring buffer or a doubly linked list. It's the key structure for "sliding window maximum" in O(n): it keeps candidate indices in decreasing order of value.