Blind 75 - problem 22 : Longest Increasing Subsequence

 

Longest Increasing Subsequence – LeetCode Solution with Detailed Explanation

Problem Statement

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

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

Example 1:

Input:

nums = [10,9,2,5,3,7,101,18]

Output:

4

Explanation:
The longest increasing subsequence is [2,3,7,101], and its 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], and its length is 4.

---

Example 3:

Input:

nums = [7,7,7,7,7,7,7]

Output:

1

Explanation:
All elements are the same, so the longest subsequence has only one element.

---

Optimal Approach – Dynamic Programming (DP) with Binary Search

We use Dynamic Programming with Binary Search to solve this problem in O(n log n) time.

Key Observations:

1. We maintain an array sub, where sub[i] represents the smallest element that could be the end of an increasing subsequence of length i+1.
2. For each nums[i]:
   • Use Binary Search (lower_bound) to find where nums[i] fits in sub.
   • If it extends sub, append nums[i].
   • Otherwise, replace an element in sub to keep it minimal.
3. The length of sub gives the length of the longest increasing subsequence.

---

LeetCode-Compatible C++ Code Implementation

#include <vector>
#include <algorithm>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        std::vector<int> sub;

        for (int num : nums) {
            auto it = std::lower_bound(sub.begin(), sub.end(), num);
            if (it == sub.end()) {
                sub.push_back(num);
            } else {
                *it = num;
            }
        }

        return sub.size();
    }
};

---

Step-by-Step Explanation of Code

1. Initialize an empty array sub
   • This stores the elements forming the longest increasing subsequence.
2. Iterate through nums
   • Use lower_bound to find the position where num can replace an element in sub.
   • If num is greater than all elements in sub, append it.
   • Otherwise, replace an existing element to keep sub minimal.
3. Return the length of sub, which represents the longest increasing subsequence.

---

Dry Run / Execution Steps

Input: nums = [10,9,2,5,3,7,101,18]

Step-by-Step Execution:

Step	num	sub (LIS at each step)	Explanation
1	10	[10]	Start LIS
2	9	[9]	Replace 10 with 9
3	2	[2]	Replace 9 with 2
4	5	[2,5]	Extend LIS
5	3	[2,3]	Replace 5 with 3
6	7	[2,3,7]	Extend LIS
7	101	[2,3,7,101]	Extend LIS
8	18	[2,3,7,18]	Replace 101 with 18

Final Output: 4 (LIS is [2,3,7,18])

---

Alternative Approaches & Why Not?

1. Brute Force – Recursion

• Try all subsequences recursively.
• Time Complexity: O(2^n) (Exponential)
• Space Complexity: O(n) (Recursion depth)
• Why Not? Too slow for large inputs.

2. Dynamic Programming (O(n²))

• Maintain a dp array where dp[i] stores LIS ending at i.
• Use nested loops to compute dp[i] = max(dp[j]) + 1 for j < i.
• Time Complexity: O(n²)
• Space Complexity: O(n)
• Why Not? Slower than O(n log n) solution.

---

Best Solution & Why It’s Best

Approach	Time Complexity	Space Complexity	Optimal?
Brute Force	O(2^n)	O(n)	❌ No (Too slow)
DP (O(n²))	O(n²)	O(n)	✅ Faster but suboptimal
DP + Binary Search	O(n log n)	O(n)	✅ Best

The Binary Search Approach (O(n log n)) is optimal because it efficiently builds sub with minimal replacements.

---

Conclusion

• Best Approach: DP + Binary Search (O(n log n))
• Why? Efficient, simple, and avoids extra computations.
• Similar problems to practice:
  • Longest Common Subsequence
  • Longest Increasing Subarray
  • Number of Longest Increasing Subsequences

🚀 This is the fastest way to solve Longest Increasing Subsequence!