ruby-dsa ruby 4.0

Data structures & algorithms in Ruby

Every example runs real CRuby in your browser. Edit one and hit run — it is yours until you reset it. Ruby downloads on your first run, once, for the page.

Big-O of Ruby's own Array & Hash
push / pop O(1) shift / unshift O(1) a[i] O(1) insert(i, x) O(n) include? O(n) sort O(n log n) h[k] / h[k]= O(1) h.key? O(1)

shift is O(1) because CRuby moves the array's start pointer rather than re-indexing — worth saying out loud, since the same operation is O(n) on a Python list.

IMPLEMENT IT FROM SCRATCH

Singly linked list 1

O(1) insert at the head, O(n) to reach anything else. Rarely the right data structure in Ruby — Array already gives you O(1) at both ends — but a standing interview request, because it is pure pointer discipline.

Singly linked list

time unshift O(1) · push O(n) · delete O(n) space O(n)

Keeping a @tail reference would make push O(1) too; it is left out here so the traversal is visible. Struct gives you the node with no ceremony.

class LinkedList
  include Enumerable

  Node = Struct.new(:value, :next_node)

  def initialize(values = [])
    @head = nil
    values.reverse_each { |v| unshift(v) }
  end

  def unshift(value)
    @head = Node.new(value, @head)
    self
  end

  def push(value)
    return unshift(value) unless @head
    node = @head
    node = node.next_node while node.next_node
    node.next_node = Node.new(value, nil)
    self
  end

  def delete(value)
    return self unless @head
    if @head.value == value
      @head = @head.next_node
      return self
    end
    node = @head
    node = node.next_node while node.next_node && node.next_node.value != value
    node.next_node = node.next_node.next_node if node.next_node
    self
  end

  def each
    return to_enum(:each) unless block_given?
    node = @head
    while node
      yield node.value
      node = node.next_node
    end
  end
end

list = LinkedList.new([2, 3])
list.unshift(1).push(4).delete(3)

p list.to_a
p list.count
p list.include?(3)
p list.map { |v| v * 10 }
expected output
[1, 2, 4]
3
false
[10, 20, 40]
Stack & queue 1

In Ruby both are an Array — push/pop for LIFO, push/shift for FIFO, all O(1). The classic interview twist is building a queue out of two stacks, which is only interesting because the amortised analysis is.

Stack, and a queue from two stacks

time push O(1) · pop O(1) · dequeue amortised O(1) space O(n)

Each element moves between the two stacks at most once, so although a single dequeue can cost O(n), n dequeues cost O(n) in total — amortised O(1). That distinction is usually the whole point of the question.

class Stack
  def initialize = @items = []
  def push(item) = (@items.push(item); self)
  def pop = @items.pop
  def peek = @items.last
  def empty? = @items.empty?
  def size = @items.size
end

class Queue2
  def initialize
    @inbox = []
    @outbox = []
  end

  def enqueue(item) = (@inbox.push(item); self)

  def dequeue
    # Drain the whole inbox, not one element: the transfer must happen at
    # most once per element for the amortised O(1) argument to hold.
    @outbox.push(@inbox.pop) while @inbox.any? if @outbox.empty?
    @outbox.pop
  end

  def size = @inbox.size + @outbox.size
end

stack = Stack.new
stack.push(1).push(2).push(3)
p [stack.pop, stack.peek, stack.size]

queue = Queue2.new
queue.enqueue(:a).enqueue(:b)
p queue.dequeue
queue.enqueue(:c)
p [queue.dequeue, queue.dequeue, queue.dequeue]
expected output
[3, 2, 2]
:a
[:b, :c, nil]
Hash map 1

Bucket array plus a collision strategy. Separate chaining — a list per bucket — is the one to write under time pressure; the interesting follow-up is what happens to the O(1) claim when the load factor climbs.

Hash map with separate chaining

time O(1) average · O(n) worst space O(n)

Average O(1) assumes keys spread evenly across buckets. With every key in one bucket it degrades to a linear scan, which is why real implementations resize once the load factor passes a threshold — mention that even if you do not implement it.

class HashMap
  include Enumerable

  def initialize(bucket_count = 8)
    @buckets = Array.new(bucket_count) { [] }
    @size = 0
  end

  attr_reader :size

  def []=(key, value)
    pair = bucket_for(key).assoc(key)
    if pair
      pair[1] = value
    else
      bucket_for(key) << [key, value]
      @size += 1
    end
    value
  end

  def [](key) = bucket_for(key).assoc(key)&.last

  def key?(key) = !bucket_for(key).assoc(key).nil?

  def delete(key)
    pair = bucket_for(key).assoc(key)
    return nil unless pair
    bucket_for(key).delete(pair)
    @size -= 1
    pair[1]
  end

  def each(&) = @buckets.flatten(1).each(&)

  private

  def bucket_for(key) = @buckets[key.hash.abs % @buckets.size]
end

map = HashMap.new
map["one"] = 1
map["two"] = 2
map["one"] = 11

p [map["one"], map["two"], map["three"]]
p [map.size, map.key?("two")]
p map.delete("two")
p [map.size, map.key?("two")]
p map.sort_by(&:first)
expected output
[11, 2, nil]
[2, true]
2
[1, false]
[["one", 11]]
Binary search tree 1

Left subtree smaller, right subtree larger — an invariant that makes lookup O(h). The catch is that h is only log n while the tree stays balanced, and inserting sorted data degrades it into a linked list.

Binary search tree

time O(log n) balanced · O(n) degenerate space O(n)

In-order traversal yields sorted values, which is the property most BST questions rest on. Insert 1, 2, 3, 4 in order and every node has only a right child: height n, lookup O(n). That is what AVL and red-black trees exist to fix.

class BST
  include Enumerable

  Node = Struct.new(:value, :left, :right)

  def initialize(values = [])
    @root = nil
    values.each { |v| insert(v) }
  end

  def insert(value)
    @root = insert_below(@root, value)
    self
  end

  def include?(value)
    node = @root
    while node
      return true if value == node.value
      node = value < node.value ? node.left : node.right
    end
    false
  end

  def min = leftmost(@root)&.value

  def height(node = @root)
    node ? 1 + [height(node.left), height(node.right)].max : 0
  end

  def each(node = @root, &block)
    return to_enum(:each) unless block
    return unless node
    each(node.left, &block)
    block.call(node.value)
    each(node.right, &block)
  end

  private

  def insert_below(node, value)
    return Node.new(value, nil, nil) unless node
    if value < node.value
      node.left = insert_below(node.left, value)
    elsif value > node.value
      node.right = insert_below(node.right, value)
    end
    node
  end

  def leftmost(node)
    node = node.left while node&.left
    node
  end
end

balanced = BST.new([5, 3, 8, 1, 4, 7, 9])
p balanced.to_a
p [balanced.include?(4), balanced.include?(6)]
p [balanced.min, balanced.height]

degenerate = BST.new([1, 2, 3, 4])
p [degenerate.to_a, degenerate.height]
expected output
[1, 3, 4, 5, 7, 8, 9]
[true, false]
[1, 3]
[[1, 2, 3, 4], 4]
Min-heap 1

A complete binary tree flattened into an array, where every parent is no larger than its children. Ruby ships no heap, so this is worth being able to write — and it is the engine behind every priority queue and Dijkstra implementation.

Min-heap / priority queue

time push O(log n) · pop O(log n) · peek O(1) space O(n)

The array encoding is the whole trick: children of i live at 2i + 1 and 2i + 2, parent at (i - 1) / 2. No node objects, no pointers — push appends then sifts up, pop swaps the last element to the root then sifts down.

class MinHeap
  def initialize(items = [])
    @items = []
    items.each { |item| push(item) }
  end

  def size = @items.size
  def empty? = @items.empty?
  def peek = @items.first

  def push(item)
    @items << item
    sift_up(@items.size - 1)
    self
  end

  def pop
    return nil if @items.empty?
    smallest = @items.first
    last = @items.pop
    unless @items.empty?
      @items[0] = last
      sift_down(0)
    end
    smallest
  end

  private

  def sift_up(index)
    while index.positive?
      parent = (index - 1) / 2
      break if @items[parent] <= @items[index]
      @items[parent], @items[index] = @items[index], @items[parent]
      index = parent
    end
  end

  def sift_down(index)
    loop do
      left = 2 * index + 1
      right = left + 1
      smallest = index
      smallest = left  if left  < @items.size && @items[left]  < @items[smallest]
      smallest = right if right < @items.size && @items[right] < @items[smallest]
      break if smallest == index
      @items[index], @items[smallest] = @items[smallest], @items[index]
      index = smallest
    end
  end
end

heap = MinHeap.new([5, 3, 8, 1, 9, 2])
p heap.peek
p Array.new(heap.size) { heap.pop }
p heap.pop
expected output
1
[1, 2, 3, 5, 8, 9]
nil
Union-find 1

Disjoint sets with two operations: which group is x in, and merge these two groups. The answer to "are these connected?" and "does adding this edge make a cycle?" — and it is far simpler than the graph traversal people reach for first.

Union-find with path compression

time near O(1) amortised space O(n)

