Longest Increasing subsequence

300.Longest Increasing Subsequence

Array

Binary Search

Dynamic Programming

Problem Statement:

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

Example:

Input:

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

→

Output:

4

Algorithm:

1. Maintain a sorted array of potential subsequence
2. Use binary search to find insertion position
3. Replace element at that position
4. Length gives LIS size

Complexity:

Binary Search: Time: O(nlogn) | Space: O(n)
DP: Time: O(n²) | Space: O(n)

Java Solution:

// Optimal Binary Search Solution O(nlogn)
public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) return 0;
    
    int len = 0;
    int[] dp = new int[nums.length];

    for (int num : nums) {
        int i = Arrays.binarySearch(dp, 0, len, num);  // Find insertion point
        
        if (i < 0) 
            i = -(i + 1);  // Convert to insertion position
        
        dp[i] = num;
        
        if (i == len) len++;  // New largest value
    }
    
    return len;
}

// DP Solution O(n²)
public int lengthOfLIS_DP(int[] nums) {
    int dp[] = new int[nums.length];
    Arrays.fill(dp, 1);  // Each number is its own subsequence
    int max = 1;

    for (int i = 1; i < nums.length; i++) 
        for (int j = 0; j < i; j++) 
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[j] + 1, dp[i]);
                max = Math.max(max, dp[i]);
            }

    return max;  
}

Python Solution:

def lengthOfLIS(self, nums: List[int]) -> int:
    if not nums: return 0
    
    dp = []
    for num in nums:
        pos = bisect_left(dp, num)  # Find position using binary search
        if pos == len(dp):
            dp.append(num)  # Add new largest value
        else:
            dp[pos] = num  # Replace existing value
    
    return len(dp)

# DP Solution
def lengthOfLIS_DP(self, nums: List[int]) -> int:
    if not nums: return 0
    
    dp = [1] * len(nums)  # Initialize with 1s
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
                
    return max(dp)

C++ Solution:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        
        vector<int> dp;
        
        for(int num : nums) {
            auto it = lower_bound(dp.begin(), dp.end(), num);  // Binary search
            if(it == dp.end())
                dp.push_back(num);  // Add new largest value
            else
                *it = num;  // Replace existing value
        }
        
        return dp.size();
    }
    
    // DP Solution
    int lengthOfLIS_DP(vector<int>& nums) {
        if(nums.empty()) return 0;
        
        vector<int> dp(nums.size(), 1);  // Initialize with 1s
        int maxLen = 1;
        
        for(int i = 1; i < nums.size(); i++) {
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                    maxLen = max(maxLen, dp[i]);
                }
            }
        }
        
        return maxLen;
    }
};