Go Guide

Core patterns · Lesson 21 of 62 · about 45 min

Deques & monotonic queues

A double-ended queue built on a ring buffer, and the monotonic deque that answers sliding-window maximum and shortest-subarray questions in O(n).

pkg.go.dev: container/list ↗pkg.go.dev: container/ring ↗
On this page · 9 sections
  1. 01Why a plain slice is not enough
  2. 02A ring buffer deque
  3. 03Sliding window maximum
  4. 04Shortest subarray with sum at least K, negatives allowed
  5. 05Recognizing the pattern
  6. 06Complexity
  7. 07Summary
  8. 08Check your understanding
  9. 09Practice in Go

Why a plain slice is not enough#

A slice is a great stack (push and pop at the end) and an acceptable queue for BFS (q = q[1:]). But adding at the front of a slice means shifting every element: O(n). And q = q[1:] never reuses the space at the front, so a long-running queue keeps growing its backing array.

Structurepush backpop frontpush frontmemory reuse
slice, s[1:] to popO(1) amortizedO(1)O(n)no
container/listO(1)O(1)O(1)yes, but one allocation per element
ring bufferO(1) amortizedO(1)O(1)yes, one contiguous slice

A ring buffer deque#

Store elements in a fixed slice and treat it as a circle. head is the index of the front element and size is how many elements there are. The back is at (head + size - 1) % cap. Pushing at the front moves head one step backward around the circle; popping from the front moves it forward. When the buffer is full, allocate one twice as big and copy the elements in order.

cap 8, head 6, size 4:   index  0  1  2  3  4  5  6  7
                                c  d  .  .  .  .  a  b
                         front = a (index 6), back = d (index 1): the data wraps around
deque.go
Go
package main
 
import "fmt"
 
// Deque is a double-ended queue backed by a growable ring buffer.
// The zero value is an empty deque ready to use.
type Deque[T any] struct {
	buf        []T
	head, size int
}
 
func (d *Deque[T]) Len() int { return d.size }
 
func (d *Deque[T]) grow() {
	if d.size < len(d.buf) {
		return
	}
	nb := make([]T, max(4, 2*len(d.buf)))
	for i := range d.size { // copy in logical order, unwrapping the circle
		nb[i] = d.buf[(d.head+i)%len(d.buf)]
	}
	d.buf, d.head = nb, 0
}
 
func (d *Deque[T]) PushBack(v T) {
	d.grow()
	d.buf[(d.head+d.size)%len(d.buf)] = v
	d.size++
}
 
func (d *Deque[T]) PushFront(v T) {
	d.grow()
	d.head = (d.head - 1 + len(d.buf)) % len(d.buf) // step backward, wrapping
	d.buf[d.head] = v
	d.size++
}
 
func (d *Deque[T]) PopFront() (T, bool) {
	var zero T
	if d.size == 0 {
		return zero, false
	}
	v := d.buf[d.head]
	d.buf[d.head] = zero // let the garbage collector reclaim what v pointed to
	d.head = (d.head + 1) % len(d.buf)
	d.size--
	return v, true
}
 
func (d *Deque[T]) PopBack() (T, bool) {
	var zero T
	if d.size == 0 {
		return zero, false
	}
	i := (d.head + d.size - 1) % len(d.buf)
	v := d.buf[i]
	d.buf[i] = zero
	d.size--
	return v, true
}
 
func (d *Deque[T]) Front() T { return d.buf[d.head] }
func (d *Deque[T]) Back() T  { return d.buf[(d.head+d.size-1)%len(d.buf)] }
 
func main() {
	var d Deque[string]
	d.PushBack("b")
	d.PushBack("c")
	d.PushFront("a")
	d.PushBack("d")
	fmt.Println("len", d.Len(), "front", d.Front(), "back", d.Back(), "buf", d.buf, "head", d.head)
 
	d.PushFront("z") // the buffer is full (cap 4), so it grows to 8 and unwraps
	fmt.Println("after growing:", d.buf, "head", d.head)
 
	for d.Len() > 0 {
		f, _ := d.PopFront()
		fmt.Print(f, " ")
		if b, ok := d.PopBack(); ok {
			fmt.Print(b, " ")
		}
	}
	fmt.Println()
	_, ok := d.PopFront()
	fmt.Println("pop on empty ok:", ok)
}
Output
len 4 front a back d buf [b c d a] head 3
after growing: [a b c d    z] head 7
z d a c b 
pop on empty ok: false

Look at the first buf line: a was pushed at the front of an empty-headed buffer, so it landed at index 3 (one step backward from 0, wrapping), while b, c and d sit at 0, 1 and 2. Logically the deque is a b c d. Growing copies it out in that logical order.

Sliding window maximum#

"For every window of k consecutive values, report the maximum." Rescanning each window costs O(n·k). A heap gives O(n log n). A monotonic deque gives O(n).

The deque holds indexes, and their values decrease from front to back. For each new index i:

  1. If the front index has slid out of the window (front <= i-k), pop it from the front.
  2. While the value at the back is <= the new value, pop it from the back. Those values are older and smaller, so they can never be the maximum of any future window.
  3. Push i at the back.
  4. Once the first window is complete, the front holds the maximum.
slidingmax.go
Go
package main
 
import "fmt"
 