Two optimisations do the work. Path compression flattens each chain during find; union by rank keeps the shallower tree underneath. Together they give the inverse-Ackermann bound — effectively constant, and safe to call O(1).

class UnionFind
  def initialize(size)
    @parent = (0...size).to_a
    @rank = Array.new(size, 0)
    @groups = size
  end

  attr_reader :groups

  def find(x)
    @parent[x] = find(@parent[x]) unless @parent[x] == x
    @parent[x]
  end

  def union(a, b)
    root_a, root_b = find(a), find(b)
    return false if root_a == root_b

    root_a, root_b = root_b, root_a if @rank[root_a] < @rank[root_b]
    @parent[root_b] = root_a
    @rank[root_a] += 1 if @rank[root_a] == @rank[root_b]
    @groups -= 1
    true
  end

  def connected?(a, b) = find(a) == find(b)
end

uf = UnionFind.new(6)
[[0, 1], [1, 2], [3, 4]].each { |a, b| uf.union(a, b) }

p [uf.connected?(0, 2), uf.connected?(0, 3)]
p uf.groups
p uf.union(0, 2)
p uf.union(2, 4)
p uf.groups
expected output
[true, false]
3
false
true
2
LRU cache 1

Fixed capacity, evict whatever was used longest ago, every operation O(1). The textbook answer is a hash plus a doubly linked list — in Ruby, Hash is already insertion-ordered, which does most of the job for you.

LRU cache

time O(1) get and put space O(capacity)

delete then re-insert moves a key to the end, because Ruby Hashes preserve insertion order — so the oldest entry is always first. Worth saying that the language-agnostic answer is a hash of nodes in a doubly linked list, and that this relies on a guarantee Ruby happens to make.

class LRUCache
  def initialize(capacity)
    @capacity = capacity
    @store = {}
  end

  def get(key)
    return nil unless @store.key?(key)
    @store[key] = @store.delete(key)
  end

  def put(key, value)
    @store.delete(key)
    @store[key] = value
    @store.delete(@store.first.first) while @store.size > @capacity
    self
  end

  def keys = @store.keys
end

cache = LRUCache.new(2)
cache.put(:a, 1).put(:b, 2)
p cache.get(:a)
cache.put(:c, 3)
p cache.get(:b)
p cache.keys
p cache.get(:a)
expected output
1
nil
[:a, :c]
1
Dynamic array 1

What Ruby's Array is underneath: a fixed block of memory, plus a rule for what to do when it fills up. Doubling the capacity is what makes push amortised O(1) rather than O(n) — and that argument is the reason this gets asked.

Growable array with capacity doubling

time push amortised O(1) · index O(1) space O(n)

Doubling means n pushes cost 1 + 2 + 4 + ... + n copies, which sums to under 2n — so the average push is constant even though individual pushes are O(n). Growing by a fixed amount instead would make it O(n^2) overall.

class DynamicArray
  include Enumerable

  def initialize
    @capacity = 1
    @store = Array.new(@capacity)
    @size = 0
  end

  attr_reader :size, :capacity

  def [](index) = index.between?(0, @size - 1) ? @store[index] : nil

  def push(value)
    resize(@capacity * 2) if @size == @capacity
    @store[@size] = value
    @size += 1
    self
  end

  def pop
    return nil if @size.zero?
    @size -= 1
    value = @store[@size]
    @store[@size] = nil
    value
  end

  def each
    return to_enum(:each) unless block_given?
    @size.times { |i| yield @store[i] }
  end

  private

  def resize(new_capacity)
    bigger = Array.new(new_capacity)
    @size.times { |i| bigger[i] = @store[i] }
    @store = bigger
    @capacity = new_capacity
  end
end

array = DynamicArray.new
growth = (1..16).map { |n| array.push(n).capacity }

p growth.uniq
p [array.size, array.capacity]
p [array[0], array[15], array[16]]
p array.pop
p array.select(&:even?).first(4)
expected output
[1, 2, 4, 8, 16]
[16, 16]
[1, 16, nil]
16
[2, 4, 6, 8]
Doubly linked list 1

A back-pointer on every node. That buys O(1) removal of a node you already hold — which is exactly what a singly linked list cannot do, and exactly what an LRU cache needs.

Doubly linked list with O(1) ends

time push/unshift/pop/shift O(1) · remove a held node O(1) space O(n)

Sentinel head and tail nodes remove every nil check: any real node always has both neighbours, so insert and remove are unconditional pointer swaps. That trick is worth more than the data structure itself.

class DoublyLinkedList
  include Enumerable

  Node = Struct.new(:value, :prev_node, :next_node)

  def initialize(values = [])
    @head = Node.new(:head, nil, nil)
    @tail = Node.new(:tail, @head, nil)
    @head.next_node = @tail
    @size = 0
    values.each { |v| push(v) }
  end

  attr_reader :size

  def push(value) = insert_before(@tail, value)
  def unshift(value) = insert_before(@head.next_node, value)

  def pop = remove(@tail.prev_node)
  def shift = remove(@head.next_node)

  def insert_before(node, value)
    fresh = Node.new(value, node.prev_node, node)
    node.prev_node.next_node = fresh
    node.prev_node = fresh
    @size += 1
    fresh
  end

  def remove(node)
    return nil if node.equal?(@head) || node.equal?(@tail)
    node.prev_node.next_node = node.next_node
    node.next_node.prev_node = node.prev_node
    @size -= 1
    node.value
  end

  def each
    return to_enum(:each) unless block_given?
    node = @head.next_node
    until node.equal?(@tail)
      yield node.value
      node = node.next_node
    end
  end

  def reverse_to_a
    [].tap do |out|
      node = @tail.prev_node
      until node.equal?(@head)
        out << node.value
        node = node.prev_node
      end
    end
  end
end

list = DoublyLinkedList.new([2, 3, 4])
list.unshift(1)
held = list.push(5)

p list.to_a
p list.reverse_to_a

# The point of the back-pointer: removing a node you already hold costs O(1),
# with no traversal to find its predecessor.
p list.remove(held)
p [list.shift, list.pop, list.size]
p list.to_a
expected output
[1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]
5
[1, 4, 2]
[2, 3]
Ring-buffer deque 1

A fixed array where the indices wrap. Constant time at both ends with no allocation and no pointer chasing — which is why it backs bounded queues, audio buffers and sliding windows over streams.

Circular buffer with wrap-around indices

time push/pop at either end O(1) space O(capacity)

Modulo arithmetic does all the work: (head - 1) % capacity wraps to the end of the array without a branch. Ruby's % always returns a non-negative result for a positive divisor, so -1 % 5 is 4 — in C or Java that would be -1 and you would need the extra + capacity.

class RingBuffer
  include Enumerable

  def initialize(capacity)
    @store = Array.new(capacity)
    @capacity = capacity
    @head = 0
    @size = 0
  end

  attr_reader :size, :capacity

  def full? = @size == @capacity
  def empty? = @size.zero?

  def push(value)
    raise "buffer full" if full?
    @store[(@head + @size) % @capacity] = value
    @size += 1
    self
  end

  def unshift(value)
    raise "buffer full" if full?
    @head = (@head - 1) % @capacity
    @store[@head] = value
    @size += 1
    self
  end

  def shift
    return nil if empty?
    value = @store[@head]
    @store[@head] = nil
    @head = (@head + 1) % @capacity
    @size -= 1
    value
  end

  def pop
    return nil if empty?
    index = (@head + @size - 1) % @capacity
    value = @store[index]
    @store[index] = nil
    @size -= 1
    value
  end

  def each
    return to_enum(:each) unless block_given?
    @size.times { |i| yield @store[(@head + i) % @capacity] }
  end
end

p(-1 % 5)

ring = RingBuffer.new(4)
ring.push(2).push(3)
ring.unshift(1)

p [ring.to_a, ring.size, ring.full?]
p [ring.shift, ring.pop]
p ring.to_a

ring.push(9).push(10).push(11)
p [ring.to_a, ring.full?]
p(begin; ring.push(12); rescue => e; e.message; end)
expected output
4
[[1, 2, 3], 3, false]
[1, 3]
[2]
[[2, 9, 10, 11], true]
"buffer full"
Trie (class-based) 1

The same prefix tree as the pattern section, written as a proper object with deletion. Deletion is the part people skip, and the part that is actually fiddly: you must prune back up the branch without cutting off another word.

Trie with insert, search and delete

time O(len) per operation space O(total characters)

Delete recurses down, unmarks the terminal, then prunes each node on the way back up only if it has no children and is not itself the end of a shorter word. Return whether the child is now prunable and the parent decides — that is what keeps "app" alive when you delete "apple".

