Longest Increasing Subsequence

• Difficulty: Medium
• Topics: Array, Binary Search, Dynamic Programming
• Link: https://leetcode.com/problems/longest-increasing-subsequence/

Problem Description

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

Example 3:

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

Constraints:

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

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Solution

1. Problem Deconstruction

Technical Version
Given an array nums of integers, determine the maximum length of any subsequence where each element is strictly greater than its predecessor. A subsequence is derived by deleting elements without changing order.

Beginner Version
From a list of numbers, pick as many as possible in order (not necessarily next to each other) where each number is bigger than the one before. Find the longest such sequence’s length.

Mathematical Formulation
Let S = [s₁, s₂, ..., sₖ] be a subsequence of nums where s₁ < s₂ < ... < sₖ. Compute:

$$\max_{S \subseteq \text{nums}} |S|$$

Constraint Analysis

1. Array length ≤ 2500:
   • Limits brute-force O(2ⁿ) approaches.
   • O(n²) DP (6M operations) is feasible.
   • Follow-up requires O(n log n) (optimal).
2. Values ∈ [-1e4, 1e4]:
   • No impact on algorithm choice.
   • Handled via standard comparisons.
3. Strictly increasing:
   • Duplicate values in nums can’t appear in the subsequence.
   • Edge case: All elements equal → answer = 1.

---

2. Intuition Scaffolding

Analogies

1. Real-World (Construction): Building the tallest tower where each block must be larger than the one below.
2. Gaming (RPG): Collecting power-ups in order of increasing strength to maximize sequence length.
3. Math (Chain Theory): Finding the longest totally ordered subset in a partially ordered set.

Common Pitfalls

1. Greedy on Smallest Elements: Picking the earliest small numbers might block longer sequences.
2. Confusing Subarray/Subsequence: Subsequences don’t require continuity.
3. Ignoring Strictness: Duplicates (e.g., [2,2]) yield length 1, not 2.
4. DP Initialization Errors: Forgetting to initialize all lengths to 1.
5. Binary Search Misuse: Incorrectly replacing tails in O(n log n) approach.

---

3. Approach Encyclopedia

Brute Force (Recursive)

• Generate all 2ⁿ subsequences, check increasing property.
• Time: O(2ⁿ) → Impossible for n=2500.

Dynamic Programming (O(n²))
Pseudocode:

def lis_dp(nums):  
    dp = [1] * len(nums)  
    for i in range(len(nums)):  
        for j in range(i):  
            if nums[i] > nums[j]:  
                dp[i] = max(dp[i], dp[j] + 1)  
    return max(dp)  

Complexity:

• Time: O(n²) → ∑₀ⁿ⁻¹ i = n(n-1)/2
• Space: O(n) → DP array.
  Visualization:

nums: [10, 9, 2, 5]  
dp:   [1, 1, 1, 1] → After j loops:  
dp:   [1, 1, 1, 2] (since 5 > 2)  

Optimal (Patience Sorting, O(n log n))
Pseudocode:

import bisect  
def lis_optimal(nums):  
    tails = []  
    for num in nums:  
        idx = bisect.bisect_left(tails, num)  
        if idx == len(tails):  
            tails.append(num)  
        else:  
            tails[idx] = num  
    return len(tails)  

Complexity Proof:

• Each of n elements triggers a binary search (O(log k), k ≤ n).
• Total: O(n log n). Space: O(n).
  Visualization:

nums: [3, 4, 1, 2]  
tails progression:  
3 → [3]  
4 → [3,4]  
1 → [1,4]  
2 → [1,2]  
Final length = 2 (correct LIS: [3,4] or [1,2])  

---

4. Code Deep Dive

Optimal Code Annotations

import bisect  
def lengthOfLIS(nums):  
    tails = []  # Tracks smallest possible tail of increasing subsequences  
    for num in nums:  
        idx = bisect.bisect_left(tails, num)  # Find insertion point  
        if idx == len(tails):  
            tails.append(num)  # Extend longest subsequence  
        else:  
            tails[idx] = num  # Optimize future sequences  
    return len(tails)  # Length of longest found  

Edge Case Handling

1. All Elements Equal (Ex 3):
   • bisect_left finds index 0 every time → tails stays [7].
2. Strictly Decreasing (Ex 1):
   • Each new num replaces prior tails → final len=1.
3. Interleaved Values (Ex 2):
   • Tails evolves to [0,1,2,3] via replacements.

---

5. Complexity War Room

Hardware Analysis

• For n=2500:
  • O(n²) → ~6M operations (fast on modern CPUs).
  • O(n log n) → ~2500*11 ≈ 27.5K operations (negligible).

Industry Comparison

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(2ⁿ)	O(n)	5/10	❌
DP	O(n²)	O(n)	9/10	✅ (Small n)
Optimal	O(n log n)	O(n)	7/10	✅ (Recommended)

---

6. Pro Mode Extras

Variants

1. Longest Non-Decreasing Subsequence:
   • Replace bisect_left with bisect_right.
2. LC 123 (Two Transactions):
   • Extend DP to track buy/sell states.

Interview Cheat Sheet

• First Mention: “This is solvable in O(n log n) via patience sorting.”
• Key Insight: “Maintain tails of smallest possible values for each subsequence length.”
• Edge Cases: “All duplicates or descending order → len=1.”