func maxSlidingWindow(nums []int, k int) []int {
	var dq []int // indexes; nums[dq[0]] > nums[dq[1]] > ...
	var out []int
	for i, x := range nums {
		if len(dq) > 0 && dq[0] <= i-k {
			dq = dq[1:] // the front left the window
		}
		for len(dq) > 0 && nums[dq[len(dq)-1]] <= x {
			dq = dq[:len(dq)-1] // smaller and older: never a max again
		}
		dq = append(dq, i)
		if i >= k-1 {
			out = append(out, nums[dq[0]])
		}
		fmt.Printf("i=%d x=%2d deque values=%v\n", i, x, values(nums, dq))
	}
	return out
}
 
func values(nums, idx []int) []int {
	v := make([]int, len(idx))
	for i, j := range idx {
		v[i] = nums[j]
	}
	return v
}
 
func main() {
	fmt.Println(maxSlidingWindow([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3))
}
Output
i=0 x= 1 deque values=[1]
i=1 x= 3 deque values=[3]
i=2 x=-1 deque values=[3 -1]
i=3 x=-3 deque values=[3 -1 -3]
i=4 x= 5 deque values=[5]
i=5 x= 3 deque values=[5 3]
i=6 x= 6 deque values=[6]
i=7 x= 7 deque values=[7]
[3 3 5 5 6 7]

The deque here is a plain slice used from both ends, which is fine for a single pass. The values printed after each step are always decreasing from front to back.

Shortest subarray with sum at least K, negatives allowed#

The sliding window from the earlier lesson only works with non-negative numbers. With negatives, use prefix sums: a subarray (i, j] has sum pre[j] - pre[i], and we want the shortest one with pre[j] - pre[i] >= K.

Keep a deque of indexes whose prefix values increase from front to back:

  • Front: while pre[j] - pre[front] >= K, record j - front and pop the front. A later j would only make that subarray longer.
  • Back: while pre[back] >= pre[j], pop the back. Index j is newer and has a smaller-or-equal prefix, so it is a strictly better starting point.
shortestk.go
Go
package main
 
import "fmt"
 
func shortestSubarray(nums []int, k int) int {
	pre := make([]int, len(nums)+1)
	for i, n := range nums {
		pre[i+1] = pre[i] + n
	}
	best := len(nums) + 1
	var dq []int
	for j := range pre {
		for len(dq) > 0 && pre[j]-pre[dq[0]] >= k {
			best = min(best, j-dq[0])
			dq = dq[1:]
		}
		for len(dq) > 0 && pre[dq[len(dq)-1]] >= pre[j] {
			dq = dq[:len(dq)-1]
		}
		dq = append(dq, j)
	}
	if best > len(nums) {
		return -1
	}
	return best
}
 
func main() {
	fmt.Println(shortestSubarray([]int{2, -1, 2}, 3)) // the whole slice
	fmt.Println(shortestSubarray([]int{1, 2}, 4))     // impossible
	fmt.Println(shortestSubarray([]int{84, -37, 32, 40, 95}, 167))
}
Output
3
-1
3

The last answer, 3, is [32, 40, 95]. A plain sliding window would get it wrong, because dropping the -37 from the left would make the sum bigger, which breaks the window's "shrinking reduces the sum" assumption.

Recognizing the pattern#

  • "Maximum or minimum of every window of size k": monotonic deque.
  • A DP where dp[i] depends on the max or min of the previous k entries (Jump Game VI, Constrained Subsequence Sum): the same deque turns O(n·k) into O(n).
  • Shortest or longest subarray with a sum condition and negative numbers: prefix sums plus a monotonic deque.
  • BFS where edges cost 0 or 1 (0-1 BFS): push 0-cost neighbors at the front and 1-cost ones at the back of a deque.

Complexity#

OperationTimeSpace
ring buffer push/pop at either endO(1) amortizedO(n)
sliding window maximumO(n)O(k)
shortest subarray with sum ≥ KO(n)O(n)

Summary#

  • A deque supports O(1) adds and removes at both ends; a ring buffer implements it in one slice.
  • A monotonic deque discards elements that can never be the answer again, so each element is pushed and popped at most once.
  • Window max: decreasing values front to back. Shortest subarray with negatives: increasing prefix sums.
  • Store indexes, not values, so you can tell when the front leaves the window.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.A ring buffer stores a queue in a fixed slice. What happens to the head index when you pop from the front?

  2. Q2.In the sliding-window-maximum deque, values from front to back are:

  3. Q3.Why can a smaller element at the back of the deque be thrown away forever when a bigger one arrives?

  4. Q4.Sliding window maximum with a monotonic deque runs in:

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

  • Design Circular Deque ↗medium
    Show hint

    A fixed slice plus head and size; tail is (head + size) % cap.

  • Sliding Window Maximum ↗hard
    Show hint

    Deque of indexes with decreasing values; drop the front when it leaves the window.

  • Shortest Subarray with Sum at Least K ↗hard
    Show hint

    Prefix sums plus a deque of increasing prefix values.

  • Jump Game VI ↗medium
    Show hint

    dp[i] = nums[i] + max(dp[i-k..i-1]); keep that window max in a monotonic deque.

  • Constrained Subsequence Sum ↗hard
    Show hint

    Same deque idea as Jump Game VI, but you may also start fresh.

  • Build a generic Deque[T]build

    Add Deque[T] to your godsa library: PushFront, PushBack, PopFront, PopBack, Front, Back, Len, growing by doubling, with table tests and an All() iterator.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.