</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

Linear and Sequence DP

What is this?

Every problem here walks a sequence once. What distinguishes them is what has to travel alongside the index: whether you currently hold a stock, whether you took a value and therefore destroyed its neighbours, which jump sizes are still available, or whether the next jump must be odd or even. Get the second component of the state right and each recurrence is short.

Linear and Sequence: what travels with the index (flowchart)

Fun fact: Delete and Earn is House Robber wearing a disguise. Taking the value v deletes every v−1 and v+1, so if you index by value instead of by array position, "cannot take adjacent values" is the robber's "cannot rob adjacent houses", with each house worth v × count(v). No new algorithm, just a change of coordinate. Spotting a known problem under a re-indexing is usually faster than deriving a fresh recurrence.

🔓 The 6 problems in this chapter are free. Sign in with Google or Microsoft to start solving.


Takeaway: the index is never the whole state. Name the second component (holding, taken, jump size, parity) and each recurrence shrinks to a line or two.


1. Two states chasing each other

cash, hold = 0, -prices[0]                  # cash: own nothing.  hold: own one share
for p in prices[1:]:
    cash = max(cash, hold + p - fee)        # sell today (pay the fee once, on sale)
    hold = max(hold, cash - p)              # buy today
return cash

Charging the fee on the sale rather than the purchase keeps it to one deduction per completed round trip. This loop updates cash first and then computes hold from the new cash. That is safe: a same-day sell followed by a buy can never beat the old plan, because the fee only makes it worse. Using the old cash would be equally correct. What matters is that cash is always the best profit holding nothing and hold the best profit holding one share.

The answer is cash, never hold: ending while still holding a share can never beat having sold it.

2. Re-index, then rob houses

pts = Counter(nums)
take, skip = 0, 0
for v in sorted(pts):
    if v - 1 in pts:                        # adjacent value → cannot take both
        take, skip = skip + v * pts[v], max(take, skip)
    else:                                   # gap → no constraint
        take, skip = max(take, skip) + v * pts[v], max(take, skip)
return max(take, skip)

Iterating over the sorted distinct values, not over 1 … max, keeps this O(n log n) time and O(n) space (the counter) even when the values are enormous. The v − 1 in pts test distinguishes a real adjacency from a gap in the value line. Getting it wrong gives a solution that refuses free points. If values are small (up to about 10^4), a dense House Robber table over 1 … max also works in O(n + max).

3. When the transitions come from a stack

Odd Even Jump is not a DP over values but over reachability, computed backwards. The simple version scans the suffix for each index and is O(n²); the stack version below is O(n log n):

odd[i]  = even[next_greater_or_equal[i]]    # odd jumps go up
even[i] = odd[next_smaller_or_equal[i]]     # even jumps go down

Both "next" arrays come from a monotonic stack over indices sorted by value. Sorting by (value, index) turns "the smallest value ≥ this one, leftmost on ties" into an ordinary next-greater scan over positions. The stack holds positions in decreasing order from bottom to top. The DP itself is then two lines, running right to left because a jump always moves forward.

4. The stack that is not a DP at all

Longest Valid Parentheses has an O(n) DP, a stack solution, and a two-pass counter scan that needs only O(1) space. The stack version:

st, best = [-1], 0                          # -1 is the base of the current valid run
for i, ch in enumerate(s):
    if ch == '(': st.append(i)
    else:
        st.pop()
        if not st: st.append(i)             # unmatched ')' becomes the new base
        else: best = max(best, i - st[-1])

The sentinel -1 is what lets i - st[-1] measure a run that starts at index 0 without a special case. The stack and the DP both use O(n) space. The two-pass scan counts ( and ) left to right, resetting when closes exceed opens, then repeats right to left to catch runs with extra opens, and gets O(1) space. Knowing the stack version and the scan, and saying which you prefer and why, is worth more than either alone.


5. A 30-second worked example (stock with fee)

prices = [1, 3, 2, 8, 4, 9], fee = 2

start          cash =  0   hold = -1
p = 3          cash = max(0, -1+3-2) =  0     hold = max(-1,  0-3) = -1
p = 2          cash = max(0, -1+2-2) =  0     hold = max(-1,  0-2) = -1
p = 8          cash = max(0, -1+8-2) =  5     hold = max(-1,  5-8) = -1
p = 4          cash = max(5, -1+4-2) =  5     hold = max(-1,  5-4) =  1
p = 9          cash = max(5,  1+9-2) =  8     hold = max( 1,  8-9) =  1

answer: 8

