What is the time complexity of longest increasing subsequence?

Best case O(n log n) patience. Worst case O(n²) DP. Space complexity is O(n). tails[] stays sorted, so the update position is found by binary search.

Longest increasing subsequence

medium

dp[i] means 'ending exactly at i' - anchoring the subproblem is what makes the recurrence work. Then switch to patience sorting and watch binary search remove the inner loop.

Best O(n log n) patienceWorst O(n²) DPSpace O(n)

Loading the longest increasing subsequence engine…

Where to go next

Longest common subsequence

medium

Match means diagonal; mismatch means the better of two.

Lower and upper bound

medium

The half-open variant that handles duplicates.

Kadane's algorithm

medium

One decision, repeated n times.