Convex Hull Trick
Maintain a set of lines so DP transitions of the form m*x + b can be optimized by querying only the best candidate line.
Interactive visualization
Use the controls to connect the idea to concrete operations before diving into the full write-up.
y = x + 1
value at x = 4: 5
y = 2x
value at x = 4: 8
y = -x + 8
value at x = 4: 4
Best line wins each query
Convex Hull Trick keeps only the lines that can be optimal somewhere. At x = 4, the best value is 4.
Family
Problem-solving strategies
Reusable paradigms like greedy choice, backtracking, and dynamic programming.
Builds on
1 topic
Read these first if you want the surrounding context.
Unlocks
1 next topic
Use these follow-ups when you want to apply the current idea in a richer setting.
Learning paths
2
This topic appears in curated progressions so you can keep moving without guessing the next step.
Problem
Many DP recurrences look like:
or the max version.
If you check every previous line candidate j, the transition becomes quadratic.
Core idea
Interpret each candidate as a line. For a new query x, you only care about the line that gives the best value there.
The Convex Hull Trick maintains only the lines that are potentially optimal somewhere.
Depending on the constraints, you can support queries with:
- monotonic pointer walking
- binary search over intersection points
- more dynamic structures like Li Chao trees
Why it matters
CHT is one of the most famous DP optimizations because it turns algebra into geometry.
It teaches a deep pattern:
an optimization recurrence can sometimes be reframed as querying the lower or upper envelope of lines
Complexity
The exact complexity depends on the variant, but monotonic or binary-search-based hulls often support near-linear or logarithmic transitions instead of quadratic ones.
Key takeaways
- Convex Hull Trick is a DP optimization viewpoint, not one single implementation
- Every candidate transition becomes a line
- Queries ask which line is best at the current
x - This is rare advanced optimization material, but it is one of the most important specialized DP tools
Practice problems
| Problem | Difficulty | Key idea |
|---|---|---|
| Line Add Get Min references | 🔴 Hard | Envelope of lines |
| Acquire references | 🔴 Hard | Classic CHT DP optimization |
| Covered Walkway references | 🔴 Hard | DP to line geometry |
Relation to other topics
- Dynamic Programming is where CHT most often appears
- Binary Search shows up in static hull variants that search intersection order
- Li Chao Tree is the dynamic segment-tree flavored cousin of the same line-query idea
Build on these first
These topics supply the mental model or underlying structure that this page assumes.
What this enables
Once the current idea feels natural, these are the most useful next jumps.
Related directions
These topics live nearby conceptually, even if they are not direct prerequisites.
Li Chao Tree
Maintain dynamic line insertion and min/max queries by storing line candidates in a segment tree over x-values.
Binary Search
Halve the search space at every step. Binary search is not just for sorted arrays — it's a general technique for any monotonic predicate.
More from Problem-solving strategies
Stay in the same family when you want parallel variations of the same mental model.
Backtracking
Systematically explore all possible solutions by building candidates incrementally and abandoning paths that cannot lead to valid solutions.
Greedy Algorithms
Make the locally optimal choice at each step to find a global optimum. Greedy works when the problem has optimal substructure and the greedy choice property.
Dynamic Programming
Break a problem into overlapping subproblems, solve each once, reuse the results. DP turns exponential brute force into polynomial time.
Paths that include this topic
Follow one of these sequences if you want a guided next step instead of open-ended browsing.
Strategy playbook
A reusable set of problem-solving moves for brute-force search, greedy choices, memoized state, and advanced DP optimization.
DP optimization
Turn transition formulas into line queries and move from hull geometry to dynamic Li Chao trees.
From the blog
Pair the atlas with recent writing from the rest of the site when you want a broader engineering perspective alongside the topic graph.