Working with arrays and containers

Arrays, containers, and the operations on them.

Arrays

Arrays map to C++ vectors.

a: [int]
b: [[int]]
dist: [long]

Create filled arrays with filled:

freq = filled(n, 0)
dist = filled(n, INF)
dp = filled(n + 1, filled(m + 1, 0))

Sorting and searching

sort(a)
sort(a, desc)
sort_by(a, key = |x| x.second)
best = min_by(a, key = |x| x.cost)
sort(a, |x, y| x.first < y.first)

Search helpers on sorted arrays:

lower(a, x)
upper(a, x)

Common array methods

a.sum()
a.min()
a.max()
a.count(|x| x > 0)
a.any(|x| x < 0)
a.all(|x| x > 0)
a.filter(|x| x > 0)
a.map(|x| x * 2)
a.find(|x| x > 0)
a.push(x)

Free-function forms exist too:

sum(a)
min(a)
max(a)
filter(a, |x| x > 0)
map(a, |x| x * 2)

Comprehensions

sq = [x * x for x in a]
evens = [x for x in a where x % 2 == 0]
indices = [i for i in [0, n) where a[i] > 0]
pairs = [(i, a[i]) for i in [0, n)]

Use comprehensions when they make the new collection clearer than an explicit loop.

Reductions

println max(dp[i] for i in [0, n))
println sum(a[i] * b[i] for i in [0, n))
ans = min(abs(a[i] - a[j]) for i in [0, n) for j in [0, n) where i != j)

Use reductions when you want one value from a collection or range.

Transforming arrays

reverse(a)
fill(a, val)
unique(a)
len(a)
b = a.compress()
flatten(nested)        # flatten one level of nesting
chunk(a, 3)            # split into groups of 3
windows(a, k)          # sliding windows of width k
a.flat_map(|x| ...)    # map then flatten

Sliding window helpers

a.sliding_max(k)
a.sliding_min(k)
a.next_greater()
a.next_smaller()

These return arrays of the same length as a.

Enumerating permutations, subsets, and combinations

Use these in for loops when you need to try every arrangement:

for p in each_perm(a):
    # p is a permutation of a

for mask in each_subset(bits):
    # mask is a submask of bits

for c in each_combo(a, k):
    # c is a k-element combination from a

You can also step through permutations manually:

next_perm(a)    # advance a in place
prev_perm(a)    # go back one step

Container types

algo	C++ shape	Typical use
set[T]	hash set	membership checks
oset[T]	ordered set	ordered membership
map[K, V]	hash map	frequency maps
omap[K, V]	ordered map	ordered key queries
multiset[T]	multiset	duplicates + ordering
pq[T]	max-heap	best-first selection
pq[T, min]	min-heap	Dijkstra / greedy
stack[T]	stack	LIFO
queue[T]	queue	BFS / FIFO
deque[T]	deque	double-ended access

Multiset helpers

s: multiset[int]
s.insert(x)
s.erase_one(x)
s.min()
s.max()
s.count(x)

Priority queues

q: pq[int]
q: pq[int, min]
q: pq[(long, int), min]

Tuples and destructuring

t = (dist[v], v)
(d, u) = t

for (u, v, w) in edges:
    # ...

Type aliases

type Edge = pair[int, int]
type Adj = [[Edge]]

Use aliases when a container or tuple type is repeated enough to hurt readability.