class Trie
  Node = Struct.new(:children, :terminal) do
    def self.empty = new({}, false)
    def prunable? = children.empty? && !terminal
  end

  def initialize(words = [])
    @root = Node.empty
    words.each { |w| insert(w) }
  end

  def insert(word)
    node = word.each_char.reduce(@root) { |n, c| n.children[c] ||= Node.empty }
    node.terminal = true
    self
  end

  def include?(word) = !!node_at(word)&.terminal

  def prefix?(prefix) = !node_at(prefix).nil?

  def words_with_prefix(prefix)
    start = node_at(prefix)
    return [] unless start
    collect(start, prefix)
  end

  def delete(word)
    prune(@root, word, 0)
    self
  end

  private

  def node_at(string)
    string.each_char.reduce(@root) { |node, c| node && node.children[c] }
  end

  def collect(node, prefix, out = [])
    out << prefix if node.terminal
    node.children.each { |c, child| collect(child, prefix + c, out) }
    out
  end

  # Returns true when the caller should drop this node from its children.
  def prune(node, word, index)
    if index == word.size
      node.terminal = false
    else
      child = node.children[word[index]]
      return false unless child
      node.children.delete(word[index]) if prune(child, word, index + 1)
    end
    node.prunable?
  end
end

trie = Trie.new(%w[app apple apply apt banana])

p trie.words_with_prefix("app")
p [trie.include?("app"), trie.include?("appl")]
p trie.prefix?("ban")

trie.delete("apple")
p trie.words_with_prefix("app")
p trie.include?("app")

trie.delete("banana")
p trie.prefix?("ban")
expected output
["app", "apple", "apply"]
[true, false]
true
["app", "apply"]
true
false
Graph representations 1

Adjacency list, adjacency matrix, or edge list. The choice is a trade between "list my neighbours" and "is there an edge between these two", and picking the wrong one is how an O(V + E) traversal quietly becomes O(V^2).

Adjacency list, matrix and edge list

time see notes space O(V + E) list · O(V^2) matrix

Adjacency list: neighbours in O(degree), edge lookup O(degree), space O(V + E). Matrix: edge lookup O(1), but neighbours cost O(V) and space is O(V^2) even for a sparse graph. Use a list by default; reach for a matrix when the graph is dense or you are constantly asking whether a specific edge exists.

EDGES = [%w[a b], %w[a c], %w[b d], %w[c d], %w[d e]].freeze
NODES = EDGES.flatten.uniq.sort.freeze

def adjacency_list(edges)
  edges.each_with_object(Hash.new { |h, k| h[k] = [] }) do |(from, to), list|
    list[from] << to
    list[to] << from
  end
end

def adjacency_matrix(nodes, edges)
  index = nodes.each_with_index.to_h
  matrix = Array.new(nodes.size) { Array.new(nodes.size, 0) }
  edges.each do |from, to|
    matrix[index[from]][index[to]] = 1
    matrix[index[to]][index[from]] = 1
  end
  matrix
end

list = adjacency_list(EDGES)
matrix = adjacency_matrix(NODES, EDGES)

p NODES
p list["d"].sort
p matrix

# Same traversal, either representation.
def bfs(start, neighbours)
  seen = { start => true }
  queue = [start]
  order = []
  until queue.empty?
    node = queue.shift
    order << node
    neighbours.call(node).each do |nxt|
      next if seen[nxt]
      seen[nxt] = true
      queue << nxt
    end
  end
  order
end

p bfs("a", ->(n) { list[n].sort })
expected output
["a", "b", "c", "d", "e"]
["b", "c", "e"]
[[0, 1, 1, 0, 0], [1, 0, 0, 1, 0], [1, 0, 0, 1, 0], [0, 1, 1, 0, 1], [0, 0, 0, 1, 0]]
["a", "b", "c", "d", "e"]
Fenwick / segment tree 1

Prefix sums that survive updates. A plain prefix-sum array answers range queries in O(1) but costs O(n) to update; a Fenwick tree makes both O(log n), which is the trade you want when the data keeps changing.

Fenwick tree (binary indexed tree)

time update O(log n) · prefix sum O(log n) space O(n)

index & -index isolates the lowest set bit, and that value is how many elements the slot covers. Adding it walks up the update path, subtracting it walks down the query path — which is the whole algorithm, in two loops of three lines. One-based indexing is not optional: index 0 would loop forever.

class FenwickTree
  def initialize(values = [])
    @tree = Array.new(values.size + 1, 0)
    @size = values.size
    values.each_with_index { |v, i| add(i, v) }
  end

  # Add delta to the value at zero-based position i.
  def add(i, delta)
    index = i + 1
    while index <= @size
      @tree[index] += delta
      index += index & -index
    end
    self
  end

  # Sum of the first i elements, zero-based exclusive: prefix_sum(3) is 0..2.
  def prefix_sum(i)
    index = i
    total = 0
    while index.positive?
      total += @tree[index]
      index -= index & -index
    end
    total
  end

  def range_sum(from, to) = prefix_sum(to + 1) - prefix_sum(from)
end

p [6 & -6, 8 & -8, 5 & -5]

values = [1, 2, 3, 4, 5, 6, 7, 8]
tree = FenwickTree.new(values)

p tree.prefix_sum(4)
p tree.range_sum(2, 5)
p values.sum

tree.add(2, 10)
p tree.range_sum(2, 5)
p tree.range_sum(0, 7)
expected output
[2, 8, 1]
10
18
36
28
46

PATTERNS

Arrays & hashing 4

The workhorse. A Hash turns "have I seen this before?" from a scan into a lookup, which is what collapses most brute-force O(n^2) pair problems to O(n). Reach for it before anything cleverer.

Two sum

time O(n) space O(n)

One pass. Store each value's index as you go and ask whether the complement has already been seen — so the pair is found before you reach its second half.

def two_sum(nums, target)
  seen = {}
  nums.each_with_index do |n, i|
    j = seen[target - n]
    return [j, i] if j
    seen[n] = i
  end
  []
end

p two_sum([2, 7, 11, 15], 9)
p two_sum([3, 2, 4], 6)
p two_sum([1, 2], 50)
expected output
[0, 1]
[1, 2]
[]

Group anagrams

time O(n · k log k) space O(n · k)

Sorted letters make a canonical key. Hash.new { |h, k| h[k] = [] } gives an auto-vivifying Hash, which is the idiomatic Ruby way to bucket without a guard clause on every insert.

def group_anagrams(words)
  buckets = Hash.new { |h, k| h[k] = [] }
  words.each { |w| buckets[w.chars.sort.join] << w }
  buckets.values
end

p group_anagrams(%w[eat tea tan ate nat bat])
expected output
[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Longest consecutive sequence

time O(n) space O(n)

Sorting makes this trivial and O(n log n); the O(n) answer is a Set plus one rule — only start counting from a number whose predecessor is absent. That guarantees each run is walked exactly once, so the nested loop is still linear.

require "set"

def longest_consecutive(nums)
  pool = nums.to_set
  best = 0

  pool.each do |n|
    next if pool.include?(n - 1) # not the start of a run

    length = 1
    length += 1 while pool.include?(n + length)
    best = [best, length].max
  end

  best
end

p longest_consecutive([100, 4, 200, 1, 3, 2])
p longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])
p longest_consecutive([])
expected output
4
9
0

Product of array except self

time O(n) space O(1) excluding output

Division is the obvious answer and the forbidden one — it breaks on a zero. Two sweeps instead: one accumulating the product of everything to the left, one coming back for everything to the right.

def product_except_self(nums)
  out = Array.new(nums.size, 1)

  running = 1
  nums.each_index do |i|
    out[i] = running
    running *= nums[i]
  end

  running = 1
  nums.each_index.reverse_each do |i|
    out[i] *= running
    running *= nums[i]
  end

  out
end

p product_except_self([1, 2, 3, 4])
p product_except_self([-1, 1, 0, -3, 3])
p product_except_self([2, 3])
expected output
[24, 12, 8, 6]
[0, 0, 9, 0, 0]
[3, 2]
Sliding window 3

A contiguous range with two moving edges. Grow the right edge to satisfy the goal, advance the left edge to restore the invariant — and because each edge only ever moves forward, the whole scan is O(n) despite the nested look.

Longest substring without repeating characters

time O(n) space O(min(n, alphabet))

Storing the last index of each character lets the left edge jump straight past the previous occurrence instead of crawling one step at a time.

def length_of_longest_substring(s)
  last_seen = {}
  left = 0
  best = 0

  s.each_char.with_index do |c, right|
    left = last_seen[c] + 1 if last_seen[c] && last_seen[c] >= left
    last_seen[c] = right
    best = [best, right - left + 1].max
  end

  best
end

p length_of_longest_substring("abcabcbb")
p length_of_longest_substring("bbbbb")
p length_of_longest_substring("pwwkew")
p length_of_longest_substring("")
expected output
3
1
3
0

Maximum sum of a fixed-size window

time O(n) space O(1)

When the window size is fixed there is nothing to decide: add the entering element, subtract the leaving one. Recomputing each window from scratch is the O(n·k) mistake this exists to avoid.

def max_window_sum(nums, k)
  return nil if k > nums.size || k <= 0

  window = nums.first(k).sum
  best = window

  (k...nums.size).each do |i|
    window += nums[i] - nums[i - k]
    best = [best, window].max
  end

  best
end

p max_window_sum([2, 1, 5, 1, 3, 2], 3)
p max_window_sum([2, 3], 2)
p max_window_sum([1], 5)
expected output
9
5
nil

Minimum window substring

time O(n + m) space O(alphabet)

The two-counter trick: missing tracks how many required characters are still outstanding, so checking whether the window is valid is an integer comparison rather than a walk over the tally. Only shrink once the window is valid.

