Longest Increasing Subsequence

Find the length of the longest increasing subsequence in an array

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

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

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

Input:

  • An integer array nums

Output:

  • Length of the longest increasing subsequence

Constraints:

  • 1 ≤ nums.length ≤ 2500
  • -10⁴ ≤ nums[i] ≤ 10⁴

Examples:

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,18], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4
Explanation: LIS could be [0,1,2,3] with length 4.

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1
Explanation: All elements are equal, so LIS length is 1.

Solutions

Approach 1: Dynamic Programming O(N²)

Algorithm:

  1. dp[i] = length of LIS ending at index i
  2. For each element, check all previous elements
  3. If previous element is smaller, extend its LIS

Python:

def lengthOfLIS_dp(nums):
    """
    DP solution for LIS
    Time: O(N²) - nested loops
    Space: O(N) - DP array
    """
    if not nums:
        return 0
    
    n = len(nums)
    # dp[i] = length of LIS ending at index i
    dp = [1] * n  # Each element forms LIS of length 1
    
    for i in range(1, n):
        for j in range(i):
            # If previous element is smaller, we can extend its LIS
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

def lengthOfLIS_with_path(nums):
    """
    DP solution that also returns the actual LIS
    Time: O(N²)
    Space: O(N)
    """
    if not nums:
        return 0, []
    
    n = len(nums)
    dp = [1] * n
    parent = [-1] * n  # To reconstruct the path
    
    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 LIS 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 max_length, lis[::-1]

# Example usage
print(lengthOfLIS_dp([10,9,2,5,3,7,101,18]))  # Output: 4
length, lis = lengthOfLIS_with_path([10,9,2,5,3,7,101,18])
print(f"Length: {length}, LIS: {lis}")  # Length: 4, LIS: [2, 3, 7, 101]

Approach 2: Binary Search + Patience Sorting O(N log N)

Algorithm:

  1. Maintain array tails where tails[i] is the smallest ending element of all increasing subsequences of length i+1
  2. For each element, find the position to insert using binary search
  3. If element is larger than all elements in tails, append it
  4. Otherwise, replace the first element that is >= current element

Python:

def lengthOfLIS_optimized(nums):
    """
    Optimized solution using binary search
    Time: O(N log N) - N elements, each with O(log N) binary search
    Space: O(N) - tails array
    """
    if not nums:
        return 0
    
    # tails[i] = smallest ending element of all increasing subsequences of length i+1
    tails = []
    
    for num in nums:
        # Binary search to find 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 num is larger than all elements in tails, append it
        if left == len(tails):
            tails.append(num)
        else:
            # Replace the first element that is >= num
            tails[left] = num
    
    return len(tails)

def lengthOfLIS_bisect(nums):
    """
    Using Python's bisect module for binary search
    Time: O(N log N)
    Space: O(N)
    """
    import bisect
    
    if not nums:
        return 0
    
    tails = []
    
    for num in nums:
        # Find the leftmost position where num can be inserted
        pos = bisect.bisect_left(tails, num)
        
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    
    return len(tails)

def lengthOfLIS_with_reconstruction(nums):
    """
    Binary search solution with LIS reconstruction
    Time: O(N log N)
    Space: O(N)
    """
    if not nums:
        return 0, []
    
    import bisect
    
    tails = []
    # Store (value, index) pairs to help with reconstruction
    positions = []  # positions[i] = list of (value, original_index) for length i+1
    
    for i, num in enumerate(nums):
        pos = bisect.bisect_left(tails, num)
        
        if pos == len(tails):
            tails.append(num)
            positions.append([])
        else:
            tails[pos] = num
        
        positions[pos].append((num, i))
    
    # Reconstruct one possible LIS (there might be multiple)
    lis_length = len(tails)
    lis = [0] * lis_length
    
    # Work backwards to find a valid LIS
    last_index = float('inf')
    for length in range(lis_length - 1, -1, -1):
        # Find the rightmost element in positions[length] that comes before last_index
        for value, idx in reversed(positions[length]):
            if idx < last_index:
                lis[length] = value
                last_index = idx
                break
    
    return lis_length, lis

# Example usage
print(lengthOfLIS_optimized([10,9,2,5,3,7,101,18]))  # Output: 4

Java:

import java.util.ArrayList;
import java.util.List;

