Longest Increasing Subsequence

Medium

💭 Introduction

You’re given an array of integers. Your task is to find the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from the array by deleting some or no elements without changing the order of the remaining elements.

For example, in [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101] with length 4.

Important: The subsequence doesn’t need to be contiguous!

Your goal is to find the length of the longest such subsequence.

🧩 Problem Statement

LeetCode #300 — Longest Increasing Subsequence

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], therefore the length is 4.

🔍 Example 2:

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

Explanation:

The longest increasing subsequence is [0,1,2,3], length = 4.

🔍 Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Explanation:

All elements are equal, so the longest strictly increasing subsequence has length 1.

🧠 Step 1: Understanding the Problem

Let’s clarify what we’re looking for:

Subsequence vs Subarray:

• Subarray: Contiguous elements → [2, 5, 3] in [10, 9, 2, 5, 3, 7]
• Subsequence: Non-contiguous but maintains order → [2, 5, 7] in [10, 9, 2, 5, 3, 7]

Strictly Increasing:

• Each element must be greater than the previous (not equal)
• [1, 2, 2, 3] → LIS is [1, 2, 3], not [1, 2, 2, 3]

Key Question:

At each position, what’s the longest increasing subsequence ending at that position?

🤔 Step 2: The Brute Force Approach

We could generate all possible subsequences and check which ones are increasing:

def lengthOfLIS(nums):
    def is_increasing(subseq):
        for i in range(1, len(subseq)):
            if subseq[i] <= subseq[i-1]:
                return False
        return True
    
    max_length = 0
    n = len(nums)
    
    # Generate all 2^n subsequences
    for mask in range(1 << n):
        subseq = []
        for i in range(n):
            if mask & (1 << i):
                subseq.append(nums[i])
        
        if is_increasing(subseq):
            max_length = max(max_length, len(subseq))
    
    return max_length

Problem: This generates $2^n$ subsequences!

⏱️ Time Complexity: $O(2^n \times n)$

📦 Space Complexity: $O(n)$

🚀 Step 3: Dynamic Programming Approach (O(n²))

Define: dp[i] = length of longest increasing subsequence ending at index i

Key Insight: For each position i, we look at all previous positions j where nums[j] < nums[i], and extend the best subsequence ending at j.

Recurrence relation:

dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]

Base case:

dp[i] = 1  // Each element is a subsequence of length 1 by itself

Answer:

max(dp[0], dp[1], ..., dp[n-1])

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        n = len(nums)
        dp = [1] * n  # Each element is a subsequence of length 1
        
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)

Let’s trace through Example 1: nums = [10, 9, 2, 5, 3, 7, 101, 18]

Index	nums[i]	dp[i]	Explanation
0	10	1	Base case
1	9	1	No smaller element before
2	2	1	No smaller element before
3	5	2	Extends from 2: [2, 5]
4	3	2	Extends from 2: [2, 3]
5	7	3	Extends from 5 or 3: [2, 5, 7] or [2, 3, 7]
6	101	4	Extends from 7: [2, 5, 7, 101]
7	18	4	Extends from 7: [2, 5, 7, 18]

Final answer: max(dp) = 4 ✓

⏱️ Time Complexity: $O(n^2)$

📦 Space Complexity: $O(n)$

⚙️ Step 4: Optimized Approach with Binary Search (O(n log n))

Key Insight: We can maintain an array tails where tails[i] is the smallest tail element of all increasing subsequences of length i+1.

Why does this work?

• If we want to extend subsequences, we prefer those with smaller tail values
• We can use binary search to find where to place each new element

Algorithm:

1. Maintain tails array
2. For each number:
   • If it’s larger than all tails, append it (extends longest subsequence)
   • Otherwise, replace the first tail that’s >= current number (maintains smaller tails)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        
        for num in nums:
            # Binary search for the position to insert/replace
            left, right = 0, len(tails)
            
            while left < right:
                mid = (left + right) // 2
                if tails[mid] < num:
                    left = mid + 1
                else:
                    right = mid
            
            # If left == len(tails), append; otherwise replace
            if left == len(tails):
                tails.append(num)
            else:
                tails[left] = num
        
        return len(tails)

Using Python’s bisect module:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        from bisect import bisect_left
        
        tails = []
        
        for num in nums:
            pos = bisect_left(tails, num)
            if pos == len(tails):
                tails.append(num)
            else:
                tails[pos] = num
        
        return len(tails)

Let’s trace through Example 1: nums = [10, 9, 2, 5, 3, 7, 101, 18]