def min_window(s, target)
  return "" if target.empty? || s.size < target.size

  need = target.chars.tally
  missing = target.size
  best = nil
  left = 0

  s.each_char.with_index do |c, right|
    missing -= 1 if need.key?(c) && need[c] > 0
    need[c] = need.fetch(c, 0) - 1

    next unless missing.zero?

    # Pull the left edge in while the window stays valid.
    while need[s[left]] < 0
      need[s[left]] += 1
      left += 1
    end

    best = [left, right] if best.nil? || (right - left) < (best[1] - best[0])
  end

  best ? s[best[0]..best[1]] : ""
end

p min_window("ADOBECODEBANC", "ABC")
p min_window("a", "aa")
p min_window("ab", "b")
expected output
"BANC"
""
"b"
Stack 3

Whenever the answer depends on the most recent unresolved thing — a bracket, a smaller value, a pending operator — that is a stack. In Ruby an Array is one already: push and pop are both O(1).

Valid parentheses

time O(n) space O(n)

Push the *expected closer* rather than the opener, so the check is a single equality instead of a second lookup table at pop time.

def valid_parentheses?(s)
  closers = { "(" => ")", "[" => "]", "{" => "}" }
  stack = []

  s.each_char do |c|
    if closers.key?(c)
      stack.push(closers[c])
    elsif stack.pop != c
      return false
    end
  end

  stack.empty?
end

p valid_parentheses?("()[]{}")
p valid_parentheses?("(]")
p valid_parentheses?("([)]")
p valid_parentheses?("(")
expected output
true
false
false
false

Daily temperatures (monotonic stack)

time O(n) space O(n)

The stack holds indices whose answer is still unknown, kept in decreasing temperature order. Each index is pushed and popped at most once, so the nested while loop is still linear overall.

def daily_temperatures(temps)
  answer = Array.new(temps.size, 0)
  pending = []

  temps.each_with_index do |t, i|
    while pending.any? && temps[pending.last] < t
      j = pending.pop
      answer[j] = i - j
    end
    pending.push(i)
  end

  answer
end

p daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73])
p daily_temperatures([30, 40, 50, 60])
expected output
[1, 1, 4, 2, 1, 1, 0, 0]
[1, 1, 1, 0]

Min stack

time O(1) for every operation space O(n)

Scanning for the minimum on demand is O(n); instead push the minimum *so far* alongside each value. Because a pop restores the previous entry, the answer to "what is the minimum now?" is always sitting on top.

class MinStack
  def initialize = @entries = []

  def push(value)
    @entries.push([value, @entries.empty? ? value : [value, min].min])
    self
  end

  def pop = @entries.pop&.first
  def top = @entries.last&.first
  def min = @entries.last&.last
  def empty? = @entries.empty?
end

stack = MinStack.new
stack.push(5).push(2).push(7).push(1)

p [stack.top, stack.min]
p stack.pop
p [stack.top, stack.min]
p stack.pop
p [stack.top, stack.min]
p MinStack.new.min
expected output
[1, 1]
1
[7, 2]
7
[2, 2]
nil
Linked list 3

Almost every linked-list question is pointer bookkeeping: reverse it, find the middle, detect a cycle, merge two. Draw the three-pointer shuffle once and the rest follow.

Reverse a list, and detect a cycle

time O(n) space O(1)

Reversal is the classic prev/curr/next shuffle. Floyd's tortoise-and-hare detects a cycle in constant space: if a loop exists the fast pointer laps the slow one, and if it does not, the fast pointer simply runs off the end.

Node = Struct.new(:value, :next_node)

def build(values)
  values.reverse.reduce(nil) { |tail, v| Node.new(v, tail) }
end

def to_a(head)
  [].tap { |out| while head; out << head.value; head = head.next_node; end }
end

def reverse(head)
  prev = nil
  while head
    head.next_node, prev, head = prev, head, head.next_node
  end
  prev
end

def cycle?(head)
  slow = fast = head
  while fast&.next_node
    slow = slow.next_node
    fast = fast.next_node.next_node
    return true if slow.equal?(fast)
  end
  false
end

list = build([1, 2, 3, 4, 5])
p to_a(reverse(list))

looped = build([1, 2, 3])
p cycle?(looped)
looped.next_node.next_node.next_node = looped
p cycle?(looped)
expected output
[5, 4, 3, 2, 1]
false
true

Merge two sorted lists

time O(n + m) space O(1)

A dummy head removes the "is this the first node?" branch entirely — you always append to tail, and return dummy.next_node at the end. The same trick cleans up almost every list-building problem.

Node = Struct.new(:value, :next_node)

def build(values) = values.reverse.reduce(nil) { |tail, v| Node.new(v, tail) }
def to_a(head) = [].tap { |o| while head; o << head.value; head = head.next_node; end }

def merge(a, b)
  dummy = Node.new(nil, nil)
  tail = dummy

  while a && b
    if a.value <= b.value
      tail.next_node, a = a, a.next_node
    else
      tail.next_node, b = b, b.next_node
    end
    tail = tail.next_node
  end

  tail.next_node = a || b
  dummy.next_node
end

p to_a(merge(build([1, 3, 5]), build([2, 4, 6])))
p to_a(merge(build([]), build([1])))
p to_a(merge(build([1, 2]), build([])))
expected output
[1, 2, 3, 4, 5, 6]
[1]
[1, 2]

Find the middle, and remove the nth from the end

time O(n) space O(1)

Both are two pointers separated by a gap. For the middle, the fast pointer moves twice as fast; for the nth from the end, it starts n nodes ahead. Neither needs a length pass, which is the point.

Node = Struct.new(:value, :next_node)

def build(values) = values.reverse.reduce(nil) { |tail, v| Node.new(v, tail) }
def to_a(head) = [].tap { |o| while head; o << head.value; head = head.next_node; end }

def middle(head)
  slow = fast = head
  while fast&.next_node
    slow = slow.next_node
    fast = fast.next_node.next_node
  end
  slow&.value
end

def remove_nth_from_end(head, n)
  dummy = Node.new(nil, head)
  lead = trail = dummy
  n.times { lead = lead&.next_node }
  return head unless lead

  while lead.next_node
    lead = lead.next_node
    trail = trail.next_node
  end

  trail.next_node = trail.next_node.next_node
  dummy.next_node
end

p middle(build([1, 2, 3, 4, 5]))
p middle(build([1, 2, 3, 4]))
p to_a(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2))
p to_a(remove_nth_from_end(build([1]), 1))
expected output
3
3
[1, 2, 3, 5]
[]
Trees 3

Recursion is the natural shape: solve for the children, combine. Reach for an explicit queue only when the question is genuinely about levels — breadth-first order is the one thing recursion does not give you for free.

Traversals, depth, and level order

time O(n) space O(h) recursive, O(w) for BFS

In-order on a BST yields sorted values, which is the property most BST questions hinge on. Level order needs a queue — and taking queue.size before the inner loop is what keeps each level separate.

Tree = Struct.new(:value, :left, :right)

def leaf(v) = Tree.new(v, nil, nil)

root = Tree.new(4,
  Tree.new(2, leaf(1), leaf(3)),
  Tree.new(7, leaf(6), leaf(9)))

def in_order(node, out = [])
  return out unless node
  in_order(node.left, out)
  out << node.value
  in_order(node.right, out)
end

def depth(node)
  node ? 1 + [depth(node.left), depth(node.right)].max : 0
end

def level_order(root)
  levels = []
  queue = [root].compact

  until queue.empty?
    levels << queue.map(&:value)
    queue = queue.flat_map { |n| [n.left, n.right] }.compact
  end

  levels
end

p in_order(root)
p depth(root)
p level_order(root)
p level_order(nil)
expected output
[1, 2, 3, 4, 6, 7, 9]
3
[[4], [2, 7], [1, 3, 6, 9]]
[]

Validate a binary search tree

time O(n) space O(h)

Checking each node against only its immediate children is the classic wrong answer — it accepts a node deeper in the left subtree that is larger than the root. Carry a (low, high) bound down instead, narrowing it at each step.

Tree = Struct.new(:value, :left, :right)
def leaf(v) = Tree.new(v, nil, nil)

def valid_bst?(node, low = nil, high = nil)
  return true unless node
  return false if low && node.value <= low
  return false if high && node.value >= high

  valid_bst?(node.left, low, node.value) &&
    valid_bst?(node.right, node.value, high)
end

good = Tree.new(5, Tree.new(3, leaf(1), leaf(4)), Tree.new(8, leaf(7), leaf(9)))

# 6 is larger than the root, but sits in the left subtree — a local check misses it.
sneaky = Tree.new(5, Tree.new(3, leaf(1), leaf(6)), leaf(8))

p valid_bst?(good)
p valid_bst?(sneaky)
p valid_bst?(nil)
expected output
true
false
true

Invert a tree, and find a lowest common ancestor

time O(n) space O(h)

Inverting is a two-line post-order swap. LCA on a *search* tree is easier than the general case: walk down while both targets sit on the same side, and the first node that splits them is the answer.

Tree = Struct.new(:value, :left, :right)
def leaf(v) = Tree.new(v, nil, nil)