class Solution {
    /**
     * DP solution O(N²)
     * Time: O(N²)
     * Space: O(N)
     */
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        
        int n = nums.length;
        int[] dp = new int[n];
        java.util.Arrays.fill(dp, 1);
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        return java.util.Arrays.stream(dp).max().orElse(0);
    }
    
    /**
     * Optimized solution using binary search O(N log N)
     * Time: O(N log N)
     * Space: O(N)
     */
    public int lengthOfLISOptimized(int[] nums) {
        if (nums.length == 0) return 0;
        
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            // Binary search for insertion position
            int left = 0, right = tails.size();
            
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails.get(mid) < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            // If num is larger than all elements, append
            if (left == tails.size()) {
                tails.add(num);
            } else {
                // Replace the first element >= num
                tails.set(left, num);
            }
        }
        
        return tails.size();
    }
    
    /**
     * Using Collections.binarySearch
     * Time: O(N log N)
     * Space: O(N)
     */
    public int lengthOfLISBinarySearch(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            int pos = java.util.Collections.binarySearch(tails, num);
            
            if (pos < 0) {
                pos = -(pos + 1);  // Convert to insertion point
            }
            
            if (pos == tails.size()) {
                tails.add(num);
            } else {
                tails.set(pos, num);
            }
        }
        
        return tails.size();
    }
}

Go:

// lengthOfLIS - DP solution
// Time: O(N²)
// Space: O(N)
func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }
    
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    
    result := 0
    for _, val := range dp {
        if val > result {
            result = val
        }
    }
    
    return result
}

// lengthOfLISOptimized - Binary search solution
// Time: O(N log N)
// Space: O(N)
func lengthOfLISOptimized(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    tails := []int{}
    
    for _, num := range nums {
        // Binary search for insertion position
        left, right := 0, len(tails)
        
        for left < right {
            mid := left + (right-left)/2
            if tails[mid] < num {
                left = mid + 1
            } else {
                right = mid
            }
        }
        
        if left == len(tails) {
            tails = append(tails, num)
        } else {
            tails[left] = num
        }
    }
    
    return len(tails)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Key Insights

  1. State Definition: dp[i] = length of LIS ending at index i
  2. Patience Sorting: Binary search approach mimics patience card game
  3. Tails Array: tails[i] stores smallest ending element for subsequences of length i+1
  4. Binary Search Invariant: tails array is always sorted
  5. Greedy Choice: Always choose smallest possible ending element for each length

Edge Cases

  1. Empty array: Return 0
  2. Single element: Return 1
  3. All equal elements: Return 1
  4. Strictly decreasing: Return 1
  5. Strictly increasing: Return array length

Test Cases

def test_lis():
    test_cases = [
        ([10,9,2,5,3,7,101,18], 4),
        ([0,1,0,3,2,3], 4),
        ([7,7,7,7,7,7,7], 1),
        ([1,3,6,7,9,4,10,5,6], 6),
        ([], 0),
        ([1], 1),
        ([2,1], 1),
        ([1,2,3,4,5], 5)
    ]
    
    for nums, expected in test_cases:
        result_dp = lengthOfLIS_dp(nums) if nums else 0
        result_opt = lengthOfLIS_optimized(nums)
        assert result_dp == expected, f"DP: nums={nums}, expected={expected}, got={result_dp}"
        assert result_opt == expected, f"Opt: nums={nums}, expected={expected}, got={result_opt}"
        print(f"LIS({nums}) = {result_opt} ✓")

test_lis()

Common Mistakes

  1. Subsequence vs Subarray: LIS doesn’t need to be contiguous
  2. Strictly vs Non-strictly: Problem asks for strictly increasing
  3. Binary search bounds: Incorrect left/right boundaries
  4. Tails array meaning: Misunderstanding what tails[i] represents
  5. Path reconstruction: Complex to reconstruct actual LIS from binary search

Follow-up Questions

  1. Count of LIS: Count how many LIS exist
  2. Longest decreasing subsequence: Reverse problem
  3. Russian doll envelopes: 2D version of LIS
  4. Print all LIS: Return all longest increasing subsequences
  5. LIS with constraints: Additional constraints on the subsequence
  6. Online LIS: Handle stream of numbers

Interview Tips

  1. Start with DP: Explain O(N²) solution first
  2. Optimize to binary search: Show the improvement to O(N log N)
  3. Explain patience sorting: Use card game analogy
  4. Draw examples: Visualize the tails array updates
  5. Discuss tradeoffs: DP is simpler but slower
  6. Path reconstruction: Mention complexity of getting actual LIS
  7. Test edge cases: Empty array, single element, all equal