Start with the quadratic recurrence
Define dp[i] as the length of the longest increasing subsequence that ends at index i. Anchoring the state to an endpoint rather than to a prefix is the move that makes the recurrence expressible, because an increasing subsequence can only be extended by comparing against its final element, and a state that says merely "the best answer among the first i elements" does not record what that final element was.
The transition scans backwards: dp[i] = 1 + max(dp[j]) over every j < i with nums[j] < nums[i], or 1 if no such j exists. The answer is the maximum over the whole array, not dp[n-1], since the longest chain need not end at the last element. That is O(n²) time and O(n) space, and it is a complete, correct answer that you should write down and offer before optimising. Interviewers do ask for the faster version, but starting there and getting the invariant slightly wrong is a much worse outcome than arriving at it in two steps.
What the faster version actually stores
Keep an array tails, where tails[j] is the smallest value that can end an increasing subsequence of length j + 1 among the elements processed so far. size is how many slots are in use, which is the best length found so far.
Two consequences follow, and both matter. First, tails is strictly increasing: a chain of length four ends no lower than the best chain of length three, because dropping the last element of the four-chain gives a three-chain with a smaller tail. That monotonicity is what licenses a binary search over it, and it is the claim to state out loud, because without it the algorithm is unexplained.
Second, preferring the smallest possible tail is never a mistake. A lower tail accepts every future element a higher tail would accept, and possibly more, so replacing a tail can only improve your options for extending that length later. It cannot shorten anything already found, because the lengths recorded in the other slots are untouched.
So each new element does exactly one of two things. If it exceeds every tail, it extends the longest chain and occupies a new slot. Otherwise it replaces the smallest tail that is greater than or equal to it, improving the prospects for that length without changing any length.
int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int lo = 0, hi = size;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
if (lo == size) size++;
}
return size;
}
Time is O(n log n): one binary search over at most size slots per element. Space is O(n) for the tails array, and in practice it is only ever size entries deep.
Note the search is written by hand. Arrays.binarySearch returns an insertion point only when the key is absent, and its behaviour with duplicate keys is explicitly unspecified — the Javadoc says there is no guarantee which of several equal elements is found. Since duplicates are precisely the case that decides strict versus non-decreasing here, borrowing the library method makes the one interesting branch depend on unspecified behaviour.
The claim that trips people up
tails is not a subsequence of the input and printing it is wrong. It is a set of independent best-known endpoints, assembled from elements that may appear in any order and may never have coexisted in a single chain. Take [10, 9, 2, 5, 3, 7, 101, 18]. The answer is length 4, and [2, 3, 7, 18] is one valid subsequence — but at the end of the loop tails holds [2, 3, 7, 18] only by coincidence of this input. With [4, 5, 6, 1] the final contents are [1, 5, 6], and 1 follows 6 in the original array, so those three values are not a chain at all. The length is right; the array is not the answer.
That is why recovering the subsequence needs extra bookkeeping. Record which input index landed in each slot, and for each element the index that occupied the slot below it at the time — that is a legitimate predecessor, because it ends a chain one shorter with a value strictly smaller.
There is usually more than one longest subsequence, so this reconstructs a longest one. If the interviewer wants a specific tie-break, that is a different problem and worth clarifying rather than assuming yours matches.
Strict versus non-decreasing is one comparison
The wording decides the search predicate, and both are one character apart. For a strictly increasing subsequence you want the lower bound — the first slot whose tail is greater than or equal to x — so an equal value replaces rather than extends, which correctly refuses to chain two identical numbers. For a non-decreasing subsequence you want the upper bound, the first slot strictly greater than x, so equal values do extend. In the loop above that is the difference between tails[mid] < x and tails[mid] <= x.
Getting this backwards produces answers that are off by exactly the number of runs of duplicates, which passes any test input with distinct values. If the problem statement says "increasing" without qualification, ask which one is meant instead of guessing, and then say which comparator you chose and why.
Where else this shape appears
The technique is patience sorting: each slot is the top card of a pile, a new card goes on the leftmost pile whose top it can cover, and the number of piles is the answer. Recognising that is what lets you spot the problem when it arrives disguised. Nesting one rectangle inside another, stacking envelopes, wiring pairs of ports without crossings, finding the minimum number of arrows for a set of intervals — all of these reduce to sorting on one dimension and running this on the other.
The reduction is where the difficulty lives, and the tie-break in the sort is where those reductions go wrong: if two items share the first coordinate and equality is not allowed in the answer, they must be ordered so that they cannot chain, which usually means sorting the second coordinate descending within a tie.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).