def invert(node)
  return nil unless node
  node.left, node.right = invert(node.right), invert(node.left)
  node
end

def in_order(node, out = [])
  return out unless node
  in_order(node.left, out)
  out << node.value
  in_order(node.right, out)
end

def lca(node, a, b)
  low, high = [a, b].minmax
  while node
    return node.value if node.value.between?(low, high)
    node = node.value > high ? node.left : node.right
  end
  nil
end

tree = Tree.new(5, Tree.new(3, leaf(1), leaf(4)), Tree.new(8, leaf(7), leaf(9)))

p lca(tree, 1, 4)
p lca(tree, 1, 9)
p lca(tree, 7, 9)

p in_order(invert(tree))
expected output
3
5
8
[9, 8, 7, 5, 4, 3, 1]
Tries 3

A tree keyed by character. Lookup costs the length of the word rather than the size of the dictionary, and — unlike a Hash of whole words — it answers prefix questions, which is the only reason to prefer one.

Prefix tree with a nested Hash

time O(len) per operation space O(total characters)

A trie is just nested Hashes. An auto-vivifying default block builds the path as you walk it, so insert is a reduce; a sentinel key marks a complete word, which is what distinguishes search from starts_with?.

TERMINAL = :end

def build_trie(words)
  root = {}
  words.each do |word|
    node = word.each_char.reduce(root) { |n, c| n[c] ||= {} }
    node[TERMINAL] = true
  end
  root
end

def walk(root, prefix)
  prefix.each_char.reduce(root) { |node, c| node && node[c] }
end

def search(root, word) = !!walk(root, word)&.key?(TERMINAL)
def starts_with?(root, prefix) = !walk(root, prefix).nil?

trie = build_trie(%w[apple app apply])

p search(trie, "app")
p search(trie, "appl")
p starts_with?(trie, "appl")
p starts_with?(trie, "banana")
expected output
true
false
true
false

Longest common prefix

time O(total characters) space O(1) for the idiomatic version

A trie is the textbook answer — walk down while each node has exactly one child and no word ends. But for one query, comparing the lexicographic min and max is enough: every other string lies between them, so their shared prefix is shared by all.

def longest_common_prefix(words)
  return "" if words.empty?

  first, last = words.minmax
  length = first.each_char.zip(last.each_char).take_while { |a, b| a == b }.size
  first[0, length]
end

p longest_common_prefix(%w[flower flow flight])
p longest_common_prefix(%w[dog racecar car])
p longest_common_prefix(%w[interspecies interstellar interstate])
p longest_common_prefix([])
p longest_common_prefix(%w[alone])
expected output
"fl"
""
"inters"
""
"alone"

Replace words with their shortest root

time O(total characters) space O(roots)

The canonical use of a trie: walk each word down the tree and stop at the first node marking a complete root. A Hash of roots would need you to try every prefix length separately; the trie finds the shortest in one descent.

TERMINAL = :end

def build_trie(roots)
  roots.each_with_object({}) do |root, trie|
    node = root.each_char.reduce(trie) { |n, c| n[c] ||= {} }
    node[TERMINAL] = true
  end
end

def shortest_root(trie, word)
  node = trie
  word.each_char.with_index do |c, i|
    node = node[c]
    return nil unless node
    return word[0..i] if node[TERMINAL]
  end
  nil
end

def replace_words(roots, sentence)
  trie = build_trie(roots)
  sentence.split.map { |w| shortest_root(trie, w) || w }.join(" ")
end

p replace_words(%w[cat bat rat], "the cattle was rattled by the battery")
p replace_words(%w[a aa aaa], "a aa aaa aaaa")
p replace_words([], "nothing changes here")
expected output
"the cat was rat by the bat"
"a a a a"
"nothing changes here"
Heap / priority queue 3

When you need the smallest or largest thing repeatedly but not a full ordering, a heap gives you O(log n) insert and extract instead of re-sorting. Ruby has no built-in heap — know that, and know when sorting is simply good enough.

Top K frequent elements

time O(n log n) sorting, O(n) by bucket space O(n)

tally counts in one pass. Sorting the distinct values is O(d log d) and almost always fine; bucketing by frequency is the O(n) answer an interviewer is fishing for, since a count can never exceed n.

def top_k_sorted(nums, k)
  nums.tally.max_by(k) { |_value, count| count }.map(&:first)
end

def top_k_bucketed(nums, k)
  buckets = Array.new(nums.size + 1) { [] }
  nums.tally.each { |value, count| buckets[count] << value }
  buckets.compact.flatten.last(k).reverse
end

p top_k_sorted([1, 1, 1, 2, 2, 3], 2)
p top_k_bucketed([1, 1, 1, 2, 2, 3], 2)
p top_k_sorted([4], 1)
expected output
[1, 2]
[1, 2]
[4]

Kth largest element

time O(n log k) with a heap of size k space O(k)

Sorting everything is O(n log n); keeping only the k largest seen so far is O(n log k), which matters when k is small and n is not. Ruby's max_by(k) does exactly that internally, so reach for it and say why.

def kth_largest(nums, k)
  nums.max(k).last
end

def kth_largest_manual(nums, k)
  keep = []
  nums.each do |n|
    keep << n
    keep.sort!
    keep.shift if keep.size > k
  end
  keep.first
end

p kth_largest([3, 2, 1, 5, 6, 4], 2)
p kth_largest_manual([3, 2, 1, 5, 6, 4], 2)
p kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)
p kth_largest([1], 1)
expected output
5
5
4
1

Merge k sorted arrays

time O(n log k) space O(k)

The heap holds one candidate per list — k items, not n — so each of the n extractions costs log k rather than log n. Concatenating and sorting is O(n log n) and perfectly reasonable in practice; know both, and know which one you were asked for.

def merge_sorted(lists)
  cursors = lists.map { |list| [list, 0] }
  out = []

  loop do
    live = cursors.reject { |list, i| i >= list.size }
    break if live.empty?

    winner = live.min_by { |list, i| list[i] }
    out << winner[0][winner[1]]
    winner[1] += 1
  end

  out
end

p merge_sorted([[1, 4, 5], [1, 3, 4], [2, 6]])
p merge_sorted([[], [1]])
p merge_sorted([])
p [[1, 4, 5], [1, 3, 4], [2, 6]].flatten.sort
expected output
[1, 1, 2, 3, 4, 4, 5, 6]
[1]
[]
[1, 1, 2, 3, 4, 4, 5, 6]
Backtracking 3

Build a candidate one choice at a time, abandon it the moment it cannot work, and undo the choice on the way out. The undo is the whole pattern — forget it and every branch inherits the last one's state.

Subsets and permutations

time O(n · 2^n) and O(n · n!) space O(n) excluding output

Note the pop after each recursive call — that is the "back" in backtracking. Ruby's Array#combination and #permutation do both for you, which is worth saying before you write the recursion by hand.

def subsets(nums)
  out = []
  walk = lambda do |start, current|
    out << current.dup
    (start...nums.size).each do |i|
      current.push(nums[i])
      walk.call(i + 1, current)
      current.pop
    end
  end
  walk.call(0, [])
  out
end

p subsets([1, 2, 3])
p (0..3).flat_map { |n| [1, 2, 3].combination(n).to_a }
p [1, 2, 3].permutation.to_a.size
expected output
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
6

Combination sum

time O(n^(target/min)) space O(target/min)

Passing start rather than restarting at 0 is what stops [2,3] and [3,2] both appearing. Candidates may repeat here, so the recursive call passes i again rather than i + 1 — that single character is the difference between "reuse allowed" and "each used once".

def combination_sum(candidates, target)
  results = []

  walk = lambda do |start, remaining, current|
    return results << current.dup if remaining.zero?
    return if remaining.negative?

    (start...candidates.size).each do |i|
      current.push(candidates[i])
      walk.call(i, remaining - candidates[i], current)
      current.pop
    end
  end

  walk.call(0, target, [])
  results
end

p combination_sum([2, 3, 6, 7], 7)
p combination_sum([2], 1)
p combination_sum([2, 4], 6)
expected output
[[2, 2, 3], [7]]
[]
[[2, 2, 2], [2, 4]]

N-Queens

time O(n!) space O(n)

Place one queen per row, so only columns and the two diagonals need checking. Both diagonals have a constant along them — row - col and row + col — which turns "is this square attacked?" into three Set lookups.

require "set"

def solve_queens(n)
  solutions = []
  columns = Set.new
  rising = Set.new
  falling = Set.new
  placement = []

  place = lambda do |row|
    return solutions << placement.dup if row == n

    (0...n).each do |col|
      next if columns.include?(col) || rising.include?(row - col) || falling.include?(row + col)

      columns << col
      rising << row - col
      falling << row + col
      placement.push(col)

      place.call(row + 1)

      placement.pop
      columns.delete(col)
      rising.delete(row - col)
      falling.delete(row + col)
    end
  end

  place.call(0)
  solutions
end

p solve_queens(4)
p [1, 2, 3, 4, 5, 6].map { |n| solve_queens(n).size }
expected output
[[1, 3, 0, 2], [2, 0, 3, 1]]
[1, 0, 0, 2, 10, 4]
Graphs 3

