Shapes and Curves (Beginner)
Every array is a picture. Plot the indices on the x-axis and the values on the y-axis, and you can see the data. That picture — the shape — tells you which algorithms will work.
This page introduces just the essentials: what "slope" means for arrays, and the four shapes you need to recognize.
Slope = The Difference Between Neighbors
Forget calculus. For arrays, slope is dead simple:
It's just how much the value changes from one position to the next.
Example: Array [2, 5, 9, 14]
| Index | Value | Slope |
|---|---|---|
| 0 | 2 | — |
| 1 | 5 | +3 |
| 2 | 9 | +4 |
| 3 | 14 | +5 |
Slopes: [3, 4, 5]. All positive — the values are going up. The slopes themselves are also going up — the curve is getting steeper.
Example: Array [10, 6, 3, 1]
Slopes: [-4, -3, -2]. All negative — the values go down.
That's it. Slope = difference between consecutive values. Everything else on this page builds from that one idea.
The Four Shapes
1. Increasing (All slopes >= 0)
The array never goes down. This is a sorted array.
Why it matters: Binary search works. If you're looking for a target, you can throw away half the array at each step because you know everything to the left is smaller and everything to the right is bigger.
Quick example: Is 7 in the array [1, 3, 5, 8, 12]?
- Check the middle: 5. Too small → look right.
- Check the middle of
[8, 12]: 8. Too big → look left. - Nothing left. 7 is not in the array.
Two comparisons instead of five. That's the power of an increasing shape.
2. Decreasing (All slopes <= 0)
The array never goes up. Binary search still works — just flip the comparison.
3. Convex — Bowl Shape
The slopes go from very negative to very positive. The curve goes down, hits a bottom, then goes up. Like a bowl.
The key property: there's exactly one minimum. The bottom of the bowl.
Why it matters: You can find the minimum efficiently. You don't need to check every element — the bowl shape guarantees the minimum is at the bottom, and you can narrow down where that is quickly (ternary search).
Real example: You're choosing how many servers to rent. Too few → overload penalties are expensive. Too many → rental costs are expensive. The total cost curve is a bowl — there's a sweet spot in the middle.
4. Concave — Hill Shape
The slopes go from very positive to very negative. The curve goes up, hits a peak, then comes down. Like a hill.
The key property: there's exactly one maximum. The top of the hill.
Real example: You're a stock trader allowed \(K\) transactions. Each extra transaction helps, but less and less (diminishing returns). The profit curve is a hill — it rises fast at first, then flattens out.
| \(K\) | Profit | Extra profit |
|---|---|---|
| 1 | 50 | — |
| 2 | 80 | +30 |
| 3 | 95 | +15 |
| 4 | 100 | +5 |
Each extra transaction gives less. That's a concave (hill) shape.
How to Check the Shape
You don't need fancy math. Just compute the slopes and look:
| Shape | What the slopes look like |
|---|---|
| Increasing | All \(\ge 0\) |
| Decreasing | All \(\le 0\) |
| Convex (bowl) | Going up: \(-5, -3, -1, +2, +4\) |
| Concave (hill) | Going down: \(+4, +3, +1, -1, -3\) |
If the slopes are increasing → convex. If the slopes are decreasing → concave.
A straight line (constant slope) is both convex and concave at the same time. It's the "neutral" shape — it doesn't break anything.
One Rule That Matters Most
Here's the most useful fact on this page:
Adding two bowl-shaped (convex) functions gives another bowl.
If cost function A is a bowl and cost function B is a bowl, then A + B is also a bowl. The sum still has exactly one minimum.
This sounds abstract, but it shows up everywhere in DP. Your total cost is often the sum of several component costs. If each component is convex, the total is convex — and you can optimize it efficiently.
The same works for hills: concave + concave = concave.
But bowl + hill = ??? — could be anything. No guarantee.
What This Unlocks
Recognizing shapes is the first step toward powerful optimizations:
| Shape | What you can do |
|---|---|
| Increasing/Decreasing | Binary search, two pointers |
| Convex (bowl) | Find the minimum efficiently |
| Concave (hill) | Find the maximum efficiently |
You don't need to understand the optimizations yet. Just practice seeing the shape. When you look at an array or a cost function, ask: is it going up? Down? Bowl? Hill?
That instinct will serve you in every algorithm you learn.
Ready for more? The full versions go deeper — slope manipulation with difference arrays, function addition rules, and how these shapes connect to 12 specific DP optimizations: