Longest Increasing Subsequence LeetCode Solution

The longest increasing subsequence leetcode problem (#300) sits at a unique crossroads in your interview prep journey. It starts as a straightforward dynamic programming exercise, but it hides an elegant O(n log n) optimization that separates good candidates from great ones. If you can explain both approaches clearly, you demonstrate not just DP fluency but genuine algorithmic depth.

LIS asks a deceptively simple question: given an integer array, find the length of the longest strictly increasing subsequence. The twist that trips up many candidates is the word "subsequence" — elements do not need to be contiguous. You can skip elements as long as the ones you pick form a strictly increasing sequence.

This problem appears frequently at Google, Amazon, and Microsoft interviews precisely because it tests multiple layers of understanding. The brute-force recursive approach is exponential. The DP solution is quadratic. And the optimal solution uses binary search on a cleverly maintained array, dropping the complexity to O(n log n). Each step up reveals whether you truly understand what you are doing or just memorized a template.

LeetCode 300 gives you an unsorted array of integers and asks for the length of the longest strictly increasing subsequence. For example, given [10, 9, 2, 5, 3, 7, 101, 18], the answer is 4 because the subsequence [2, 3, 7, 101] (or [2, 3, 7, 18], or [2, 5, 7, 101]) has length 4.

The key distinction is between a subsequence and a subarray. A subarray must be contiguous — consecutive elements in the original array. A subsequence can skip elements, maintaining only relative order. This means [2, 5, 7, 101] is a valid subsequence of the input even though 5 and 7 are not adjacent in the original array.

Strictly increasing means each element must be greater than the previous one — not equal. If the array is [1, 3, 3, 5], the LIS is [1, 3, 5] with length 3, not [1, 3, 3, 5]. This detail matters in edge cases and changes how you handle duplicates in your solution.

The classic LIS dynamic programming solution defines dp[i] as the length of the longest increasing subsequence that ends at index i. Every element by itself forms a subsequence of length 1, so you initialize every dp[i] to 1.

For each index i, you look at every previous index j where j < i. If nums[j] < nums[i], then nums[i] can extend the subsequence ending at j. You update dp[i] = max(dp[i], dp[j] + 1). After filling the entire dp array, the answer is the maximum value across all dp[i].

Here is how the recurrence works on [10, 9, 2, 5, 3, 7, 101, 18]. Start with dp = [1, 1, 1, 1, 1, 1, 1, 1]. When you reach index 3 (value 5), you check all previous elements — 10, 9, and 2. Only 2 < 5, so dp[3] = dp[2] + 1 = 2. When you reach index 5 (value 7), both 2, 5, and 3 are smaller, giving dp[5] = max(dp[2]+1, dp[3]+1, dp[4]+1) = 3.

The time complexity is O(n²) because of the nested loop — for each element, you scan all previous elements. Space complexity is O(n) for the dp array. This solution is perfectly acceptable in most interviews and is what interviewers expect as your first approach.

The O(n log n) solution for the longest increasing subsequence leetcode problem uses a brilliant insight called patience sorting. Instead of tracking the LIS ending at each index, you maintain a "tails" array where tails[i] represents the smallest possible tail element of all increasing subsequences of length i + 1.

The algorithm works as follows. For each element in the input array, you binary search the tails array to find the leftmost position where tails[pos] >= current element. If the element is larger than all tails, append it — you have found a longer subsequence. If not, replace tails[pos] with the current element, because you have found a smaller tail for a subsequence of that length.

Why does this work? The tails array is always sorted, which is what makes binary search possible. By replacing a tail with a smaller value, you are not changing any existing subsequence — you are recording that a subsequence of that length can now end with a smaller element, opening up more possibilities for future extensions.

The time complexity drops to O(n log n) because you process each of the n elements with a binary search that takes O(log n). Space complexity remains O(n) for the tails array. The length of the tails array at the end equals the length of the LIS.

Let us trace the O(n log n) tails algorithm step by step on the classic example [10, 9, 2, 5, 3, 7, 101, 18] to see patience sorting in action.

Process 10: tails is empty, so append 10. tails = [10]. Process 9: binary search finds 10 >= 9, replace tails[0]. tails = [9]. Process 2: binary search finds 9 >= 2, replace tails[0]. tails = [2]. Notice how the tails array keeps shrinking the minimum — we now know an increasing subsequence of length 1 can end as small as 2.

Process 5: 5 > 2 (all tails), so append. tails = [2, 5]. Process 3: binary search finds 5 >= 3, replace tails[1]. tails = [2, 3]. We still have a subsequence of length 2, but now it ends at 3 instead of 5 — a better starting point for future growth.

Process 7: 7 > 3 (all tails), so append. tails = [2, 3, 7]. Process 101: 101 > 7, append. tails = [2, 3, 7, 101]. Process 18: binary search finds 101 >= 18, replace tails[3]. tails = [2, 3, 7, 18]. Final tails length is 4, which equals the LIS length.

Notice that tails = [2, 3, 7, 18] is not necessarily the actual LIS — it is a valid one here, but in general, the tails array represents the optimal tail values, not the actual subsequence. Getting the actual subsequence requires additional bookkeeping.

Before you consider this problem fully solved, think through the edge cases that can trip you up. If the array is strictly decreasing like [5, 4, 3, 2, 1], the LIS is 1 — every element by itself. If the array is already sorted like [1, 2, 3, 4, 5], the LIS equals the array length. Both cases should be handled correctly by your algorithm without special logic.

Duplicate elements are another subtle trap. For [1, 3, 3, 5], the LIS is 3 (not 4) because the problem requires strictly increasing, not non-decreasing. Make sure your binary search uses lower bound (leftmost position where tails[pos] >= num), not upper bound.

LeetCode has several related problems that extend the LIS concept. Number of Longest Increasing Subsequences (#673) asks you to count how many distinct LIS exist — this requires tracking both lengths and counts in your DP. Russian Doll Envelopes (#354) is a 2D extension where you sort by one dimension and apply LIS on the other. Longest Increasing Subsequence II (#2407) adds a constraint on the difference between consecutive elements.

LIS is more than just another DP problem — it is a masterclass in optimization thinking. The journey from brute-force O(2^n) to O(n²) DP to O(n log n) binary search mirrors exactly the kind of thought process interviewers want to see. You start with a correct but slow approach, identify the bottleneck, and apply a clever data structure insight to eliminate redundant work.

The patience sorting technique used in the O(n log n) solution is a pattern that appears in other problems too. Whenever you need to maintain a sorted structure while processing elements one at a time, binary search on a dynamically maintained array is a powerful tool. This same idea shows up in problems involving envelopes, scheduling, and sequence alignment.

If you are preparing for coding interviews, practice both the O(n²) and O(n log n) approaches until you can write them from memory. Start with the DP solution to show correctness, then offer the binary search optimization to demonstrate depth. YeetCode flashcards can help you drill both approaches using spaced repetition, so the patterns stick when it matters most.