A grid is a graph; so is a set of prerequisites. Once you see the adjacency, the traversal is mechanical — BFS for fewest steps, DFS for reachability, and a visited set in both so you terminate.

Number of islands (flood fill)

time O(rows · cols) space O(rows · cols) worst case

Each cell is visited once: the outer loop finds an unvisited land cell, then the flood sinks its whole component so it is never counted again. Mutating the grid is the standard trick for O(1) extra space — mention it, and ask whether mutating the input is acceptable.

def count_islands(grid)
  grid = grid.map(&:dup)

  sink = lambda do |r, c|
    return if r < 0 || c < 0 || r >= grid.size || c >= grid[0].size
    return unless grid[r][c] == "1"
    grid[r][c] = "0"
    [[1, 0], [-1, 0], [0, 1], [0, -1]].each { |dr, dc| sink.call(r + dr, c + dc) }
  end

  count = 0
  grid.each_index do |r|
    grid[r].each_index do |c|
      next unless grid[r][c] == "1"
      count += 1
      sink.call(r, c)
    end
  end
  count
end

p count_islands([
  %w[1 1 0 0 0],
  %w[1 1 0 0 0],
  %w[0 0 1 0 0],
  %w[0 0 0 1 1]
])
p count_islands([%w[0 0], %w[0 0]])
expected output
3
0

Course schedule (cycle detection)

time O(V + E) space O(V + E)

Three states, not two. A node being *in progress* is what distinguishes a genuine cycle from merely revisiting a node you already finished by another route — with a plain visited set, a diamond-shaped DAG reports a false cycle.

def can_finish?(course_count, prerequisites)
  graph = Hash.new { |h, k| h[k] = [] }
  prerequisites.each { |course, needs| graph[course] << needs }

  state = Array.new(course_count, :unvisited)

  walk = lambda do |node|
    return true  if state[node] == :done
    return false if state[node] == :in_progress

    state[node] = :in_progress
    return false unless graph[node].all? { |nxt| walk.call(nxt) }
    state[node] = :done
    true
  end

  (0...course_count).all? { |node| walk.call(node) }
end

p can_finish?(2, [[1, 0]])
p can_finish?(2, [[1, 0], [0, 1]])
# A diamond: 3 depends on 1 and 2, both of which depend on 0. Not a cycle.
p can_finish?(4, [[1, 0], [2, 0], [3, 1], [3, 2]])
expected output
true
false
true

Shortest path through a grid (BFS)

time O(rows · cols) space O(rows · cols)

BFS finds the fewest steps because it visits in order of distance — the first time you reach a cell is via a shortest route. Mark cells visited as you *enqueue*, not as you dequeue, or the same cell joins the queue many times.

def shortest_path(grid, from, to)
  rows, cols = grid.size, grid.first.size
  queue = [[from, 0]]
  seen = { from => true }

  until queue.empty?
    (cell, steps) = queue.shift
    return steps if cell == to

    r, c = cell
    [[1, 0], [-1, 0], [0, 1], [0, -1]].each do |dr, dc|
      nxt = [r + dr, c + dc]
      next if nxt[0] < 0 || nxt[1] < 0 || nxt[0] >= rows || nxt[1] >= cols
      next if grid[nxt[0]][nxt[1]] == 1 || seen[nxt]
      seen[nxt] = true
      queue << [nxt, steps + 1]
    end
  end

  -1
end

maze = [
  [0, 0, 0, 0],
  [1, 1, 0, 1],
  [0, 0, 0, 0],
  [0, 1, 1, 0]
]

p shortest_path(maze, [0, 0], [3, 3])
p shortest_path(maze, [0, 0], [0, 0])
p shortest_path([[0, 1], [1, 0]], [0, 0], [1, 1])
expected output
6
0
-1
Advanced graphs 3

Ordering under constraints, and shortest paths with weights. Topological sort is the answer to every "can this be scheduled?" question; Dijkstra is BFS where the queue is sorted by distance instead of by arrival.

Topological sort (Kahn's algorithm)

time O(V + E) space O(V + E)

Repeatedly take a node with no unmet prerequisites. If the output is shorter than the input, the leftovers are all in a cycle — which is how the same algorithm answers "is there a circular dependency?" for free.

def topological_sort(nodes, edges)
  incoming = nodes.to_h { |n| [n, 0] }
  outgoing = Hash.new { |h, k| h[k] = [] }

  edges.each do |from, to|
    outgoing[from] << to
    incoming[to] += 1
  end

  ready = nodes.select { |n| incoming[n].zero? }
  order = []

  until ready.empty?
    node = ready.shift
    order << node
    outgoing[node].each do |nxt|
      incoming[nxt] -= 1
      ready << nxt if incoming[nxt].zero?
    end
  end

  order.size == nodes.size ? order : nil
end

p topological_sort(%w[a b c d], [%w[a b], %w[a c], %w[b d], %w[c d]])
p topological_sort(%w[a b], [%w[a b], %w[b a]])
expected output
["a", "b", "c", "d"]
nil

Dijkstra's shortest paths

time O(V^2) here, O((V + E) log V) with a heap space O(V)

Scanning for the nearest unvisited node is O(V), which makes this O(V^2). A priority queue replaces that scan with O(log V) — say so, since Ruby has no built-in heap and an interviewer will want to know you noticed.

def dijkstra(graph, source)
  distance = graph.keys.to_h { |n| [n, Float::INFINITY] }
  distance[source] = 0
  unvisited = graph.keys.dup

  until unvisited.empty?
    node = unvisited.min_by { |n| distance[n] }
    break if distance[node] == Float::INFINITY
    unvisited.delete(node)

    graph[node].each do |neighbour, weight|
      candidate = distance[node] + weight
      distance[neighbour] = candidate if candidate < distance[neighbour]
    end
  end

  distance
end

graph = {
  "a" => { "b" => 1, "c" => 4 },
  "b" => { "c" => 2, "d" => 6 },
  "c" => { "d" => 3 },
  "d" => {},
  "x" => {}
}

p dijkstra(graph, "a")
expected output
{"a" => 0, "b" => 1, "c" => 3, "d" => 6, "x" => Infinity}

Minimum spanning tree (Kruskal)

time O(E log E) space O(V)

Sort the edges, take each one unless it would close a cycle — and union-find is what answers "would this close a cycle?" in near-constant time. This is the clearest case for knowing that structure: without it the cycle check is a traversal per edge.

class UnionFind
  def initialize(nodes)
    @parent = nodes.to_h { |n| [n, n] }
  end

  def find(x)
    @parent[x] = find(@parent[x]) unless @parent[x] == x
    @parent[x]
  end

  def union(a, b)
    root_a, root_b = find(a), find(b)
    return false if root_a == root_b
    @parent[root_b] = root_a
    true
  end
end

def kruskal(nodes, edges)
  uf = UnionFind.new(nodes)
  chosen = edges.sort_by(&:last).select { |a, b, _weight| uf.union(a, b) }
  [chosen, chosen.sum(&:last)]
end

nodes = %w[a b c d]
edges = [["a", "b", 1], ["b", "c", 2], ["a", "c", 4], ["c", "d", 3], ["a", "d", 10]]

chosen, total = kruskal(nodes, edges)
p chosen
p total
p chosen.size == nodes.size - 1
expected output
[["a", "b", 1], ["b", "c", 2], ["c", "d", 3]]
6
true
Dynamic programming — 1D 3

A recurrence plus a cache. Write the naive recursion first, notice it recomputes the same arguments, then either memoise it or flip it into a loop. If only the last couple of states matter, the array collapses to two variables.

Climbing stairs and house robber

time O(n) space O(1)

Both are Fibonacci wearing a hat. Climbing stairs sums the two previous states; house robber takes the better of skipping or taking. Keeping two variables instead of an array is the O(1)-space version interviewers look for.

def climb_stairs(n)
  a, b = 1, 1
  n.times { a, b = b, a + b }
  a
end

def rob(houses)
  skip = take = 0
  houses.each { |money| skip, take = [skip, take].max, skip + money }
  [skip, take].max
end

p (0..6).map { |n| climb_stairs(n) }
p rob([1, 2, 3, 1])
p rob([2, 7, 9, 3, 1])
p rob([])
expected output
[1, 1, 2, 3, 5, 8, 13]
4
12
0

Coin change

time O(amount · coins) space O(amount)

Bottom-up over every amount from 1 up. This is unbounded knapsack: coins may repeat, so the inner loop runs forwards. Greedily taking the largest coin is the tempting wrong answer — with coins [1, 3, 4] and amount 6 it gives 3 coins where 2 suffice.

def coin_change(coins, amount)
  best = Array.new(amount + 1, Float::INFINITY)
  best[0] = 0

  (1..amount).each do |value|
    coins.each do |coin|
      next if coin > value
      best[value] = [best[value], best[value - coin] + 1].min
    end
  end

  best[amount].infinite? ? -1 : best[amount]
end

p coin_change([1, 3, 4], 6)
p coin_change([1, 2, 5], 11)
p coin_change([2], 3)
p coin_change([2], 0)
expected output
2
3
-1
0

Longest increasing subsequence

time O(n^2), or O(n log n) with the patience method space O(n)

The O(n^2) version is the one to write first. The patience-sorting version keeps the smallest possible tail for each length and binary-searches the insert point — bsearch_index does that in one call, and the tails array's *length* is the answer even though its contents are not the subsequence.

def lis_quadratic(nums)
  return 0 if nums.empty?
  best = Array.new(nums.size, 1)

  nums.each_index do |i|
    (0...i).each do |j|
      best[i] = [best[i], best[j] + 1].max if nums[j] < nums[i]
    end
  end

  best.max
end

def lis_patience(nums)
  tails = []
  nums.each do |n|
    slot = tails.bsearch_index { |t| t >= n }
    slot ? tails[slot] = n : tails << n
  end
  tails.size
end

nums = [10, 9, 2, 5, 3, 7, 101, 18]
p lis_quadratic(nums)
p lis_patience(nums)
p [lis_patience([]), lis_patience([7]), lis_patience([5, 4, 3])]
expected output
4
4
[0, 1, 1]
Dynamic programming — 2D 3

Two sequences, so the state is a pair of positions and the table is a grid. Fill it so every cell's dependencies are already computed, and read the answer out of the far corner.

Longest common subsequence, and edit distance

time O(m · n) space O(m · n)

Same grid, different recurrence. Matching characters move diagonally; a mismatch takes the best neighbour. Edit distance adds one to that best neighbour because a mismatch costs an operation rather than merely being skipped.

def lcs(a, b)
  table = Array.new(a.size + 1) { Array.new(b.size + 1, 0) }

  a.each_char.with_index(1) do |ca, i|
    b.each_char.with_index(1) do |cb, j|
      table[i][j] = ca == cb ? table[i - 1][j - 1] + 1
                             : [table[i - 1][j], table[i][j - 1]].max
    end
  end

  table[a.size][b.size]
end

def edit_distance(a, b)
  table = Array.new(a.size + 1) { |i| Array.new(b.size + 1) { |j| i.zero? ? j : (j.zero? ? i : 0) } }

  a.each_char.with_index(1) do |ca, i|
    b.each_char.with_index(1) do |cb, j|
      table[i][j] = ca == cb ? table[i - 1][j - 1]
                             : 1 + [table[i - 1][j], table[i][j - 1], table[i - 1][j - 1]].min
    end
  end

  table[a.size][b.size]
end

p lcs("abcde", "ace")
p lcs("abc", "xyz")
p edit_distance("horse", "ros")
p edit_distance("", "abc")
expected output
3
0
3
3

0/1 knapsack

time O(n · capacity) space O(capacity)

Each item is taken or not, so unlike coin change the inner loop runs **backwards** — otherwise an item updated earlier in the same pass could be picked twice, silently turning this into the unbounded version.

def knapsack(weights, values, capacity)
  best = Array.new(capacity + 1, 0)

  weights.each_with_index do |weight, i|
    capacity.downto(weight) do |c|
      best[c] = [best[c], best[c - weight] + values[i]].max
    end
  end

  best[capacity]
end

p knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)
p knapsack([2], [3], 1)
p knapsack([], [], 5)
expected output
9
0
0

