Coin change problem solution in clojure
Coin Change in Clojure:
A Functional Take on Classic DP
Dynamic Programming · Clojure · Loop/Recur · Persistent Data Structures
The Coin Change problem is one of those classic puzzles that appears deceptively simple on the surface but exposes fundamental ideas about optimal substructure, overlapping subproblems, and the trade-offs between top-down (memoization) and bottom-up (tabulation) approaches. In this post we walk through a clean, idiomatic Clojure solution and highlight what makes it distinctly Lispy.
Problem Statement
Given an integer array coins representing coin denominations and an integer
amount, return the fewest number of coins needed to reach exactly that
amount. If no combination can reach it, return -1.
coins = [1, 5, 6, 9], amount = 11Optimal:
9 + 1 + 1 = 11 → 3 coins. A greedy approach (take the largest
coin first) would give 9 + 1 + 1 — that's lucky here, but greedy fails for many
denominations. DP is the safe bet.
The Solution
(defn coin-change [coins amount]
(loop [memo (into [] (concat '(0) (repeat amount Integer/MAX_VALUE)))
coins coins
n (first coins)]
(let [[coin & xs] coins]
(cond
(not coin) (let [r (get memo amount)]
(if (= r Integer/MAX_VALUE) -1 r))
(> n amount) (recur memo xs (first xs))
:else (recur
(update memo n #(min % (inc (get memo (- n coin)))))
coins
(inc n))))))How the Algorithm Works
This is a bottom-up tabulation approach. We build a 1-D DP array memo
of size amount + 1, where memo[i] represents the minimum number of coins
needed to make amount i.
Recurrence relation
memo[0] = 0 ; base case: 0 coins to make amount 0
memo[i] = ∞ ; initially "unreachable"
for each coin c in coins:
for n from c to amount:
memo[n] = min(memo[n], 1 + memo[n - c])
For each denomination, we sweep n from the coin's face value up to amount.
At each step we ask: "Is it cheaper to reach n using this coin on top of whatever it costs
to reach n - coin?" This is the unbounded knapsack pattern — each coin may be used
any number of times.
Worked example: coins = [1, 5], amount = 6
| Pass | memo[0] | memo[1] | memo[2] | memo[3] | memo[4] | memo[5] | memo[6] |
|---|---|---|---|---|---|---|---|
| Init | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| coin=1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| coin=5 | 0 | 1 | 2 | 3 | 4 | 1 | 2 |
After processing both coins, memo[6] = 2 (one 5 + one 1). The answer is returned from
memo[amount].
Clojure-Specific Highlights
1. loop / recur — tail recursion without a call stack
Clojure runs on the JVM, which does not natively support tail-call optimisation (TCO).
The loop / recur special form is the idiomatic workaround: recur
jumps back to the nearest loop binding point in constant stack space.
This is not ordinary recursion — it's a compiler-level jump. The pattern gives us the
clarity of recursive thinking with the efficiency of a for loop.
memo, coins, and
n — effectively encoding the entire iteration state as immutable snapshots
that are replaced on each recur call.
2. Persistent vectors and structural sharing
(update memo n #(min % ...)) does not mutate the vector.
Clojure's persistent vectors use a bit-partitioned trie (a 32-way tree)
under the hood: updating a single element creates a new vector that shares all unchanged
branches with the old one. For a vector of length amount + 1 this is
O(log32 N) per update — effectively O(1) for realistic inputs. You get
immutability for free without paying a meaningful performance price.
3. Java interop — Integer/MAX_VALUE
Clojure sits on the JVM and can reach directly into Java's standard library.
Integer/MAX_VALUE (2 147 483 647) is used here as a sentinel representing
"unreachable". This is a deliberate trade-off: it avoids a separate boolean reachability
flag, keeping the cond branches minimal. The one gotcha to watch for is
integer overflow — (inc Integer/MAX_VALUE) wraps to a negative number in Java.
The code sidesteps this because we only call inc on memo[n - coin]
after not short-circuiting on (not coin), and any slot that remains
MAX_VALUE can only appear at memo[amount], which is checked
separately at the end.
4. Lazy sequences and repeat
(into [] (concat '(0) (repeat amount Integer/MAX_VALUE)))
(repeat amount Integer/MAX_VALUE) produces a lazy sequence:
no memory is allocated for the elements until they are consumed. concat glues
the '(0) sentinel in front, and into [] realises the entire
sequence into a persistent vector in one pass. This is a characteristic Clojure idiom —
build with lazy pipelines, materialise only when you need random access.
5. Sequential destructuring in let
(let [[coin & xs] coins]
...)
Clojure's destructuring binds coin to the first element of coins
and xs to the remainder — equivalent to Haskell's x:xs pattern.
When coins is exhausted, coin becomes nil, which the
(not coin) branch catches cleanly without an explicit length check.
6. The dual-cursor trick
Notice that the loop carries both coins (the remaining
denominations) and n (the current target amount) as separate
loop variables. When n exceeds amount we advance the coin cursor
(xs) and reset n to the face value of the next coin
((first xs)). This encodes the nested for coin / for amount loop as a
single flat loop/recur without nesting, which is the idiomatic way to express
nested iteration in functional Clojure.
Complexity Analysis
Let C = number of coin denominations, A = target amount.
| Dimension | Complexity | Notes |
|---|---|---|
| Time | O(C × A) | One inner sweep of length A for each of the C coins |
| Space | O(A) | Single 1-D memo vector; no recursion stack |
The bottom-up approach has the same asymptotic complexity as a top-down memoised DFS but avoids all call-stack overhead and cache-miss patterns associated with hash-map memoisation. The persistent vector also gives better cache locality than a hash map for dense integer keys.
A Note on Purity
The entire function is referentially transparent: the same inputs always
produce the same output, and no global state is touched. Each recur call
passes a logically new memo vector, even though Clojure's runtime shares
structure beneath the surface. This purity makes the function trivially testable, safe to
call from parallel threads, and easy to reason about — you never need to ask "what was
the state of memo before this call?"
Potential Pitfalls
Coin order independence: Because each denomination sweeps the full range
of n before the next coin is processed, the final result is independent of
the order of coins. However, the intermediate states of memo
differ by order, which matters if you try to add early-exit heuristics.
Zero-value coins: If a zero-value coin slips into the input, n
would never advance beyond 0, creating an infinite loop. The standard LeetCode problem
guarantees coins[i] >= 1, so this is safe — but worth guarding in
production code.
Integer/MAX_VALUE overflow: As noted above, do not attempt
arithmetic on a slot that still holds MAX_VALUE without first confirming the
predecessor slot is reachable. The current code does this correctly through its final
(if (= r Integer/MAX_VALUE) -1 r) check.
Closing Thoughts
This Clojure solution is a great example of how functional idioms — loop/recur,
persistent data structures, lazy sequences, and destructuring — can express a classic
imperative algorithm without sacrificing readability or correctness. The code is concise,
purely functional, and runs efficiently on the JVM without any mutation.
(coin-change [1 5 6 9] 11) → 2 (9 + 1 + 1? No — 6 + 5!)(coin-change [2] 3) → -1
Happy hacking — and may your recurrence relations always have optimal substructure. 🪙
Comments
Post a Comment