Two transactions (buy at 1, sell at 8, buy at 4, sell at 9) make 7 + 5 = 12 gross, and two fees of 2 leave 8. Watch the step at p = 4: hold becomes 1 because cash was already 5 from the sale at 8, so buying at 4 costs 5 - 4.


6. Where you'll actually meet this

  • Trading with costs. A per-trade fee is why chasing every small uptick loses money, and the two-state machine in the fee problem is the standard way to model it.
  • Bracket matching. Longest balanced region is the same scan an editor can use to find the unmatched brackets in a line.
  • Re-indexing. Delete and Earn is the habit of asking whether a problem is a known one on a different axis.

7. Problems in this chapter

Best Time to Buy and Sell Stock with Transaction Fee

Maximum profit with a fee per transaction. Carry two states, holding and not holding, and roll them forward one day at a time.
Pattern: two-state linear DP. Target: O(n) time, O(1) space.

Delete and Earn

Take a value and lose its neighbours. Index by value rather than position and the problem becomes House Robber.
Pattern: re-indexed House Robber. Target: O(n + max) with a dense table, or O(n log n) time and O(n) space over sorted distinct values.

Frog Jump

Cross a river where the next jump is within one of the last. State is (stone, jump size), stored as a set per stone.
Pattern: reachability DP with a compound state. Target: O(n²) time and space. Memoized recursion works, but its depth grows with n and passes Python's default recursion limit near n = 2000, so I'd write the forward set DP.

Longest Increasing Subsequence

The classic, with an O(n²) DP and an O(n log n) version. Maintain the smallest possible tail for each length and binary-search the insertion point. The tails array gives the length but is not always a real subsequence: on [3, 1, 4, 1, 5, 9, 2, 6] it ends as [1, 2, 5, 6], yet the 2 comes after the 5 in the input.
Pattern: patience sorting. Target: O(n log n) time, O(n) space.

Longest Valid Parentheses

Longest balanced substring. A DP on match positions, a stack of indices with a sentinel base, or a two-pass counter scan.
Pattern: stack with an index sentinel. Target: O(n) time; O(n) space for the stack or DP, O(1) for the two-pass scan.

Odd Even Jump

Count indices from which the end is reachable under alternating jump rules. Precompute the odd and even targets with a monotonic stack over value-sorted indices, then a two-line DP backwards.
Pattern: monotonic stack + reachability DP. Target: O(n log n) time, O(n) space.


8. Common pitfalls

  • Charging the fee twice. Deduct it once per completed transaction, on the sale.
  • Mixing up what cash and hold mean. Both are best profits at the end of a day; cash holds nothing, hold holds one share. Either update order works if you keep that meaning.
  • Iterating 1 … max(nums) in Delete and Earn, which explodes on large values. Iterate the distinct values.
  • Missing the gap case. When v − 1 is absent there is no constraint and you take both.
  • Storing only "reachable" in Frog Jump. The jump size that got you there is part of the state.
  • Deep recursion in Python. Memoized Frog Jump can pass the default recursion limit near n = 2000. Prefer the forward DP.
  • Treating tails as the answer sequence in LIS. It gives the length only; keep predecessor indices if you need the subsequence.
  • Forgetting the -1 sentinel in the parentheses stack, which breaks every run starting at index 0.
  • Sorting by value without an index tie-break in Odd Even Jump. Equal values must resolve to the smaller index.

9. Key takeaways

  1. The index alone is never the state in this chapter. Name what travels with it.
  2. Re-indexing can turn a new problem into a known one. Value, not position.
  3. Define each state precisely. cash and hold as end-of-day best profits make the update order a detail rather than a trap.
  4. A monotonic stack can supply DP transitions as easily as it answers next-greater queries.
  5. Sentinels remove edge cases. One -1 replaces a special case for index 0.
  6. Know more than one solution where several exist, and be able to say which you prefer.
  7. Why interviewers like it: these all look one-dimensional and none of them are, so the state choice is the entire signal.

Order: Best Time to Buy and Sell Stock with Transaction Fee → Delete and Earn → Frog Jump → Longest Increasing Subsequence → Longest Valid Parentheses → Odd Even Jump.

Longest Increasing Subsequence

Core idea: You don't need to remember every subsequence. You only need, for each possible length, the smallest tail you've managed to achieve. Keep that one number per length in a sorted array called tails, and binary-search every incoming value into it. The length of tails is the answer, and the binary search is what turns an O(n²) DP into O(n log n).


Problem, rephrased

You maintain a release dashboard that streams version numbers as builds land, in arrival order. You're given an integer array nums, where nums[i] is the version number of the i-th build to land (builds arrive out of order, so the stream jumps around).

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.