Log inSign up
mediumLeetCodeNot Started

Longest Increasing Subsequence

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

### Example 1 - Input: nums = [10, 9, 2, 5, 3, 7, 101, 18] - Output: 4 - Explanation: The longest increasing subsequence is [2, 3, 7, 101] (or [2, 5, 7, 101], [2, 3, 7, 18]), therefore the length is 4.

### Example 2 - Input: nums = [0, 1, 0, 3, 2, 3] - Output: 4

### Example 3 - Input: nums = [7, 7, 7, 7, 7, 7, 7] - Output: 1

Constraints:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Derive the classic O(n2) DP recurrence.
  • Master the Patience Sorting archetype with binary search.
  • Understand why replacing elements in tails maintains the correct LIS length.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding longest increasing subsequence.
  • Array elements with no deletion penalties.
  • Optimization from O(n2) to O(n log n).

Algorithmic Decision Tree:

  • Strictly increasing -> use lower_bound (first element >= x).
  • Non-decreasing -> use upper_bound (first element > x).

Connected Patterns:

Russian Doll EnvelopesLongest Bitonic SubsequenceNumber of Longest Increasing Subsequence

1. Recursive Exhaustive Search

Intuition

For each element, decide whether to include it in the increasing subsequence (if greater than previous chosen element) or skip it.

Algorithm

  1. Define dfs(idx, prevIdx).
  2. If idx == nums.length, return 0.
  3. Option 1: skip dfs(idx + 1, prevIdx).
  4. Option 2: if prevIdx == -1 or nums[idx] > nums[prevIdx]: 1 + dfs(idx + 1, idx).
  5. Return max(Option 1, Option 2).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int dfs(int idx, int prevIdx, const vector<int>& nums) {
8 if (idx == (int)nums.size()) return 0;
9 int skip = dfs(idx + 1, prevIdx, nums);
10 int take = 0;
11 if (prevIdx == -1 || nums[idx] > nums[prevIdx]) {
12 take = 1 + dfs(idx + 1, idx, nums);
13 }
14 return max(skip, take);
15}
16
17int lengthOfLISRec(vector<int>& nums) {
18 return dfs(0, -1, nums);
19}
20
21int main() {
22 vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
23 cout << "LIS (Recursive): " << lengthOfLISRec(nums) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. Dynamic Programming Tabulation O(n^2)

Intuition

Build array dp of size n where dp[i] = 1 + max_{j < i, nums[j] < nums[i]}(dp[j]).

Algorithm

  1. Create dp array of size n filled with 1.
  2. Initialize maxLen = 1.
  3. For i = 1 to n - 1:
  4. For j = 0 to i - 1:
  5. If nums[j] < nums[i]:
  6. dp[i] = max(dp[i], 1 + dp[j])
  7. maxLen = max(maxLen, dp[i])
  8. Return maxLen.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int lengthOfLIS_DP(vector<int>& nums) {
8 if (nums.empty()) return 0;
9 int n = nums.size();
10 vector<int> dp(n, 1);
11 int maxLen = 1;
12
13 for (int i = 1; i < n; i++) {
14 for (int j = 0; j < i; j++) {
15 if (nums[j] < nums[i]) {
16 dp[i] = max(dp[i], 1 + dp[j]);
17 }
18 }
19 maxLen = max(maxLen, dp[i]);
20 }
21 return maxLen;
22}
23
24int main() {
25 vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
26 cout << "LIS (O(n^2) DP): " << lengthOfLIS_DP(nums) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n) for dp array

3. Patience Sorting with Binary Search O(n log n)

Intuition

Maintain a tails array where tails[i] stores the minimum tail value of all increasing subsequences of length i+1. Update via binary search in O(log n) per element.

Algorithm

  1. Initialize empty array tails.
  2. For each x in nums:
  3. Binary search (lower_bound) for x in tails.
  4. If x is greater than all elements, append x to tails.
  5. Otherwise, replace the element at the found index with x.
  6. Return tails.length.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int lengthOfLISOptimal(vector<int>& nums) {
8 vector<int> tails;
9 for (int x : nums) {
10 auto it = lower_bound(tails.begin(), tails.end(), x);
11 if (it == tails.end()) {
12 tails.push_back(x);
13 } else {
14 *it = x;
15 }
16 }
17 return tails.size();
18}
19
20int main() {
21 vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
22 cout << "LIS (Optimal O(n log n)): " << lengthOfLISOptimal(nums) << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(n log n)
  • Space complexity: O(n) for tails array

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive ChoiceO(2^n)O(n)Exhaustive branching over take vs skip.Redundant subsequences
2.O(n2) Tabulation DPO(n^2)O(n)dp[i] = 1 + max(dp[j]) for j < i.Inner comparison loop
3.Patience Sorting O(n log n)OptimalO(n log n)O(n)Binary search on smallest tail values array.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using bisect_right instead of bisect_left for strictly increasing (bisect_right permits duplicate elements, solving Non-Decreasing Subsequence).

Pitfall 2:

Assuming tails array contains the actual elements of the subsequence.

Crucial Edge Cases to Validate:

  • All elements identical: LIS is 1.
  • Strictly decreasing: LIS is 1.
  • Strictly increasing: LIS is n.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start with the O(n2) DP to demonstrate core problem understanding, then immediately state: 'We can optimize this to O(n log n) using Patience Sorting with binary search.' Interviewers love this two-tier demonstration.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Does the tails array in the O(n log n) Patience Sorting algorithm store the actual Longest Increasing Subsequence itself?

Back to DSA Sheet