Meet in the Middle
Halve the exponent by splitting the search.
Meet in the Middle is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
When Brute Force Is Too Slow
Some problems have N around 40, where trying all 2^N subsets is hopeless. Meet in the middle rescues these mid-size cases. 🤝
The Core Idea
Split the input into two halves. Solve each half by brute force, then cleverly combine the two partial results.
Halving the Exponent
Two halves of size N/2 cost 2^(N/2) each instead of 2^N total. That square root shrink turns 2^40 into a friendly 2^20.
A Classic Target: Subset Sum
Ask whether some subset sums to a target T. Subset sum with N near 40 is the textbook meet-in-the-middle problem.
Enumerate the First Half
List every subset sum of the left half and store them. With N/2 items this is just 2^(N/2) sums.
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []Enumerate the Second Half
Do the same for the right half, building its full list of subset sums. Now you have two manageable lists.
Combine with a Lookup
For each right sum r, you need a left sum equal to T minus r. A set or sorted list makes that check fast.
need = T - r
found = need in left_setTwo Ways to Match
For exact targets use a hash set. For counting or closest sums, sort one half and binary-search into it.
The Time Cost
Total work is about 2^(N/2) times a log factor for the search or sort. That complexity is what makes N near 40 doable.
Memory Is the Trade-off
You store one full half, so memory grows to 2^(N/2). Keep only what you must to stay within the limit.
Where Else It Shines
Beyond subset sum, use it for max subset under a cap, counting pairs, and discrete-log style problems. It loves a clean split.
Quick Check
You apply meet in the middle to a subset problem with N items. What is the rough time cost?
Recap
Split into two halves, brute-force each, then match left and right sums. You traded a tiny bit of memory for a huge speedup. 🚀
Frequently asked questions
Is the “Meet in the Middle” lesson free?
Yes — the full text of “Meet in the Middle” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Meet in the Middle”?
Halve the exponent by splitting the search. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Meet in the Middle” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.