Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Find the length of the longest strictly increasing subsequence (elements need not be contiguous). The classic DP is O(n²): dp[i] = longest LIS ending at i. The optimal is patience sorting with binary search — maintain a 'tails' array where tails[k] is the smallest possible tail of an increasing subsequence of length k+1, and binary-search each number into it: O(n log n) time.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can write the standard O(n²) LIS DP cleanly, and whether you know the O(n log n) patience-sorting / binary-search optimization and can explain why the tails array stays sorted.
Where candidates slip
Confusing subsequence with subarray (requiring contiguity), or in the binary-search version using the wrong bound (bisect_right vs bisect_left) so 'strictly increasing' silently becomes 'non-decreasing'.
How to stand out
Derive the O(n²) DP, then explain the patience-sorting model: tails[k] is the minimal tail of a length-(k+1) subsequence, so a smaller tail always dominates — that's why binary search and overwrite are correct.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewLongest increasing SUBSEQUENCENeed the actual subsequence?Yes, reconstructJust the lengthExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Dynamic Programming — dp Ending at i (O(n²))
1Hint 1Explore hintHide hint
Define dp[i] = length of the longest increasing subsequence that ENDS exactly at index i. What does dp[i] depend on?
2Hint 2Explore hintHide hint
To end at i, the previous element must be some j < i with nums[j] < nums[i]. So dp[i] = 1 + max(dp[j]) over all such j (or 1 if none).
3Hint 3Explore hintHide hint
Two nested loops: outer i, inner j < i. Answer is the max over all dp[i], since the LIS can end anywhere.
A · Core idea
Let dp[i] be the length of the longest strictly increasing subsequence that ends at index i. Every element starts as its own length-1 subsequence; extend it by looking back at every earlier element smaller than nums[i].
Why anchor the subproblem on 'ending at i'. The total LIS can end anywhere, which is hard to recurse on directly. Pinning the subproblem to 'ends exactly at i' makes the recurrence local and clean: any increasing subsequence ending at i is some shorter increasing subsequence ending at an earlier j (with nums[j] < nums[i]) plus nums[i] itself. So dp[i] = 1 + max(dp[j] for j < i where nums[j] < nums[i]), defaulting to 1 when no smaller predecessor exists. The final answer is max(dp) because we don't know in advance which index the best subsequence ends on.
Why strictness lives in the comparison. The single condition nums[j] < nums[i] (strict <, not <=) is what enforces strictly increasing. Relax it to <= and [7, 7, 7, 7] would report 4 instead of 1. This one operator is the entire difference between the two problem variants.
Why this is the version to reach for when you need the subsequence itself. Because dp[i] records where each subsequence ends, you can store a parent[i] pointer to the j that produced the max and walk it backward to reconstruct the actual LIS. The faster patience-sorting method gives you only the length cleanly. State the O(n²) DP first; for n ≤ 2500 it even passes outright.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [10, 9, 2, 5, 3, 7]Array state
i=3 (5)
2<5 → dp[3]=2
3C · Code with teaching comments
Reference implementation previewpublic int lengthOfLIS(int[] nums) { int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, 1); int best = 1;Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The trick is choosing a subproblem you can recurse on: 'LIS ending at i' is local and composable, whereas 'LIS of the whole array' is not. Whenever the global objective is hard to break down, try anchoring it to 'ending at / using element i' — it's the workhorse framing for subsequence DPs.
ComplexityO(n²) time, O(n) space — For each i we scan all j < i → n + (n−1) + … ≈ n²/2 = O(n²) time. The dp array is O(n) space.
E · Edge cases and pitfalls4nums = [7, 7, 7, 7] — No j satisfies nums[j] < nums[i] (all equal), so every dp[i] stays 1 → answer 1. Strict < is doing the work.Explore edge casesHide edge cases
Edge cases handled
nums = [7, 7, 7, 7]No j satisfies nums[j] < nums[i] (all equal), so every dp[i] stays 1 → answer 1. Strict < is doing the work.
Pitfalls
- Using <= instead of < — turns strictly increasing into non-decreasing.
- Returning dp[n-1] instead of max(dp) — the LIS need not end at the last index.
- Forgetting to initialize dp to 1 — a lone element is already length 1.
Approach 2 of 2 · Optimal
Patience Sorting — tails[] + Binary Search (Optimal)
1Hint 1Explore hintHide hint
The O(n²) DP rescans all earlier elements each step. What if you kept a compact summary that lets you place each new number with a binary search instead?
2Hint 2Explore hintHide hint
Maintain tails[], where tails[k] is the smallest possible tail value of any increasing subsequence of length k+1. This array is always sorted.
3Hint 3Explore hintHide hint
For each x, binary-search the first tail >= x. If none, append x (LIS grew). Otherwise overwrite that tail with x. The answer is len(tails).
A · Core idea
Maintain an array tails where tails[k] is the smallest possible tail of any strictly increasing subsequence of length k+1. Process each number with a binary search; the final length of tails is the LIS length.
Why a smaller tail always dominates. Suppose two increasing subsequences both have length 3, ending in 9 and in 5. The one ending in 5 is strictly better for the future: anything that could extend the 9-ending one can also extend the 5-ending one (since 5 < 9 leaves more room), but not vice versa. So for each length we only ever need to remember the minimum achievable tail — that's exactly tails[k]. Keeping the minimum is what lets us throw away dominated states and collapse the DP.
Why tails stays sorted (so binary search is valid). A longer increasing subsequence must end on a larger value than the increasing subsequence one shorter that it extends, so tails is strictly increasing by construction. That sortedness is what licenses the O(log n) binary search — we're searching a sorted array every step.
The placement rule, and the strict-vs-non-strict knob. For each x, binary-search for the leftmost tail that is ≥ x (bisect_left / lower_bound). If x exceeds every tail, it extends the longest subsequence so we append it. Otherwise we overwrite that first ≥ x tail with x — same length, but now a smaller (better) tail. Using lower_bound (replace first ≥ x) gives strictly increasing; switching to upper_bound (first > x) would allow equal values and solve the non-decreasing variant. That single choice is the entire difference.
The crucial caveat. tails is not a valid subsequence of nums — its contents can be a mix of values that never appeared together in order. Only its length is meaningful. If the interviewer wants the actual subsequence, fall back to the O(n²) DP with parent pointers (or augment patience sorting with index bookkeeping). Say this explicitly; it's a favorite follow-up.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [10, 9, 2, 5, 3, 7, 101, 18]Array state
after 5
5 > all → append
4 (length of tails)C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The leap is realizing that for each subsequence length, only the smallest tail matters — every larger tail is dominated and can be discarded. That reduces an O(n²) 'compare against all predecessors' to an O(log n) 'binary-search into a sorted summary'. The dominance-pruning idea (keep only the non-dominated frontier) is a reusable optimization far beyond LIS.
ComplexityO(n log n) time, O(n) space — n elements, each placed with an O(log n) binary search into tails → O(n log n) time. tails holds at most n values → O(n) space.
E · Edge cases and pitfalls5nums = [7, 7, 7, 7] — Each 7 finds the first tail >= 7 at index 0 and overwrites it; tails stays [7], length 1. bisect_left enforces strictness.Explore edge casesHide edge cases
Edge cases handled
nums = [7, 7, 7, 7]Each 7 finds the first tail >= 7 at index 0 and overwrites it; tails stays [7], length 1. bisect_left enforces strictness.nums = [1, 3, 2]tails: [1] → [1,3] → overwrite 3 with 2 → [1,2]. Length 2. Shows overwrite doesn't lose the answer even though [1,2] isn't the literal LIS [1,3].
Pitfalls
- Using bisect_right / upper_bound — silently solves non-decreasing, wrong on [7,7,7].
- Treating tails as the actual subsequence — only its length is meaningful.
- Appending when you should overwrite (or vice versa) — append only when x exceeds every tail (index == size).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int lengthOfLIS(int[] nums) { int[] tails = new int[nums.length]; int size = 0; for (int x : nums) { int lo = 0, hi = size;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Subarray vs subsequence
A subsequence allows gaps; a subarray must be contiguous. Requiring contiguity reports a far shorter answer — e.g. [0,1,0,3,2,3] gives 2 (contiguous) instead of 4.
Explore the code comparisonHide the code comparison
Subarray vs subsequence
A subsequence allows gaps; a subarray must be contiguous. Requiring contiguity reports a far shorter answer — e.g. [0,1,0,3,2,3] gives 2 (contiguous) instead of 4.
Don't write this
# resets the chain on any dip (treats it as a subarray)
length = 1
for i in range(1, n):
if nums[i] > nums[i-1]:
length += 1
else:
length = 1Write this instead
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)2Wrong binary-search bound
bisect_right (upper_bound) lets equal values append, turning strict LIS into non-decreasing. [7,7,7,7] would wrongly return 4.
Explore the code comparisonHide the code comparison
Wrong binary-search bound
bisect_right (upper_bound) lets equal values append, turning strict LIS into non-decreasing. [7,7,7,7] would wrongly return 4.
Don't write this
i = bisect.bisect_right(tails, x) # allows equal valuesWrite this instead
i = bisect.bisect_left(tails, x) # first tail >= x → strictly increasing3Reading the subsequence off tails[]
tails holds the minimal tail per length, not actual chained elements. Its contents may never co-occur in order; only len(tails) is the answer.
Explore the code comparisonHide the code comparison
Reading the subsequence off tails[]
tails holds the minimal tail per length, not actual chained elements. Its contents may never co-occur in order; only len(tails) is the answer.
Don't write this
return tails; // NOT a valid subsequenceWrite this instead
return size; // only the LENGTH is meaningfulRevise
Carry the pattern into the interview
Pattern to remember
Patience sorting — tails[] + binary search
Code pattern to memorize
tails = []
for x in nums:
i = bisect_left(tails, x) # strict: leftmost >= x
if i == len(tails): tails.append(x)
else: tails[i] = x
return len(tails)Rules to remember
- 1
tails[k]= the smallest possible tail of an increasing subsequence of lengthk+1; the array stays sorted, so binary search applies. - 2For strictly increasing, binary-search with
lower_bound/bisect_left(replace the first element≥ x); for non-decreasing useupper_bound/bisect_right. - 3
tailsis not a real subsequence — its length is the answer, but its contents may never co-occur in nums. - 4If
xis larger than every tail, append (LIS grew); otherwise overwrite the first tail≥ x(keeps future options open). - 5The O(n²) DP (
dp[i] = 1 + max(dp[j] for j
Use this pattern when
- Longest subsequence (non-contiguous) that is monotonic under some order
- Can reduce 'best chain' problems (envelopes, pairs, box stacking) to an LIS after sorting
- n is large enough that O(n²) is too slow → patience + binary search
- Only the LENGTH is needed (binary-search version doesn't reconstruct)
Choose another pattern when
- Contiguous required → that's a subarray problem (Kadane-style), not subsequence
- Need the actual subsequence, not just length → use O(n²) DP with parent pointers
- Longest common subsequence of two arrays → 2-D DP, different recurrence
- Counting the number of LIS → DP carrying both length and count
Interview takeaway
LIS has two canonical answers and you should know both: the O(n²) dp-ending-here DP (intuitive, reconstructable) and the O(n log n) patience-sorting trick (tails[] + binary search). The patience insight — keep the smallest tail per length to leave the most room — recurs across many 'longest chain' problems.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternPatience Sorting / LIS. Many 'longest chain under an order' problems (envelopes, pair chains, box stacking) reduce to LIS after a clever sort. Know the O(n²) DP for reconstruction and the O(n log n) tails+binary-search for length; the dominance-pruning idea generalizes widely.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Russian Doll EnvelopesComing soonSort by width asc, height desc on ties, then run LIS on heights — reduces 2-D nesting to 1-D LIS.
- Number of Longest Increasing SubsequenceComing soonCarry both length and count per index in the O(n²) DP; combine counts when lengths tie.
- Maximum Length of Pair ChainComing soonSort by second element and greedily chain — an LIS-flavored chaining problem.
- Longest Common SubsequenceDifferent shape — 2-D DP over two strings; LIS reduces to LCS against a sorted copy in some variants.