Longest Increasing Subsequence Solution

Problem

Given an array of integers, find the length of the longest subsequence that is strictly increasing. A subsequence is formed by deleting some (or no) elements from the array without changing the order of the remaining elements — unlike a subarray, the chosen elements do not need to be adjacent.

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The subsequence [2, 3, 7, 101] (or [2, 3, 7, 18]) has length 4 and is strictly increasing.

Intuition

The core question is: for each position in the array, what is the longest increasing subsequence that ends here? Once we know that for every position, the answer is just the maximum across all positions. This bottom-up structure lets us reuse results — the LIS ending at index i is at most one longer than the best LIS ending at any earlier index whose value is smaller than nums[i]. Going further, we can observe that for each possible LIS length, maintaining the smallest possible last element maximizes our ability to extend that subsequence — and binary search lets us find the right slot in O(log n) instead of O(n).

Approach 1 — DP (O(n²))

For each index i, scan all previous indices to find the longest IS that can be extended by nums[i].

Create a dp array of length n where dp[i] = length of the LIS ending at index i. Initialize every entry to 1 (each element alone is a valid IS of length 1).
For each index i from 1 to n-1, scan every earlier index j from 0 to i-1.
If nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1) — we can extend the IS ending at j by appending nums[i].
After filling dp, return max(dp) — the longest IS may end at any index, not necessarily the last one.

1def lengthOfLIS(nums: list[int]) -> int:
2    dp = [1] * len(nums)  # LIS ending at each position starts at length 1
3
4    for i in range(1, len(nums)):
5        for j in range(i):
6            if nums[j] < nums[i]:  # nums[i] can extend any IS that ends at nums[j]
7                dp[i] = max(dp[i], dp[j] + 1)
8
9    return max(dp)

Time: O(n²) — for each of the n elements, we scan all preceding elements.
Space: O(n) — the dp array stores one value per index.

Approach 2 — Binary Search (O(n log n))

Instead of tracking the LIS length at every index, maintain a tails list where tails[k] holds the smallest possible tail element of any increasing subsequence of length k+1. Because this list is always sorted, we can use binary search.

Initialize tails = [].
For each num in nums, binary search tails for the first position where tails[pos] >= num (lower bound / bisect_left).
If pos == len(tails), append num — it is larger than every tail, so it extends the longest IS found so far.
Otherwise, replace tails[pos] = num — a smaller tail at this IS length opens more opportunities for future extensions.
Return len(tails) — each index in tails accounts for exactly one unit of IS length.

Trace on [10, 9, 2, 5, 3, 7, 101, 18]:

10 → tails = [10]
9 → replace pos 0 → tails = [9]
2 → replace pos 0 → tails = [2]
5 → append → tails = [2, 5]
3 → replace pos 1 → tails = [2, 3]
7 → append → tails = [2, 3, 7]
101 → append → tails = [2, 3, 7, 101]
18 → replace pos 3 → tails = [2, 3, 7, 18]
→ return 4 ✓

Note: tails = [2, 3, 7, 18] does not represent an actual LIS — the array [2, 3, 7, 101] or [2, 3, 7, 18] is the real answer. tails is purely a bookkeeping structure for counting length.

1import bisect
2
3def lengthOfLIS(nums: list[int]) -> int:
4    tails = []  # tails[k] = smallest tail of any IS of length k+1
5
6    for num in nums:
7        # find the leftmost position where tails[pos] >= num
8        pos = bisect.bisect_left(tails, num)
9        if pos == len(tails):
10            tails.append(num)    # num extends the longest IS found so far
11        else:
12            tails[pos] = num     # replace to keep this tail as small as possible
13
14    return len(tails)

Time: O(n log n) — one binary search per element over a list that grows at most to length n.
Space: O(n) — the tails list holds at most n elements.

Complexity Summary

Approach	Time	Space	When to use
DP	O(n²)	O(n)	When n is small (≤ 2500) or you need to reconstruct the actual subsequence
Binary Search	O(n log n)	O(n)	When n is large (up to 10⁵) and only the length is needed

Common Mistakes

Confusing "subsequence" with "subarray" — elements can be non-adjacent; [2, 3, 7] is a valid subsequence of [10, 9, 2, 5, 3, 7] even though they are not next to each other.
Initializing dp[i] = 0 instead of 1 — every single element is already a valid IS of length 1, so the baseline is 1, not 0.
Returning dp[n-1] instead of max(dp) — the longest IS doesn't have to end at the last element; [10, 9, 2, 5, 3, 7, 1] has its LIS ending at index 5, not 6.
Using bisect_right instead of bisect_left — bisect_right (upper bound) would allow a value equal to an existing tail, incorrectly treating a non-strictly-increasing step as valid.
Assuming tails represents the actual LIS — after processing [10, 9, 2, 5, 3, 7, 101, 18], tails = [2, 3, 7, 18], but the elements were never adjacent in the original array in that order; tails is a length-counting tool, not a sequence.

Longest Increasing Subsequence — Solution