Unique paths, and minimum path sum

time O(rows · cols) space O(cols)

Both fill a grid where each cell depends only on the one above and the one to the left, so a single row rolling downwards is enough — row[c] still holds the value from above at the moment you read it.

def unique_paths(rows, cols)
  row = Array.new(cols, 1)
  (rows - 1).times { (1...cols).each { |c| row[c] += row[c - 1] } }
  row.last
end

def min_path_sum(grid)
  row = grid.first.each_with_object([]) { |v, acc| acc << v + (acc.last || 0) }

  grid.drop(1).each do |line|
    row[0] += line[0]
    (1...line.size).each { |c| row[c] = line[c] + [row[c], row[c - 1]].min }
  end

  row.last
end

p unique_paths(3, 7)
p unique_paths(1, 1)
p min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])
p min_path_sum([[1, 2, 3]])
expected output
28
1
7
6
Greedy 3

Take the locally best option and never reconsider. That is only correct when you can argue no earlier choice needs revisiting — so the interesting part of a greedy answer is always the justification, not the code.

Maximum subarray (Kadane's algorithm)

time O(n) space O(1)

At each element, either extend the running sum or start fresh from here. The justification: a prefix with a negative sum can never help what follows it, so discarding it costs nothing.

def max_subarray(nums)
  return 0 if nums.empty?

  best = running = nums.first
  nums.drop(1).each do |n|
    running = [n, running + n].max
    best = [best, running].max
  end
  best
end

p max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])
p max_subarray([-3, -1, -2])
p max_subarray([])
expected output
6
-1
0

Jump game

time O(n) space O(1)

Track the furthest index reachable so far. If the loop ever stands on an index beyond that reach, no earlier choice could have helped — which is the argument that makes the greedy pass correct rather than merely plausible.

def can_jump?(nums)
  reach = 0
  nums.each_with_index do |jump, i|
    return false if i > reach
    reach = [reach, i + jump].max
  end
  true
end

def min_jumps(nums)
  jumps = current_end = furthest = 0
  (0...nums.size - 1).each do |i|
    furthest = [furthest, i + nums[i]].max
    if i == current_end
      jumps += 1
      current_end = furthest
    end
  end
  jumps
end

p can_jump?([2, 3, 1, 1, 4])
p can_jump?([3, 2, 1, 0, 4])
p min_jumps([2, 3, 1, 1, 4])
p min_jumps([1])
expected output
true
false
2
0

Gas station

time O(n) space O(1)

Two observations do it. If the total gas covers the total cost a solution exists; and if you run dry between i and j, no station in that span can be the start either — so restart at j + 1 rather than re-testing each candidate.

def start_station(gas, cost)
  return -1 if gas.sum < cost.sum

  start = tank = 0
  gas.each_index do |i|
    tank += gas[i] - cost[i]
    if tank.negative?
      start = i + 1
      tank = 0
    end
  end

  start
end

p start_station([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])
p start_station([2, 3, 4], [3, 4, 3])
p start_station([5], [4])
expected output
3
-1
0
Intervals 3

Sort by start, then sweep. Nearly every interval question — merge, insert, count overlaps, fit meetings into rooms — is that sort followed by one linear pass comparing each interval to the one you are currently holding.

Merge overlapping intervals

time O(n log n) space O(n)

Sorting by start is what makes a single pass sufficient: once ordered, an interval can only ever overlap the one immediately before it. Note >= — whether [1,2] and [2,3] touch or merge is a question worth asking out loud.

def merge_intervals(intervals)
  intervals.sort_by(&:first).each_with_object([]) do |(start, finish), merged|
    if merged.any? && start <= merged.last[1]
      merged.last[1] = [merged.last[1], finish].max
    else
      merged << [start, finish]
    end
  end
end

p merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]])
p merge_intervals([[1, 4], [4, 5]])
p merge_intervals([])
expected output
[[1, 6], [8, 10], [15, 18]]
[[1, 5]]
[]

Insert into a sorted interval list

time O(n) space O(n)

Already sorted, so no sort is needed — three passes suffice: everything strictly before, the run that overlaps (absorbed into one), then everything strictly after. Sorting here would be the O(n log n) answer to an O(n) question.

def insert_interval(intervals, fresh)
  before = intervals.take_while { |_s, e| e < fresh[0] }
  after  = intervals.drop_while { |s, _e| s <= fresh[1] }
  overlapping = intervals[before.size...(intervals.size - after.size)]

  merged = overlapping.empty? ? fresh
                              : [[fresh[0], overlapping.first[0]].min,
                                 [fresh[1], overlapping.last[1]].max]

  before + [merged] + after
end

p insert_interval([[1, 3], [6, 9]], [2, 5])
p insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8])
p insert_interval([], [5, 7])
p insert_interval([[1, 5]], [6, 8])
expected output
[[1, 5], [6, 9]]
[[1, 2], [3, 10], [12, 16]]
[[5, 7]]
[[1, 5], [6, 8]]

Minimum meeting rooms

time O(n log n) space O(n)

Forget which meeting is which. Sort the starts and the ends separately and sweep: a start before the next end needs a new room, otherwise a room frees up. The peak concurrency is the answer.

def min_rooms(meetings)
  starts = meetings.map(&:first).sort
  ends = meetings.map(&:last).sort

  rooms = peak = 0
  finished = 0

  starts.each do |start|
    while finished < ends.size && ends[finished] <= start
      rooms -= 1
      finished += 1
    end
    rooms += 1
    peak = [peak, rooms].max
  end

  peak
end

p min_rooms([[0, 30], [5, 10], [15, 20]])
p min_rooms([[7, 10], [2, 4]])
p min_rooms([[1, 5], [2, 6], [3, 7]])
p min_rooms([])
expected output
2
1
3
0
Bit manipulation 3

Worth knowing three identities: XOR cancels equal values, n & (n - 1) clears the lowest set bit, and n & 1 tests parity. Most bit questions are one of those in disguise.

Single number, and counting bits

time O(n) space O(1)

