Longest Increasing Subsequence
O(n^2) DP then the O(n log n) trick.
Longest Increasing Subsequence is a free Coding Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What an LIS Is
A subsequence keeps order but skips elements. The longest increasing one is the longest such run that strictly rises.
a = [3, 1, 4, 1, 5, 9, 2]Subsequence, Not Subarray
Unlike a subarray, an LIS need not be contiguous. You may jump over smaller numbers to keep the chain growing.
The O(n^2) DP State
Let dp[i] be the LIS length that ends at index i. Every element is at least a length-one subsequence by itself.
dp = [1] * nThe O(n^2) Transition
For each i, look at every earlier j. If a[j] is smaller, extend: dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)Read Off the Answer
The result is the largest value in the table, since the LIS can end anywhere, not only at the last index.
answer = max(dp)Why O(n^2) Can TLE
The double loop costs O(n squared). For n near 100000 that is far too slow and earns a time-limit verdict.
The Patience Idea
The faster method keeps a list of the smallest possible tail for each subsequence length, like patience sorting.
tails = []Use bisect to Place
For each number, binary-search where it fits among the tails with bisect_left, giving O(n log n) total.
from bisect import bisect_leftExtend or Replace
If the slot is past the end, append to grow the LIS. Otherwise overwrite that tail with the smaller value.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xLength Lives in tails
When the scan ends, len(tails) is the LIS length. The list itself is not always the subsequence, only its length is exact.
answer = len(tails)Strict vs Non-Decreasing
For a non-decreasing variant, swap to bisect_right so equal values can extend the chain.
from bisect import bisect_rightQuick Check
Which method finds the LIS length in O(n log n)?
Recap: From n^2 to n log n
You can now solve LIS two ways. The O(n^2) DP is simple; the tails-plus-bisect method scales to large inputs and beats the time limit.
Frequently asked questions
Is the “Longest Increasing Subsequence” lesson free?
Yes — the full text of “Longest Increasing Subsequence” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Longest Increasing Subsequence”?
O(n^2) DP then the O(n log n) trick. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Longest Increasing Subsequence” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Memoization vs Tabulation
- Define State and Transition
- Climbing Stairs & Coin Combinations
- Longest Increasing Subsequence