A monotonic sequence is a sequence that is either entirely non-increasing or entirely non-decreasing.

Ordered Data Structures Comparison

UseCase: Dijkstra, Top-K, Scheduling | Track min or max in a sliding window: The values in Queue are changed when the window slides.

****UseCase: Sliding Window Max/Min | Track previous/next smaller or larger element

UseCase: Histogram Area, Stock Span, Next Greater Element | | Data Order Maintained | Monotonic | Tree in-order | Heap order | Monotonic

To maintain monotonic, improve time complexity, and reflect the window range, stale and unrelated values will be removed. | Monotonic | | Push Time Complexity | O(n) O(1) (push end)

Push + shifting | O(log n ~ n)

Binary Search | O(log n)

Push + Percolate Up | Amortized O(1)

Push + removing Stale and unrelated values will be removed. | Amortized O(1)

Push + removing | | Pop Time Complexity | O(n) O(1) (pop end/top)

Pop + shifting | O(log n ~ n)

Pop root + connect nodes | O(log n)

Pop index 0 + Percolate Down | O(1)

Pop index 0 Only stale value will be removed. | O(1)

Pop index len-1 | | Random removal? | ✅  O(n) | ✅  O(log n ~ n) | ⚠️  Lazy removal (with a map) | ❌ | ❌ | | Peek Min/Max Time Complexity | O(1)

Return index 0 or len-1 | O(log n ~ n)

Return the leftest or the rightest leaf node. | O(1)

Return index 0 | O(1)

Return index 0 | O(1)

Return index len-1 | | Space Complexity | O(n) | O(n) | O(n) | O(n) | O(n) |

Monotonic Queues

A Monotonic Queues is a Queue (on its behaviour, but it is implemented by Deque) that maintains its elements in a monotonic order.

• Monotonic Increasing Queue: It is used to track min. (Get the value by Peek method)
• Monotonic Decreasing Queue: It is used to track max. (Get the value by Peek method)

Behaviour

• When a new value is pushed into Queue, it will remove values which are greater or smaller, so the pushing value will be the smallest or largest, it indicates (the purpose) what’s the largest or smallest value (at the peek position) at this sliding window state.
  • Why removing values instead of shifting like Heap or Sorted Array?
    • To improve time complexity to amortized O(1) over the sequence
    • The removing values serve no purpose, they are not the largest or smallest. The removal procedure could also remove the previous window stale value then the pushing value becomes to be the Peek.
    • The remaining values (except peek value) in the Queue after removing are not the largest or smallest, but they could be when the window slides.
• When the window slides, the Pop is needed since we don’t want to include stale largest/smallest value, it doesn’t belong to the new state. If the Peek value belongs to current window already, no pop is proceeded.

Example: Decreasing Queue

• Push
  • It removes all elements smaller than n from the back
  • Time Complexity: O(1)
    • The worst case is k (k is number of elements smaller than n in the stack). But in a sequence, deleted elements in the queue won’t appear again, so the time complexity is amortized to ****O(1).
• Peek/Pop
  • The large element in the queue
  • Time Complexity: ****O(1)

type DecrQueue struct {
    data []int
}

func (mq *DecrQueue) Push(n int) {
    for len(mq.data) > 0 && mq.data[len(mq.data)-1] < n {
        mq.data = mq.data[:len(mq.data)-1]
    }
    mq.data = append(mq.data, n)
}

func (mq *DecrQueue) Pop(n int) {
    if len(mq.data) > 0 && mq.data[0] == n {
        mq.data = mq.data[1:]
    }
}

func (mq *DecrQueue) Peek() int {
    return mq.data[0]
}

Monotonic Stacks

A Monotonic Stack is a Stack that maintains its elements in a monotonic order.

Behaviour

• When a new value is pushed into Stack, it removes values which are greater or smaller, so the pushing value will be the smallest or largest, it indicates (the purpose) what’s the remaining values in the stack which are smaller or larger or what’s the removing values which are larger or smaller at this current state.
• The Pop operation is the same as a regular stack's pop operation. However, in the context of using a monotonic stack to solve a problem, we often don't explicitly call it.

Example: Decreasing Stack