num	Action	tails	Length
10	Append	[10]	1
9	Replace 10	[9]	1
2	Replace 9	[2]	1
5	Append	[2, 5]	2
3	Replace 5	[2, 3]	2
7	Append	[2, 3, 7]	3
101	Append	[2, 3, 7, 101]	4
18	Replace 101	[2, 3, 7, 18]	4

Final answer: len(tails) = 4 ✓

Important: The tails array doesn’t represent the actual LIS, just its length!

⏱️ Time Complexity: $O(n \log n)$

📦 Space Complexity: $O(n)$

🎯 Step 5: Reconstructing the Actual LIS

If you need the actual subsequence (not just its length), use the DP approach with backtracking:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        
        n = len(nums)
        dp = [1] * n
        parent = [-1] * n  # Track previous element in LIS
        
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j
        
        # Find the index with maximum length
        max_length = max(dp)
        max_index = dp.index(max_length)
        
        # Reconstruct the LIS
        lis = []
        current = max_index
        while current != -1:
            lis.append(nums[current])
            current = parent[current]
        
        return lis[::-1]  # Reverse to get correct order

🎯 Key Insights

1. Subsequence vs Subarray: Subsequence doesn’t need to be contiguous

2. DP State Definition: dp[i] = longest increasing subsequence ending at index i

3. Two Solutions: O(n²) DP is intuitive; O(n log n) binary search is optimal

4. Tails Array Trick: Maintain smallest tail for each length to enable binary search

5. Strictly Increasing: Use < not <= for comparison

📊 Complexity Summary

Approach	Time	Space	Notes
Brute Force	$O(2^n \times n)$	$O(n)$	Generate all subsequences
DP (O(n²))	$O(n^2)$	$O(n)$	Easy to understand
Binary Search	$O(n \log n)$	$O(n)$	Optimal solution
With Reconstruction	$O(n^2)$	$O(n)$	Returns actual LIS

🌟 Edge Cases to Consider

1. Empty array: [] → 0
2. Single element: [1] → 1
3. All equal: [5, 5, 5, 5] → 1
4. Strictly decreasing: [5, 4, 3, 2, 1] → 1
5. Already sorted: [1, 2, 3, 4, 5] → 5
6. Negative numbers: [-10, -5, 0, 5] → 4

💡 Common Mistakes

1. Confusing subsequence with subarray: Subsequence can skip elements
2. Using <= instead of <: Problem asks for strictly increasing
3. Thinking tails is the actual LIS: It’s not! It just tracks lengths
4. Wrong binary search bounds: Be careful with left/right pointers
5. Forgetting to return max(dp): Answer is not dp[-1]

🔍 Variations of This Problem

1. Longest Decreasing Subsequence — Reverse the comparison
2. Number of Longest Increasing Subsequences — Count all LIS
3. Russian Doll Envelopes — 2D version of LIS
4. Maximum Length of Pair Chain — Similar pattern with pairs
5. Longest Arithmetic Subsequence — With arithmetic progression constraint

🧮 Step 6: Understanding the Binary Search Approach

Why does replacing elements work?

Consider tails = [2, 5, 7] and we encounter 3:

• We replace 5 with 3 → tails = [2, 3, 7]
• This doesn’t change the length (still 3)
• But now we have a better foundation for future extensions!
• If we see 4 next, we can extend: [2, 3, 4] vs [2, 5, 4] (invalid)

Invariant maintained:

• tails[i] is always the smallest possible tail for length i+1
• This greedy choice maximizes our chances of extending the sequence

💡 Related Problems

• Maximum Subarray - Contiguous version
• House Robber - Linear DP pattern
• Longest Common Subsequence - 2D DP variant
• Edit Distance - Similar DP thinking
• Russian Doll Envelopes - 2D LIS

🏆 Why This Problem Matters

1. Interview favorite: Extremely common in technical interviews
2. Multiple solutions: Tests ability to optimize from O(n²) to O(n log n)
3. Binary search mastery: Non-obvious application of binary search
4. DP fundamentals: Classic example of optimal substructure
5. Real-world applications: Version control, data compression, bioinformatics

🎓 Key Takeaways

• Start with DP: The O(n²) solution is intuitive and correct
• Optimize with binary search: The O(n log n) solution is elegant but less obvious
• Understand the state: dp[i] represents LIS ending at position i
• Greedy + DP: The binary search approach combines greedy choice with DP thinking
• Practice both: Know when to use each approach based on constraints

📝 Interview Tips

1. Clarify requirements: Strictly increasing? Can elements repeat?
2. Start with O(n²): It’s easier to explain and code
3. Mention optimization: Show you know the O(n log n) solution exists
4. Test edge cases: Empty array, single element, all equal
5. Explain the tails array: If using binary search, explain why it works