Precomputation
Overview
Precomputation involves doing expensive work once upfront (trading space for time) so that subsequent repetitive queries become significantly cheaper.
When the same kind of question is asked many times over the same fixed data, recalculating the answer iteratively incurs a massive penalty. Precomputing aggregates (like prefix sums) reduces O(n) queries to O(1).
Where used: Real-time pattern matching in continuous data streams., Computer vision algorithms, such as Integral Images, which calculate pixel sums inside arbitrary rectangles in O(1) time.
Why learn this
- It embodies a foundational engineering trade-off: sacrificing memory to permanently reduce time complexity.
- It is the recognition signal for when a problem asks for the SAME kind of answer over many different ranges/windows of the same fixed input.
Common mistakes
- Applying precomputation for a single query: If there is only one query, the upfront cost of precomputation is pure overhead with no payoff. The technique only wins when the upfront cost is amortized over multiple queries.
Recall questions
- What is the primary trade-off made in precomputation techniques?
- What is the surface recognition signal that precomputation might be required?
Understanding checks
A developer uses a prefix sum array to find the sum of a subarray, but the problem only asks for one single subarray sum. Why is this a poor design choice?
Because building the prefix sum array takes O(n) time and O(n) space. For a single query, a simple O(n) iteration requires only O(1) space, making the precomputation pure overhead.
Precomputation is an amortization strategy; its benefits only materialize when the upfront cost is spread across multiple subsequent O(1) queries.
You need to repeatedly check if a user has access to various files based on a complex inheritance hierarchy. Should you traverse the hierarchy on every request, or flatten the permissions into a hash map on startup?
Flatten into a hash map on startup. Traversing the hierarchy per request is an O(depth) operation, whereas precomputing the access map allows O(1) lookups for the high-frequency authorization checks.
This is a classic space-time trade-off. Authorization checks are frequent and must be fast, making them perfect candidates for upfront precomputation.
Practice tasks
Amortize the cost
Modify the given `query_frequencies` function. Instead of calling `.count()` on the array for every query (which is O(n * q)), precompute a frequency map once and use it to answer the queries in O(1) time.
Continue learning
Previous: Prefix Sums
Previous: Hash Tables