2.1. Vector and Deque

Vectors are the go-to choice when you need a sequence of elements whose size might change during your program’s execution. Here’s what makes them special:

• Contiguous Storage: A vector stores its elements in a single, continuous block of memory. This provides lightning-fast random access to elements using their index. Think of it like a neatly organized bookshelf where you can instantly locate any book by its position.

• Growth and Shrinkage: Vectors automatically expand or shrink as you add (push_back) or remove (pop_back) elements. This dynamic nature eliminates the need to manually pre-allocate or resize arrays.

• Efficiency at the End: Adding or removing elements from the end of a vector is extremely fast, usually taking constant time \(O(1)\).

Many data structure and algorithms can be implemented with vector. The related algorithms include sorting, binary search, two pointers. There are non-sequential data structures flattened as vectors, like disjoint set (union find), heap tree, segment tree, binary index tree, flat map, flat interval tree etc.

Note

• Array Replacement: If you need an array-like structure that can grow and shrink, vectors are an ideal replacement for traditional C-style arrays.

• Fast Back-End Operations: When you frequently add or remove elements from the back of your sequence, vectors excel.

---

Deques (pronounced “decks”) are double-ended queues. You can efficiently insert and remove elements from both the front and the back, offering more flexibility than traditional stacks or queues. It is normally implemented by vector under the hood [1].

Adaptable Structure: Internally, a deque may be represented as multiple smaller chunks of memory. This gives it flexibility but makes random access by index slightly slower than vectors.

Front and Back Agility: The defining feature of deques is their efficiency in adding (push_front, push_back) and removing (pop_front, pop_back) elements from either end. These operations maintain constant time complexity \(O(1)\).

Note

• Queues and Stacks: Deques are the natural choice when implementing queues (first-in, first-out) or stacks (last-in, first-out) in your program.

• Flexibility Needed: If you need to frequently manipulate both the beginning and end of your sequence, deques offer an advantage over vectors.

Footnotes

[1]

Deque is typically implemented as a vector of arrays (a linked-list of arrays can’t give constant time random access). The size of the arrays is implementation dependent, commonly a constant size in bytes (4096 for libc++, 512 for libstdc++, 16 for MS STL).

In the following sections, we will discussion some algorithms related to vector and deque.

• 2.1.1. Sort
  • 2.1.1.1. Sorting in linear time and constant space
  • 2.1.1.2. Wiggle Sort
  • 2.1.1.3. Strict Wiggle Sort
• 2.1.2. Two Pointers
  • 2.1.2.1. Maximize Number of Subsequences in a String
• 2.1.3. Cumulative Sum
  • 2.1.3.1. Maximum Size Subarray Sum Equals k
  • 2.1.3.2. Longest Subarray With Equal 0 and 1
  • 2.1.3.3. Continuous Subarray Sum
  • 2.1.3.4. Maximum Subarray
• 2.1.4. Sliding Window
  • 2.1.4.1. Fixed Window
    • 2.1.4.1.1. Sliding Window Maximum
    • 2.1.4.1.2. Sliding Window Meidan
  • 2.1.4.2. Variable Window
    • 2.1.4.2.1. Find All Anagrams in a String
    • 2.1.4.2.2. Minimum Window Substring
    • 2.1.4.2.3. Longest Substring with At Most Two Distinct Characters
    • 2.1.4.2.4. Longest Substring Without Repeating Characters
• 2.1.5. Meeting Room
  • 2.1.5.1. Meeting Rooms
  • 2.1.5.2. Partition Labels
• 2.1.6. Questions
  • 2.1.6.1. Maximum Subarray
  • 2.1.6.2. Maximum Score Of Spliced Array