Seeing Numbers as Curves
Every array is a curve. Plot the indices on the x-axis and the values on the y-axis, and you've got a picture. [2, 5, 9, 14] becomes four dots that slope upward. [10, 7, 5, 4] slopes downward. [1, 4, 2, 8] bounces around with no pattern.
That picture — the shape of the data — tells you which algorithms work and which don't. Binary search needs an increasing curve. Sliding window needs monotonicity. DP optimizations need convexity or concavity. If you can't see the shape, you're guessing.
This page teaches you to see it.
Why Shape Matters
Here's the deal. When data has structure, you can exploit that structure for speed. And the most common structure is sorted order — values that go up (or down) consistently.
Take the array [2, 3, 5, 7, 11]. It's sorted. You can binary search it because it has a property: if the value at position mid is too small, everything to the left is also too small. You can throw away half the array in one step.
But here's the part most people miss: binary search doesn't just work on "arrays that happen to be sorted." It works on any increasing function. You can binary search on a mathematical quantity — a cost function, a distance, an answer — as long as that function is monotonically increasing (or decreasing). The array doesn't even have to exist physically.
This is why understanding shape matters. It's not about memorizing "binary search works on sorted arrays." It's about recognizing: "This function is increasing, therefore I can binary search on it." (For the nuts-and-bolts of implementing binary search correctly, see the Binary Search: Implementation Variations page.)
Slope: The Language of Shape
To talk precisely about shapes, we need one concept: slope.
In continuous math, slope is the derivative \(\mathrm{d}y / \mathrm{d}x\). But we're programmers, not mathematicians. Our data lives at discrete indices: \(0, 1, 2, 3, \ldots\) The gap between consecutive indices is always 1. So the slope between index \(i\) and \(i+1\) is just:
That's it. The slope is the difference between consecutive elements. No calculus needed.
Let's look at the 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 curve is going up. And the slopes themselves are increasing (3, 4, 5) — the curve is getting steeper. That specific pattern has a name: convex.
Now look at [10, 7, 5, 4]:
| Index | Value | Slope (Δ) |
|---|---|---|
| 0 | 10 | — |
| 1 | 7 | -3 |
| 2 | 5 | -2 |
| 3 | 4 | -1 |
Slopes: [-3, -2, -1]. All negative — the curve goes down. But the slopes are increasing (-3 → -2 → -1, getting less negative). So this is also convex. A bit counterintuitive, but we'll come back to that.
The Four Shapes You Need to Know
Every algorithm that exploits structure cares about one of these shapes. Let's define them through slopes.
1. Monotonically Increasing
All slopes are \(\ge 0\). The function never goes down.
If all slopes are strictly positive (\(> 0\)), it's strictly increasing — no ties allowed.
Why it matters: Binary search works. Two-pointer techniques work. Merge operations work. Basically, any algorithm that relies on "if I move right, the value only gets bigger" needs this.
2. Monotonically Decreasing
All slopes are \(\le 0\). The function never goes up.
Same as increasing, just mirrored. Binary search still works (just flip the comparison).
3. Convex (Bowl Shape)
The slopes are increasing. The curve might go down, then up — or just go up while getting steeper. The key is that the rate of change is growing.
Think of it as a bowl. The bottom of the bowl is the minimum, and both sides curve upward.
Why it matters: Convex functions have a single minimum. You can ternary search them. Convex + convex = convex (this enables Slope Trick, CHT, and other DP optimizations). The absolute value function \(|x|\) is convex.
4. Concave (Hill Shape)
The slopes are decreasing. The curve rises, then flattens, then falls. The rate of change is shrinking.
Think of it as a hill. The top is the maximum.
Why it matters: Concave functions have a single maximum. They show up in profit optimization problems — each extra unit of effort gives diminishing returns. The "max profit for \(K\) transactions" curve is typically concave.
Quick Reference
| Shape | Slope Condition | Visual | Has... |
|---|---|---|---|
| Increasing | All slopes \(\ge 0\) | ↗ | Sorted order |
| Decreasing | All slopes \(\le 0\) | ↘ | Reverse sorted |
| Convex | Slopes increasing | \(\cup\) | Single minimum |
| Concave | Slopes decreasing | \(\cap\) | Single maximum |
| Linear | All slopes equal | / | Both convex AND concave |
Notice that last row. A straight line has constant slope, which is trivially both "increasing" and "decreasing" (non-strictly). So a linear function is simultaneously convex and concave. This isn't a curiosity — it's a property you'll use later when we talk about function addition.
The Stock Profit Example
Let's make this real. Suppose you're trading a stock and you want to know: if I'm allowed \(K\) transactions, what's my maximum profit?
| \(K\) (transactions) | Max Profit |
|---|---|
| 0 | 0 |
| 1 | 50 |
| 2 | 80 |
| 3 | 95 |
| 4 | 100 |
| 5 | 102 |
Slopes (marginal profit per extra transaction): [50, 30, 15, 5, 2].
The slopes are decreasing: 50, 30, 15, 5, 2. Each additional transaction gives you less profit than the previous one. That's a concave curve.
Why does this matter? Because once you know the profit curve is concave, you can apply the Alien Trick (WQS Binary Search) to solve the problem much faster than a 2D DP. You don't need to memorize the optimization — you just need to recognize the shape.
Discrete vs. Continuous: We Don't Use Calculus
One thing that trips people up: in a calculus class, you check convexity by taking the second derivative. If \(f''(x) > 0\), it's convex.
We don't do that. Our functions live on integer indices. There's no continuous derivative. Instead, we check the differences of differences — the discrete equivalent.
If the slope array is [3, 4, 5], the differences of slopes are [1, 1] — both positive. Convex.
If the slope array is [50, 30, 15, 5], the differences of slopes are [-20, -15, -10] — all negative. Concave.
That's the whole test. No limits, no epsilon-delta. Just check whether the differences are increasing or decreasing. In practice, you won't even compute this explicitly — you'll develop an intuition for recognizing the pattern from the problem statement.
Storing and Comparing Slopes
Sometimes the slope isn't just \(\Delta y\) with \(\Delta x = 1\). When you're working with coordinates on a 2D plane, or comparing rates that don't share a common denominator, you need to handle slopes as fractions: \(\Delta y / \Delta x\).
The problem: floating point comparison is unreliable. Is 0.333333 equal to 1/3? Maybe. Maybe not.
Two clean ways to handle this:
Method 1: Reduce to lowest terms with GCD
Store the slope as a pair \((\Delta y / g, \, \Delta x / g)\) where \(g = \gcd(|\Delta y|, |\Delta x|)\). Two slopes are equal if and only if their reduced pairs are identical.
pair<int,int> normalizeSlope(int dy, int dx) {
if (dx == 0) return {1, 0}; // vertical line
if (dy == 0) return {0, 1}; // horizontal line
int sign = (dx < 0) ? -1 : 1; // normalize sign to denominator
int g = __gcd(abs(dy), abs(dx));
return {sign * dy / g, sign * dx / g};
}
Method 2: String key
Encode the reduced slope as a string "dy#dx" and use it as a hash map key. Quick and dirty, works fine for grouping slopes.
string slopeKey(int dy, int dx) {
int g = __gcd(abs(dy), abs(dx));
if (g != 0) { dy /= g; dx /= g; }
if (dx < 0) { dy = -dy; dx = -dx; }
return to_string(dy) + "#" + to_string(dx);
}
You'll see this in problems like "Max Points on a Line" — group points by slope, and the largest group (all on the same line) is your answer.
Predicate Form: Why Binary Search Really Works
There's a deeper way to think about binary search that connects directly to monotonicity.
Say you're searching for the first position where some condition is true. The condition might be "the value is \(\ge\) target" or "the cost exceeds the budget" or "we can ship all packages in \(D\) days."
If you line up the answers to this condition for every possible position, you get something like:
False, false, false... then at some point it flips to true and stays true forever. That's a monotonic predicate — it goes from false to true exactly once.
Binary search finds that flip point. It doesn't care whether you're searching an array, a cost function, or an abstract mathematical space. As long as the predicate is monotonic, binary search works.
The takeaway: when someone says "binary search on the answer," what they really mean is "the feasibility predicate is monotonic." If you can prove monotonicity, you can binary search. If you can't prove it, you can't.
But What If the Predicate Isn't Monotonic?
What if the pattern looks like 000...100...111 — a stray 1 in the middle before the real block of 1s? Standard binary search fails. It might land on the glitch and go the wrong direction. There are also interesting questions like: can you binary search a rotated sorted array? What about an unsorted array — which elements are "binary searchable"?
These edge cases and deeper explorations are covered in the dedicated binary search pages:
- Binary Search: Brainstorming Tasks — When can you binary search? What breaks it? What makes an element "binary searchable" in an unsorted array?
- Binary Search: Implementation Variations — The many ways to write binary search: loop conditions, midpoint calculations, pointer movement, and how to avoid infinite loops.
- Binary Search: Infinite Loop Quiz — 27 variations tested against edge cases. Hands-on practice to build bulletproof instincts.
This page gives you the why — monotonicity is the foundation. Those pages give you the how — writing correct binary search implementations that don't break on corner cases.
The Bigger Picture
Here's what we've built so far:
| Concept | What It Means | What It Unlocks |
|---|---|---|
| Slopes | Differences between consecutive values | A language for describing shape |
| Monotonic | Slopes all same sign | Binary search, two pointers, merge |
| Convex | Slopes increasing | Single minimum, ternary search, Slope Trick, CHT |
| Concave | Slopes decreasing | Single maximum, WQS Binary Search, D&C optimization |
| Linear | Slopes constant | Neutral — doesn't break any shape when added |
These aren't isolated definitions you memorize for an exam. They're a visual vocabulary that tells you which optimizations are legal. When you stare at a DP recurrence and the cost function is convex, that's not trivia — that's a signal that says "you can optimize this."
The next page — Difference Arrays: The Geometric Toolkit — shows you how to manipulate these curves efficiently. Instead of just reading shape, you'll learn to modify it: shifting curves up, tilting them, applying range updates — all through the lens of slopes.