Longest Increasing Subsequence II (LeetCode 2407)
You will see how a segment tree over values answers "the longest chain ending at any value in this window" in O(log M), a window max that a Fenwick tree can't give.
You get an integer array nums and an integer k. Choose some elements of nums, keeping their original order (you may skip any), so that:
- each chosen element is strictly larger than the one chosen before it, and
- it is larger by at most
k.
Return the largest number of elements such a choice can have.
Worked Examples
nums = [4,2,1,4,3,4,5,8,15], k = 35nums = [7,4,5,1,8,12,4,7], k = 54nums = [1,5], k = 11⚖️Formal Constraints & Bounds
1 <= nums.length <= 1051 <= nums[i], k <= 105
Why It Works & Core Invariant
Index the tree by value, not by position: slot v holds the longest valid chain that ends with value v. The chain ending at x is one more than the max over the window of values [x - k, x - 1], and a segment tree answers any window max and any point update in O(log M).
Real-World Scenario & Production Applications
A metrics store keeps one reading per time bucket and answers "peak over this window" while new readings arrive: a tree of per-block maxima changes one leaf and its ancestors per reading and combines a few blocks per window. Here the "buckets" are values, and the reading in bucket v is the longest chain that ends with v.
Subproblems & Recurrence Decomposition3 Phases
dp[i] is the length of the longest increasing subsequence that ENDS at index i. Every single element is trivially an increasing subsequence of length 1 by itself.
dp = [1] * len(nums)Step-by-Step Execution Trace Table
LeetCode Example 1: nums = [4,2,1,4,3,4,5,8,15], k = 3. best[v] is what the tree's slot v holds.
x | Window [max(x - k, 0), x - 1] | seg.query(...) | longest | best after seg.update(x, longest) | answer |
|---|---|---|---|---|---|
| 4 | [1, 3] | 0 | 1 | 4: 1 | 1 |
| 2 | [0, 1] | 0 | 1 | 2: 1, 4: 1 | 1 |
| 1 | [0, 0] | 0 | 1 | 1: 1, 2: 1, 4: 1 | 1 |
| 4 | [1, 3] | 1 | 2 | 4: 2 | 2 |
| 3 | [0, 2] | 1 | 2 | 3: 2 | 2 |
| 4 | [1, 3] | 2 | 3 | 4: 3 | 3 |
| 5 | [2, 4] | 3 | 4 | 5: 4 | 4 |
| 8 | [5, 7] | 4 | 5 | 8: 5 | 5 |
| 15 | [12, 14] | 0 | 1 | 15: 1 | 5 |
Each seg.update also recomputes every ancestor of the changed leaf; without that, the query for x = 8 still reads an old, smaller max and the answer drops to 4.
| 1 | The chain ending at `x` is one longer than the longest chain ending at any value in `[x - k, x - 1]`: a window max over values, then a point update, so a max segment tree over values. |
| 2 | After every `update`, `self.tree[node]` equals the largest value stored in the slots `left..right` that `node` covers; `query` returns the stored max when fully inside, `0` when fully outside, and the larger of both halves otherwise. |
| 3 | `seg = SegmentTree(max(nums) + 1)`; for each `x`: `longest = seg.query(max(x - k, 0), x - 1) + 1`, `seg.update(x, longest)`, `answer = max(answer, longest)`. |
| 4 | The trap: after the recursive `update` returns, recompute `self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2])`, or every max above the leaf stays stale. |
Target: Longest Increasing Subsequence II (LeetCode 2407). Slot `v` holds the longest valid chain that ends with value `v`. Elements are handled left to right, so everything already in the tree comes from earlier positions.
Trie: root-to-node path encodes common prefix; DSU: find(u) with path compression flattens tree so root is direct parent.
Trie: traverse word char-by-char in O(L); DSU: if find(u) != find(v): union(u, v) in O(alpha(N)).
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Call best[v] the longest valid choice that ends with value v. A new element x can only follow a value in [x - k, x - 1], so its chain is one longer than the largest best over that window of values. Scanning every earlier element for each x is O(N^2). A segment tree over values stores the max of a range in every node: the root covers every value, its two children cover the two halves, and so on down to single values. Any window splits into a few stored nodes, and changing one value only touches the nodes on the path from its leaf to the root. A Fenwick tree answers prefix sums well, but a max over a window in the middle can't be built from two prefixes; the segment tree answers it directly.
🏔️ The Analogy: The Tallest Peak in a Range of Maps
A survey office keeps a map sheet for every square kilometre, a sheet for every block of four, then sixteen, up to the whole country, and each sheet notes only the tallest peak on it. To find the tallest peak between two roads you pick a few big sheets that sit fully inside that stretch and a few small ones at its edges, and compare their notes. When one peak is re-measured, only the sheets that contain it need a new note.
🪄 The Mathematical Harmony / Magic Trick
for x in nums: longest = seg.query(max(x - k, 0), x - 1) + 1 seg.update(x, longest) answer = max(answer, longest) query returns a node's stored max when the node lies fully inside [ql, qr], 0 when it lies fully outside, and the larger of its two children's answers otherwise. update walks down to the leaf for x, stores the longer chain there, and on the way back up sets self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2]) for every ancestor. That recompute is what keeps every stored max true.
💡 Summary
Node i covers [left, right], its children 2i + 1 and 2i + 2 cover the halves; 4 * n slots are always enough. The window [x - k, x - 1] stops at x - 1 because an equal value is not strictly larger. Each query and update is O(log M), so the whole run is O(N log M) with M = max(nums), and the tree takes O(M) space.
Not recomputing ancestors: changing only the leaf in
updateleaves every max above it stale; on LeetCode Example 1 (nums = [4,2,1,4,3,4,5,8,15],k = 3) the answer drops from 5 to 4. Recomputeself.tree[node]after the recursive call returns.A window that includes
x:seg.query(max(x - k, 0), x)lets an equal value extend the chain, but each chosen element must be strictly larger;nums = [3,3,3]would return 3 instead of 1. Stop the window atx - 1.A window that starts at
x - k + 1: a step of exactlykis allowed, so the window starts atx - k; withnums = [1,2,3,4,5],k = 1, starting atx - k + 1returns 1 instead of 5.An overlap test instead of a containment test:
querymay returnself.tree[node]only whenql <= left and right <= qr; a node that merely overlaps the window also holds values outside it, and Example 1 would return 9.Too little space:
2 * nslots overflow whennis not a power of two; allocate4 * n.A tree over positions: the window is a range of values,
[x - k, x - 1], not of indexes, so the tree needs one slot per value up tomax(nums).
4-Phase Thought Process Model
You will see how a senior engineer spots a window max over values and explains why updates must recompute on the way up.
Pattern Recognition Signals
The 10-second spot
"Strictly larger" and "larger by at most k": the element before x must be a value in [x - k, x - 1], so the chain ending at x is one more than the best chain ending anywhere in that window of values. A window max in the middle of the range, mixed with a point update after every element, is the job of a Segment Tree over values; a Fenwick tree only gives prefixes.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After every update, self.tree[node] equals the largest value stored in the slots left..right that node covers; slot v holds the longest valid chain ending with value v, and query uses a node's stored max only when the node lies fully inside [ql, qr].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2])after the recursiveupdate: changing only the leaf leaves every max above it stale.seg.query(max(x - k, 0), x - 1): the window stops atx - 1, because an equal value is not strictly larger, and starts atx - k, because a step of exactlykis allowed.if ql <= left and right <= qr: a containment test, not an overlap test; a node that only overlaps the window also holds values outside it.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Segment Tree over values. Slot v holds the longest valid chain that ends with value v. For each x in order, the element before it must be a value from x minus k to x minus one, so I ask the tree for the max over that window, add one, and store it at x. Each node stores the max of a range and its two children store the halves: a node fully inside the window returns its stored max, a node fully outside returns zero, and otherwise I ask both children; at most two nodes per level are only partly covered, so a query visits O(log M) nodes. An update walks down to the leaf for x and, on the way back up, recomputes each ancestor as the max of its two children. That recompute is the trap: skip it and every max above the leaf goes stale. A Fenwick tree can't do this, because a max over a window can't be built from two prefixes. Total time is O(N log M) with M the largest value, and space is O(M).
So: slot per value, window [x - k, x - 1], fully inside / fully outside / split, then overwrite the leaf with the longer chain and recompute every ancestor.
Complexity & Mathematical Proof
O(N log M), M = max(nums)
Look at the loop: each of the N elements makes one seg.query and one seg.update. update follows one path from the root to a leaf (depth about log2 M) and does O(1) work per node on the way back up: O(log M). query stops at nodes fully inside or fully outside the window; at each level at most two nodes are only partly covered, so it visits O(log M) nodes. Total: O(N log M).
O(M)
self.tree has 4 * (max(nums) + 1) slots: O(M). The recursion is at most about log2 M + 1 calls deep, which is O(log M) of call stack.
Derivation Progression
depth × O(1) = O(log M)
One root-to-leaf path down, one recompute per ancestor on the way up.
≤ 2 partial nodes per level = O(log M)
Fully inside or fully outside nodes stop the recursion immediately.
N × O(log M)
One query and one update per element of nums.
Variable Definitions
Length of nums
max(nums): the tree has one slot per value 0..M
A tree slot; its children are 2 * node + 1 and 2 * node + 2
Memory Architecture & Bounds
O(log M): recursion depth of update and query
O(M): self.tree with 4(M + 1) slots
O(1): one integer
Boundary Best / Worst Cases
: every element still walks one root-to-leaf path in update
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "strictly larger", "larger by at most k". The element before x must be a value in [x - k, x - 1], so the chain ending at x needs the best chain over a window of values, then a point update: a Segment Tree over values with max as the combine.
and values up to . The dynamic program over every earlier position is , about steps, far too slow. A Fenwick tree gives prefix maxima, not a max over [x - k, x - 1]; the segment tree answers it in , about 17 levels here.
The tree has one slot per possible value, so its size follows max(nums), not len(nums): with values up to you would first compress the values to their ranks (sort the distinct values) and keep the window bounds as ranks.
Core Algorithmic State Invariants
- Index by Value, Not by Position
Slot v holds the longest valid chain that ends with value v, and elements are handled left to right, so everything already in the tree comes from earlier positions. The window of values that may come before x is [x - k, x - 1].
- Inside, Outside, Split
query returns the stored max for a node fully inside [ql, qr], 0 for a node fully outside, and the larger of both children's answers otherwise; a node that is only partly inside must never return its stored max.
- Log-Depth Paths
update follows one root-to-leaf path and query meets at most two partly covered nodes per level: O(log M) each, so N elements cost O(N log M), with 4(M + 1) slots of space.
Longest Increasing Subsequence II (LeetCode 2407)
You will see how a segment tree over values answers "the longest chain ending at any value in this window" in O(log M), a window max that a Fenwick tree can't give.
You get an integer array nums and an integer k. Choose some elements of nums, keeping their original order (you may skip any), so that:
- each chosen element is strictly larger than the one chosen before it, and
- it is larger by at most
k.
Return the largest number of elements such a choice can have.
Worked Examples
nums = [4,2,1,4,3,4,5,8,15], k = 35nums = [7,4,5,1,8,12,4,7], k = 54nums = [1,5], k = 11⚖️Formal Constraints & Bounds
1 <= nums.length <= 1051 <= nums[i], k <= 105
Why It Works & Core Invariant
Index the tree by value, not by position: slot v holds the longest valid chain that ends with value v. The chain ending at x is one more than the max over the window of values [x - k, x - 1], and a segment tree answers any window max and any point update in O(log M).
Real-World Scenario & Production Applications
A metrics store keeps one reading per time bucket and answers "peak over this window" while new readings arrive: a tree of per-block maxima changes one leaf and its ancestors per reading and combines a few blocks per window. Here the "buckets" are values, and the reading in bucket v is the longest chain that ends with v.
Subproblems & Recurrence Decomposition3 Phases
dp[i] is the length of the longest increasing subsequence that ENDS at index i. Every single element is trivially an increasing subsequence of length 1 by itself.
dp = [1] * len(nums)Step-by-Step Execution Trace Table
LeetCode Example 1: nums = [4,2,1,4,3,4,5,8,15], k = 3. best[v] is what the tree's slot v holds.
x | Window [max(x - k, 0), x - 1] | seg.query(...) | longest | best after seg.update(x, longest) | answer |
|---|---|---|---|---|---|
| 4 | [1, 3] | 0 | 1 | 4: 1 | 1 |
| 2 | [0, 1] | 0 | 1 | 2: 1, 4: 1 | 1 |
| 1 | [0, 0] | 0 | 1 | 1: 1, 2: 1, 4: 1 | 1 |
| 4 | [1, 3] | 1 | 2 | 4: 2 | 2 |
| 3 | [0, 2] | 1 | 2 | 3: 2 | 2 |
| 4 | [1, 3] | 2 | 3 | 4: 3 | 3 |
| 5 | [2, 4] | 3 | 4 | 5: 4 | 4 |
| 8 | [5, 7] | 4 | 5 | 8: 5 | 5 |
| 15 | [12, 14] | 0 | 1 | 15: 1 | 5 |
Each seg.update also recomputes every ancestor of the changed leaf; without that, the query for x = 8 still reads an old, smaller max and the answer drops to 4.
| 1 | The chain ending at `x` is one longer than the longest chain ending at any value in `[x - k, x - 1]`: a window max over values, then a point update, so a max segment tree over values. |
| 2 | After every `update`, `self.tree[node]` equals the largest value stored in the slots `left..right` that `node` covers; `query` returns the stored max when fully inside, `0` when fully outside, and the larger of both halves otherwise. |
| 3 | `seg = SegmentTree(max(nums) + 1)`; for each `x`: `longest = seg.query(max(x - k, 0), x - 1) + 1`, `seg.update(x, longest)`, `answer = max(answer, longest)`. |
| 4 | The trap: after the recursive `update` returns, recompute `self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2])`, or every max above the leaf stays stale. |
Target: Longest Increasing Subsequence II (LeetCode 2407). Slot `v` holds the longest valid chain that ends with value `v`. Elements are handled left to right, so everything already in the tree comes from earlier positions.
Trie: root-to-node path encodes common prefix; DSU: find(u) with path compression flattens tree so root is direct parent.
Trie: traverse word char-by-char in O(L); DSU: if find(u) != find(v): union(u, v) in O(alpha(N)).
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Call best[v] the longest valid choice that ends with value v. A new element x can only follow a value in [x - k, x - 1], so its chain is one longer than the largest best over that window of values. Scanning every earlier element for each x is O(N^2). A segment tree over values stores the max of a range in every node: the root covers every value, its two children cover the two halves, and so on down to single values. Any window splits into a few stored nodes, and changing one value only touches the nodes on the path from its leaf to the root. A Fenwick tree answers prefix sums well, but a max over a window in the middle can't be built from two prefixes; the segment tree answers it directly.
🏔️ The Analogy: The Tallest Peak in a Range of Maps
A survey office keeps a map sheet for every square kilometre, a sheet for every block of four, then sixteen, up to the whole country, and each sheet notes only the tallest peak on it. To find the tallest peak between two roads you pick a few big sheets that sit fully inside that stretch and a few small ones at its edges, and compare their notes. When one peak is re-measured, only the sheets that contain it need a new note.
🪄 The Mathematical Harmony / Magic Trick
for x in nums: longest = seg.query(max(x - k, 0), x - 1) + 1 seg.update(x, longest) answer = max(answer, longest) query returns a node's stored max when the node lies fully inside [ql, qr], 0 when it lies fully outside, and the larger of its two children's answers otherwise. update walks down to the leaf for x, stores the longer chain there, and on the way back up sets self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2]) for every ancestor. That recompute is what keeps every stored max true.
💡 Summary
Node i covers [left, right], its children 2i + 1 and 2i + 2 cover the halves; 4 * n slots are always enough. The window [x - k, x - 1] stops at x - 1 because an equal value is not strictly larger. Each query and update is O(log M), so the whole run is O(N log M) with M = max(nums), and the tree takes O(M) space.
Not recomputing ancestors: changing only the leaf in
updateleaves every max above it stale; on LeetCode Example 1 (nums = [4,2,1,4,3,4,5,8,15],k = 3) the answer drops from 5 to 4. Recomputeself.tree[node]after the recursive call returns.A window that includes
x:seg.query(max(x - k, 0), x)lets an equal value extend the chain, but each chosen element must be strictly larger;nums = [3,3,3]would return 3 instead of 1. Stop the window atx - 1.A window that starts at
x - k + 1: a step of exactlykis allowed, so the window starts atx - k; withnums = [1,2,3,4,5],k = 1, starting atx - k + 1returns 1 instead of 5.An overlap test instead of a containment test:
querymay returnself.tree[node]only whenql <= left and right <= qr; a node that merely overlaps the window also holds values outside it, and Example 1 would return 9.Too little space:
2 * nslots overflow whennis not a power of two; allocate4 * n.A tree over positions: the window is a range of values,
[x - k, x - 1], not of indexes, so the tree needs one slot per value up tomax(nums).
4-Phase Thought Process Model
You will see how a senior engineer spots a window max over values and explains why updates must recompute on the way up.
Pattern Recognition Signals
The 10-second spot
"Strictly larger" and "larger by at most k": the element before x must be a value in [x - k, x - 1], so the chain ending at x is one more than the best chain ending anywhere in that window of values. A window max in the middle of the range, mixed with a point update after every element, is the job of a Segment Tree over values; a Fenwick tree only gives prefixes.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After every update, self.tree[node] equals the largest value stored in the slots left..right that node covers; slot v holds the longest valid chain ending with value v, and query uses a node's stored max only when the node lies fully inside [ql, qr].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2])after the recursiveupdate: changing only the leaf leaves every max above it stale.seg.query(max(x - k, 0), x - 1): the window stops atx - 1, because an equal value is not strictly larger, and starts atx - k, because a step of exactlykis allowed.if ql <= left and right <= qr: a containment test, not an overlap test; a node that only overlaps the window also holds values outside it.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Segment Tree over values. Slot v holds the longest valid chain that ends with value v. For each x in order, the element before it must be a value from x minus k to x minus one, so I ask the tree for the max over that window, add one, and store it at x. Each node stores the max of a range and its two children store the halves: a node fully inside the window returns its stored max, a node fully outside returns zero, and otherwise I ask both children; at most two nodes per level are only partly covered, so a query visits O(log M) nodes. An update walks down to the leaf for x and, on the way back up, recomputes each ancestor as the max of its two children. That recompute is the trap: skip it and every max above the leaf goes stale. A Fenwick tree can't do this, because a max over a window can't be built from two prefixes. Total time is O(N log M) with M the largest value, and space is O(M).
So: slot per value, window [x - k, x - 1], fully inside / fully outside / split, then overwrite the leaf with the longer chain and recompute every ancestor.
Complexity & Mathematical Proof
O(N log M), M = max(nums)
Look at the loop: each of the N elements makes one seg.query and one seg.update. update follows one path from the root to a leaf (depth about log2 M) and does O(1) work per node on the way back up: O(log M). query stops at nodes fully inside or fully outside the window; at each level at most two nodes are only partly covered, so it visits O(log M) nodes. Total: O(N log M).
O(M)
self.tree has 4 * (max(nums) + 1) slots: O(M). The recursion is at most about log2 M + 1 calls deep, which is O(log M) of call stack.
Derivation Progression
depth × O(1) = O(log M)
One root-to-leaf path down, one recompute per ancestor on the way up.
≤ 2 partial nodes per level = O(log M)
Fully inside or fully outside nodes stop the recursion immediately.
N × O(log M)
One query and one update per element of nums.
Variable Definitions
Length of nums
max(nums): the tree has one slot per value 0..M
A tree slot; its children are 2 * node + 1 and 2 * node + 2
Memory Architecture & Bounds
O(log M): recursion depth of update and query
O(M): self.tree with 4(M + 1) slots
O(1): one integer
Boundary Best / Worst Cases
: every element still walks one root-to-leaf path in update
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "strictly larger", "larger by at most k". The element before x must be a value in [x - k, x - 1], so the chain ending at x needs the best chain over a window of values, then a point update: a Segment Tree over values with max as the combine.
and values up to . The dynamic program over every earlier position is , about steps, far too slow. A Fenwick tree gives prefix maxima, not a max over [x - k, x - 1]; the segment tree answers it in , about 17 levels here.
The tree has one slot per possible value, so its size follows max(nums), not len(nums): with values up to you would first compress the values to their ranks (sort the distinct values) and keep the window bounds as ranks.
Core Algorithmic State Invariants
- Index by Value, Not by Position
Slot v holds the longest valid chain that ends with value v, and elements are handled left to right, so everything already in the tree comes from earlier positions. The window of values that may come before x is [x - k, x - 1].
- Inside, Outside, Split
query returns the stored max for a node fully inside [ql, qr], 0 for a node fully outside, and the larger of both children's answers otherwise; a node that is only partly inside must never return its stored max.
- Log-Depth Paths
update follows one root-to-leaf path and query meets at most two partly covered nodes per level: O(log M) each, so N elements cost O(N log M), with 4(M + 1) slots of space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| One slot per value, not per position | seg = SegmentTree(max(nums) + 1) | Slot `v` holds the longest valid chain that ends with value `v`. Elements are handled left to right, so everything already in the tree comes from earlier positions. |
| Room for 4n nodes | self.tree = [0] * (4 * self.n) | With children `2 * node + 1` and `2 * node + 2`, 4n slots always fit the tree; every slot starts at `0`, no chain yet. |
| Window max over the values that may come before x | longest = seg.query(max(x - k, 0), x - 1) + 1 | The value chosen before `x` must be smaller than `x` by at most `k`, so it lies in `[x - k, x - 1]`; clamp the left end at `0`. |
| Query: fully inside, fully outside, or split | if ql <= left and right <= qr:
return self.tree[node]
if right < ql or left > qr:
return 0 | Fully inside uses the stored max; fully outside returns the neutral `0`; otherwise ask both halves and keep the larger answer. |
| Point update at the leaf | self.tree[node] = max(self.tree[node], val) | The leaf for `x` keeps the longest chain that ends with value `x` so far. |
| Recompute on the way back up | self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2]) | The card's trap: every ancestor of the changed leaf is rebuilt from its two children, or later window queries read a stale max. |
| The answer is the longest chain seen | answer = max(answer, longest) | Any value can end the best choice, so keep the largest `longest` over all elements. |