Linear DP
Walk along a list once, and at each position work out the best answer so far from the answers at the few positions before it.
O(n)Space O(n)17 practice problemsStep-through pictureThe idea
Linear DP works on a sequence: an array, a string, or a row of days. The state is one position in the sequence. One cell, best[i], answers the question for the first i + 1 items, or for a sequence that ends at item i.
At each position you make a small decision, usually "take this item or skip it" or "start fresh here or continue". The answer for position i comes from one or two earlier positions, so a single left-to-right pass is enough.
The template below solves a classic version. You have a row of values and want the largest total, but you may never pick two neighbors.
An everyday example
Picking stalls at a market without neighbors
You can visit stalls along a street, and each stall gives you some coins, but the owners don't allow you to visit two stalls side by side. Walking down the street, at each stall you ask: is it better to skip this stall and keep my best total so far, or take its coins plus my best total from two stalls back? You never need to remember more than that.
| In the example | In the code |
|---|---|
| The row of stalls | The values array |
The best total after looking at stall i | best[i] |
| Skipping the stall | skip = best[i - 1] |
| Taking the stall, which rules out its left neighbor | take = values[i] + best[i - 2] |
| Choosing the better plan | best[i] = Math.max(skip, take) |
From the slow way to linear dp
- Start with brute force: try every way to pick items with no two neighbors, add up each choice, and keep the largest. The number of such choices grows exponentially, by about 1.6 times per extra item: a row of 30 items has 2,178,309 valid choices, and a row of 40 has 267,914,296. Each also needs a sum, so this is far too slow.
- Simple rules don't work either. "Take every other item" picks a fixed pattern and ignores the values. "Take the biggest item, cross out its neighbors, repeat" can give up two medium items for one big one. The only safe way is to compare real options, but without listing every choice.
- Walk along the row and ask about one item at a time. For item
i, there are only two options: skip it, or take it. If you skip it, the best you can have is whatever was best up to itemi - 1. If you take it, itemi - 1is off limits, so you addvalues[i]to the best up to itemi - 2. Nothing else about the earlier choices matters. - So store one number per position:
best[i], the largest total using items0toi. Each cell isMath.max(skip, take)from two cells you already have. One pass from left to right fills it, and the last cell is the answer. That loop is linear DP.
How it works
- Define
best[i]: the largest total you can get fromvalues[0]tovalues[i]without picking two neighbors. - Base case: with one item,
best[0]isvalues[0], or0if that value is negative and you would rather pick nothing. - For each later
i, computeskip = best[i - 1]: leave itemialone and keep the best from before. - Compute
take = values[i] + best[i - 2]: pick itemi, which rules out itemi - 1, so add the best up toi - 2(or0if there is none). - Set
best[i] = Math.max(skip, take). - The answer is
best[n - 1], the best total over the whole row.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function bestNonAdjacent(values) {const n = values.length;if (n === 0) return 0;const best = new Array(n).fill(0);best[0] = Math.max(0, values[0]);for (let i = 1; i < n; i++) {const skip = best[i - 1];const take = values[i] + (i >= 2 ? best[i - 2] : 0);best[i] = Math.max(skip, take);}return best[n - 1];}
How fast it is
| Time | O(n) |
|---|---|
| Extra memory | O(n) |
Each position is visited once with two additions and a comparison. The table has one cell per position, and it can be cut to two variables because only the last two cells are ever read.
- Best case
O(1)An empty row: line 3 returns 0 before any table is made.
- Average case
O(n)Any row of
nitems: one pass, two additions and a comparison per item. - Worst case
O(n)The same as the average. The values never change how many cells are read.
Common mistakes
- Using a greedy rule like "pick every other item" or "pick the biggest first". For
[2, 1, 1, 2]the best is2 + 2 = 4, which neither rule finds. - Reading
best[i - 2]wheniis 1, which isbest[-1]and givesundefined. Handle the start of the row on its own. - Mixing up "best among the first
iitems" with "best ending exactly at itemi". Write the meaning down; the transition and the final answer depend on it. - Returning
best[n]when the table has onlyncells. Match the final index to how you sized the table.
When to use it
Look for these clues in a problem:
- The input is one array or string and the answer is a best total, a count, or a yes or no.
- Each item is taken or skipped, with a rule about neighbors, such as "no two in a row".
- The answer for a prefix (the first
iitems) can be built from the answers for slightly shorter prefixes. - A greedy choice (always take the biggest item) fails on some small example.
Check yourself
Answer each one in your head first, then open it.
Why is best[0] set to Math.max(0, values[0]) instead of values[0]?
Because picking nothing is allowed. If the first value is negative, the best total using only it is to leave it, which is 0.
Why does take read best[i - 2] and not best[i - 1]?
Taking item i rules out its neighbor i - 1. best[i - 1] might include that neighbor, while best[i - 2] only uses items that are safe to combine with i.
Can best[i] ever be smaller than best[i - 1]?
No. skip equals best[i - 1], and best[i] is the larger of skip and take, so it is at least best[i - 1].
In the trace, why does the last item, 1, get skipped?
Taking it gives 1 + best[3] = 12, because it can't sit next to the 10. Skipping keeps 17, which is larger.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 17 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingeasy
medium
Go further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
The table keeps one promise: best[i] is the largest total you can get from values[0] to values[i] with no two neighbors picked. For i = 0, that is either the one value or nothing, whichever is bigger, which is exactly line 5.
Each new cell keeps the promise because the best choice up to i falls into one of two cases. If it doesn't use item i, it is a valid choice from items 0 to i - 1, so it can be no better than best[i - 1], and best[i - 1] itself is reachable. If it does use item i, it can't use i - 1, so the rest is a valid choice from items 0 to i - 2, worth at most best[i - 2]. The larger of the two cases is the answer, and the code computes both.
Filling from left to right means best[i - 1] and best[i - 2] are always ready. The loop visits each index once and stops after n - 1, so the promise says best[n - 1] is the best for the whole row. Notice that best never goes down, since skip is always one of the options.
Going deeper
3 more ideas
Why looking back two places is enough
Any good selection either uses the last item or does not. If it doesn't, it is a good selection of the items before it, which is best[i - 1]. If it does, the item before it is not picked, so the rest is a good selection of items up to i - 2, which is best[i - 2]. Those two cases cover every possibility.
How much work it does
One pass with a constant amount of work per item: O(n) time. The table uses O(n) space, but each cell only reads the two before it, so two variables (prev and prevPrev) are enough for O(1) space.
Other shapes of linear DP
"Ends exactly at i" states are common too. For the largest sum of a contiguous run, best[i] is the largest sum of a run that ends at i: either values[i] alone or values[i] + best[i - 1]. Some problems look further back, such as best[i - 7] for a weekly pass, but the idea is the same.
Work it by hand
Every step in a table, with why
Pick values from a row of 6, never two neighbors, for the largest total. The first value is negative.
values = [-2, 7, 3, 4, 10, 1]
| Step | i | values[i] | skip | take | best[i] | What happens | Why |
|---|---|---|---|---|---|---|---|
| 1 | 0 | -2 | - | - | 0 | Base: pick nothing | Math.max(0, -2) is 0. Taking a negative value only lowers the total, so the best with one item is to pick none. |
| 2 | 1 | 7 | 0 | 7 + 0 = 7 | 7 | Take wins | There is no best[-1], so take adds 0 for the earlier part (line 8). |
| 3 | 2 | 3 | 7 | 3 + 0 = 3 | 7 | Skip wins | Taking 3 means giving up the 7 next to it. Keeping 7 is better. |
| 4 | 3 | 4 | 7 | 4 + 7 = 11 | 11 | Take wins | 4 is not next to 7, so it can join the best from up to index 1. |
| 5 | 4 | 10 | 11 | 10 + 7 = 17 | 17 | Take wins | Taking 10 rules out the 4, so it adds best[2], which is 7 (the 7 at index 1). |
| 6 | 5 | 1 | 17 | 1 + 11 = 12 | 17 | Skip wins; loop ends | Taking 1 would mean dropping the 10. The last cell is filled, and line 11 returns it. |
It returns 17, from picking 7 and 10. "Every other item" would give -2 + 3 + 10 = 11 or 7 + 4 + 1 = 12, both worse. The loop ends after the last index.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Linear DP | O(n) | O(n) | The clear first version: the table makes each step easy to check and to walk back through. |
| Two rolling variables | O(n) | O(1) | When you only need the total, not the list of picked items. |
| Try every valid choice | O(2^n) | O(n) | Only to check the DP on rows of 15 items or fewer. |
| Greedy, biggest value first | O(n log n) | O(n) | Never for this problem. It can give up two medium values for one big one, which is wrong when the two together are worth more. |
Extra memory: O(n) for the best array. Only the last two cells are ever read, so two variables, often named prev and prevPrev, give O(1) space.
How the steps grow
- Linear DP, Two rolling variables
O(n) - Try every valid choice
O(2^n) - Greedy, biggest value first
O(n log n)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Linear DP | 10 | 1,000 | 1 million |
| Two rolling variables | 10 | 1,000 | 1 million |
| Try every valid choice | 1,024 | more than a quadrillion | more than a quadrillion |
| Greedy, biggest value first | 33 | 9,966 | 20 million |
Inputs that need care
5 tricky inputs
- An empty row:
values = [] - Line 3 returns 0. No items means no total.
- One item:
values = [9] - The loop never runs, and it returns
best[0], which is 9. - Only negative values:
values = [-4, -1, -6] - Every cell stays 0, so it returns 0: picking nothing is allowed. If the problem says you must pick at least one item, the answer should be the largest value,
-1, and the base case must change. - The best choice uses both ends:
values = [5, -1, -1, 5] bestbecomes[5, 5, 5, 10], so it returns 10. Skipping two items in a row is allowed, and the table handles it with no special rule.- Equal options, where skip and take tie
Math.maxreturns the same number either way, so the total is right. If you also rebuild which items were picked, decide which way ties go and stick to it.
Variations and follow-ups
Twists interviewers add
A circular row
If the first and last items are neighbors, they can't both be picked. Run the same loop twice: once on items 0 to n - 2, and once on items 1 to n - 1. The larger of the two answers is right, because any valid choice leaves out the first item or the last.
Best run that ends at i
For the largest sum of a contiguous run, the state changes to "the best run that ends exactly at i": either values[i] alone, or values[i] added to the best run ending at i - 1. The answer is the largest cell, not the last one. This is Kadane's algorithm.
A wider gap
If picked items must be at least k apart, take reads best[i - k] instead of best[i - 2]. The table and the loop stay the same; only how far back you look changes.
Listing the picked items
Walk back from the end: if best[i] equals best[i - 1], item i was skipped, so move to i - 1. Otherwise it was taken, so record it and jump to i - 2. Skipped negative first items need the same check at index 0.
In an interview
Spot it, explain it, answer follow-ups
- Spot it when the input is one sequence, you decide something at each position, and the rule only links an item to its near neighbors: "no two adjacent", "at most one per day", "must rest after".
- Say the state in one sentence and say whether it means "best among the first
i + 1items" or "best ending exactly ati". The transition and the place you read the answer both depend on that choice. - Test four tiny rows by hand: empty, one item, two items where the second is bigger, and a row whose answer skips two in a row, like
[5, -1, -1, 5]. - Expect two follow-ups: "do it in
O(1)space" (keep the last two cells in variables) and "what if the row is a circle?" (run it twice, without the first item and without the last).
Where frontend code uses it
The same idea in real UI code
- Choosing which posts to feature in a feed when two featured posts may not sit next to each other is this exact take-or-skip DP.
- Analytics dashboards that show "best streak" or "largest gain over a period" compute it in one pass with a linear DP like Kadane's algorithm.
- Planning which days to buy a 1-day, 7-day, or 30-day plan for a paid API is a linear DP over the days of the month.