XOR is its own inverse and is commutative, so every duplicate annihilates and the lone value survives. Ruby Integers are arbitrary precision, so there is no 32-bit wraparound to reason about — a genuine difference from the C or Java version of this answer.

def single_number(nums) = nums.reduce(0, :^)

def count_set_bits(n)
  count = 0
  while n.positive?
    n &= n - 1
    count += 1
  end
  count
end

p single_number([4, 1, 2, 1, 2])
p count_set_bits(11)
p 11.to_s(2)
p 11.digits(2).sum
expected output
4
3
"1011"
3

Counting bits for every number up to n

time O(n) space O(n)

i >> 1 is i with its last bit dropped, so its popcount is already known — add back the bit you dropped. That is a one-line DP recurrence, and beats calling a per-number popcount for each of the n values.

def count_bits(n)
  counts = Array.new(n + 1, 0)
  (1..n).each { |i| counts[i] = counts[i >> 1] + (i & 1) }
  counts
end

p count_bits(8)
p count_bits(0)
p (0..8).map { |n| n.to_s(2).count("1") }
expected output
[0, 1, 1, 2, 1, 2, 2, 3, 1]
[0]
[0, 1, 1, 2, 1, 2, 2, 3, 1]

Missing number, and powers of two

time O(n) and O(1) space O(1)

XOR the indices against the values and every present number cancels, leaving the absent one — no sorting, no extra Set. n & (n - 1) being zero means a single bit is set, which is exactly what a power of two is.

def missing_number(nums)
  (0..nums.size).reduce(:^) ^ nums.reduce(0, :^)
end

def power_of_two?(n) = n.positive? && (n & (n - 1)).zero?

p missing_number([3, 0, 1])
p missing_number([0])
p missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1])
p [1, 2, 3, 16, 0, -8].map { |n| power_of_two?(n) }
expected output
2
1
8
[true, true, false, true, false, false]
Math & geometry 3

Matrix rotation, spiral order, happy numbers. Usually less about cleverness than about getting indices right under pressure — and Ruby's Array methods remove most of the index arithmetic if you know them.

Rotate a matrix 90 degrees

time O(n^2) space O(n^2) here, O(1) in place

Transpose then reverse each row. transpose is built in, so the whole rotation is one line — but be ready to write the in-place layer-by-layer swap, which is what is usually being asked for.

def rotate(matrix) = matrix.transpose.map(&:reverse)

def rotate_in_place(matrix)
  matrix.reverse!
  (0...matrix.size).each do |i|
    (i + 1...matrix.size).each do |j|
      matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    end
  end
  matrix
end

p rotate([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
p rotate_in_place([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
expected output
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Spiral order

time O(rows · cols) space O(1) extra

Peeling: take the top row, rotate what remains anticlockwise, repeat. It is a three-line recursion in Ruby because transpose and reverse are built in — worth showing, then offering the four-boundary loop if they want the index arithmetic.

def spiral(matrix)
  return [] if matrix.empty? || matrix.first.empty?
  matrix.first + spiral(matrix.drop(1).transpose.reverse)
end

p spiral([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
p spiral([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])
p spiral([[7]])
p spiral([])
expected output
[1, 2, 3, 6, 9, 8, 7, 4, 5]
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
[7]
[]

Fast exponentiation, and happy numbers

time O(log n) and O(log n) per step space O(1)

Squaring halves the exponent each round, so 2^30 costs five multiplications rather than thirty. Happy numbers reuse Floyd's cycle detection from the linked-list section — any "does this process repeat?" question is that same tortoise and hare.

def power(base, exponent)
  return 1.0 / power(base, -exponent) if exponent.negative?

  result = 1
  while exponent.positive?
    result *= base if exponent.odd?
    base *= base
    exponent >>= 1
  end
  result
end

def next_square_sum(n) = n.digits.sum { |d| d * d }

def happy?(n)
  slow = fast = n
  loop do
    slow = next_square_sum(slow)
    fast = next_square_sum(next_square_sum(fast))
    return true if fast == 1
    break if slow == fast
  end
  false
end

p power(2, 10)
p power(3, 0)
p power(2, -2)
p [1, 7, 19, 2, 4].map { |n| happy?(n) }
expected output
1024
1
0.25
[true, true, true, false, false]
Two pointers 3

Two indices walk the same array, and the trick is always the same: prove that moving one of them can never discard the answer. Usually they start at opposite ends and close inward, which turns an O(n^2) pair search into a single O(n) pass with no extra memory.

Valid palindrome

time O(n) space O(1)

Walk inward from both ends. The normalising gsub is O(n) and allocates a new string, so the O(1) claim is about the comparison loop, not the whole method — an interviewer may well ask you that.

def palindrome?(s)
  t = s.downcase.gsub(/[^a-z0-9]/, "")
  i, j = 0, t.size - 1
  while i < j
    return false unless t[i] == t[j]
    i += 1
    j -= 1
  end
  true
end

p palindrome?("A man, a plan, a canal: Panama")
p palindrome?("race a car")
expected output
true
false

Two sum on a sorted array

time O(n) space O(1)

Sortedness is what earns the pointers. If the sum is too small only the left pointer can help, and if it is too big only the right one can — so each step discards a row or column of the pair space without ever examining it.

def two_sum_sorted(nums, target)
  i, j = 0, nums.size - 1
  while i < j
    sum = nums[i] + nums[j]
    return [i + 1, j + 1] if sum == target
    sum < target ? i += 1 : j -= 1
  end
  []
end

p two_sum_sorted([2, 7, 11, 15], 9)
p two_sum_sorted([2, 3, 4], 6)
p two_sum_sorted([1, 2], 99)
expected output
[1, 2]
[1, 3]
[]

Container with most water

time O(n) space O(1)

Area is width times the *shorter* wall, so moving the taller wall inward can only ever lose width without gaining height. Moving the shorter one is the only move that can improve the answer — which is why discarding it is safe.

def max_area(heights)
  best = 0
  i, j = 0, heights.size - 1
  while i < j
    best = [best, (j - i) * [heights[i], heights[j]].min].max
    heights[i] < heights[j] ? i += 1 : j -= 1
  end
  best
end

p max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])
p max_area([1, 1])
expected output
49
1

RUBY IDIOMS FOR INTERVIEWS

Ruby idioms worth knowing 3

The methods that turn five lines of loop into one, and the two or three places where Ruby's complexity differs from the Python or Java answer an interviewer may be carrying in their head.

Counting and grouping

time O(n) space O(n)

tally replaces the count-into-a-hash loop entirely. Hash.new(0) gives a default for arbitrary accumulation, and Hash.new { |h, k| h[k] = [] } gives an auto-vivifying bucket — note the block form assigns, so the array persists.

words = %w[apple banana apple kiwi banana apple]

p words.tally
p words.group_by(&:size)
p words.each_with_object(Hash.new(0)) { |w, h| h[w] += 1 }
p words.uniq.sort
p words.tally.max_by { |_w, n| n }
expected output
{"apple" => 3, "banana" => 2, "kiwi" => 1}
{5 => ["apple", "apple", "apple"], 6 => ["banana", "banana"], 4 => ["kiwi"]}
{"apple" => 3, "banana" => 2, "kiwi" => 1}
["apple", "banana", "kiwi"]
["apple", 3]

Windows, chunks and comparison

time O(n) space O(n)

each_cons gives overlapping windows — the whole sliding-window setup in one call. <=> returns -1, 0 or 1, and defining it plus including Comparable gets you <, between?, sort and min/max for free.

nums = [1, 3, 6, 10, 15]

p nums.each_cons(2).map { |a, b| b - a }
p nums.each_slice(2).to_a
p nums.each_cons(2).all? { |a, b| a < b }

Version = Struct.new(:major, :minor) do
  include Comparable
  def <=>(other) = [major, minor] <=> [other.major, other.minor]
  def to_s = "#{major}.#{minor}"
end

versions = [Version.new(2, 1), Version.new(1, 9), Version.new(2, 0)]
p versions.sort.map(&:to_s)
p versions.max.to_s
p Version.new(1, 5).between?(Version.new(1, 0), Version.new(2, 0))
expected output
[2, 3, 4, 5]
[[1, 3], [6, 10], [15]]
true
["1.9", "2.0", "2.1"]
"2.1"
true

Where Ruby's complexity surprises people

time see notes space O(1)

Array#shift is O(1): CRuby moves the array's start pointer rather than re-indexing, so an Array is a perfectly good queue — the same operation on a Python list is O(n), which is why Python answers reach for a deque. include? on an Array is O(n) while Set#include? and Hash#key? are O(1), and that single swap is the most common real speed-up in an interview answer.

require "set"

queue = [1, 2, 3]
p [queue.shift, queue]

haystack = (1..50_000).to_a
as_set = haystack.to_set

p haystack.include?(49_999)
p as_set.include?(49_999)
p as_set.size

p [1, 2, 3].sum
p (1..10).step(3).to_a
p [3, 1, 2].sort_by { |n| -n }
p [[1, "b"], [1, "a"], [0, "c"]].sort
expected output
[1, [2, 3]]
true
true
50000
6
[1, 4, 7, 10]
[3, 2, 1]
[[0, "c"], [1, "a"], [1, "b"]]