Longest Increasing Subsequence (LIS)

Generated on 2025-07-10 02:00:49 Algorithm Cheatsheet for Technical Interviews

---

Longest Increasing Subsequence (LIS) Cheat Sheet

1. Quick Overview

• What is it? Find the longest subsequence of a given sequence in which the subsequence’s elements are in strictly increasing order. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
• When to use it? When you need to find the longest increasing order within a sequence where elements don’t have to be contiguous. Common in sequence analysis, algorithm optimization, and data compression.

2. Time & Space Complexity

Approach	Time Complexity	Space Complexity
Naive Recursive	O(2n)	O(n)
Dynamic Programming (Tabulation)	O(n2)	O(n)
Dynamic Programming (Patience Sorting + Binary Search)	O(n log n)	O(n)

3. Implementation

Python

# Dynamic Programming (O(n^2))
def longest_increasing_subsequence_dp(nums):
    """
    Finds the length of the LIS using dynamic programming.

    Args:
        nums: The input list of numbers.

    Returns:
        The length of the LIS.
    """
    n = len(nums)
    dp = [1] * n  # Initialize dp array: each element is an LIS of length 1

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp) if dp else 0

# Patience Sorting + Binary Search (O(n log n))
def longest_increasing_subsequence_binary_search(nums):
    """
    Finds the length of the LIS using patience sorting and binary search.

    Args:
        nums: The input list of numbers.

    Returns:
        The length of the LIS.
    """
    tails = []  # Stores the smallest tail of all increasing subsequences with length i+1.

    for num in nums:
        if not tails or num > tails[-1]:
            tails.append(num)
        else:
            # Binary search to find the smallest tail that is >= num
            l, r = 0, len(tails) - 1
            while l <= r:
                mid = (l + r) // 2
                if tails[mid] < num:
                    l = mid + 1
                else:
                    r = mid - 1
            tails[l] = num  # Replace the smallest tail that is >= num

    return len(tails)

Java

// Dynamic Programming (O(n^2))
class Solution {
    public int lengthOfLIS_DP(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;

        int[] dp = new int[n];
        Arrays.fill(dp, 1); // Initialize dp array: each element is an LIS of length 1

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

        int maxLen = 0;
        for (int len : dp) {
            maxLen = Math.max(maxLen, len);
        }
        return maxLen;
    }

    // Patience Sorting + Binary Search (O(n log n))
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;

        for (int num : nums) {
            int i = 0, j = size;
            while (i != j) {
                int m = (i + j) / 2;
                if (tails[m] < num)
                    i = m + 1;
                else
                    j = m;
            }
            tails[i] = num;
            if (i == size) ++size;
        }
        return size;
    }
}

C++

// Dynamic Programming (O(n^2))
#include <vector>
#include <algorithm>

int longestIncreasingSubsequenceDP(std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    std::vector<int> dp(n, 1); // Initialize dp array: each element is an LIS of length 1

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }

    return *std::max_element(dp.begin(), dp.end());
}

// Patience Sorting + Binary Search (O(n log n))
int longestIncreasingSubsequenceBinarySearch(std::vector<int>& nums) {
    std::vector<int> tails;

    for (int num : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), num); // Find the smallest tail that is >= num
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num; // Replace the smallest tail that is >= num
        }
    }

    return tails.size();
}

4. Common Patterns

• Variations:
  • Longest Non-Decreasing Subsequence: Change the comparison from > to >=.
  • Finding the actual subsequence: Keep track of the predecessor for each element in the dp array. Trace back from the element with the maximum LIS length.
• Use Cases:
  • Stock Market Analysis: Identify trends in stock prices.
  • Bioinformatics: Sequence alignment and gene expression analysis.
  • Data Compression: Optimizing data storage.

5. Pro Tips

• Binary Search Optimization: The O(n log n) approach is significantly faster for larger input sizes. Understand the underlying patience sorting concept.
• Lower Bound: In C++, use std::lower_bound for efficient binary search. In Java, implement your own binary search or use Arrays.binarySearch with appropriate handling of negative return values.
• Edge Cases: Handle empty input arrays gracefully.
• Space Optimization (DP): In some cases, you can optimize the space complexity of the DP solution to O(1) if you only need the length of the LIS and not the subsequence itself, but this usually involves modifying the original array in place (which might not be desirable).

6. Practice Problems

1. LeetCode 300. Longest Increasing Subsequence: https://leetcode.com/problems/longest-increasing-subsequence/
2. LeetCode 354. Russian Doll Envelopes: https://leetcode.com/problems/russian-doll-envelopes/ (A variation requiring sorting and then LIS).
3. LeetCode 673. Number of Longest Increasing Subsequence: https://leetcode.com/problems/number-of-longest-increasing-subsequence/ (Find the number of LISs).

7. Templates

C++ Template:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
    // Implementation (O(n log n) using binary search)
    vector<int> tails;
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "Length of LIS: " << longestIncreasingSubsequence(nums) << endl;
    return 0;
}

Python Template:

def longest_increasing_subsequence(nums):
    # Implementation (O(n log n) using binary search)
    tails = []
    for num in nums:
        l, r = 0, len(tails) - 1
        while l <= r:
            mid = (l + r) // 2
            if tails[mid] < num:
                l = mid + 1
            else:
                r = mid - 1
        if l == len(tails):
            tails.append(num)
        else:
            tails[l] = num
    return len(tails)

if __name__ == "__main__":
    nums = [10, 9, 2, 5, 3, 7, 101, 18]
    print("Length of LIS:", longest_increasing_subsequence(nums))

Java Template:

import java.util.Arrays;

class Solution {
    public int longestIncreasingSubsequence(int[] nums) {
        // Implementation (O(n log n) using binary search)
        int[] tails = new int[nums.length];
        int size = 0;

        for (int num : nums) {
            int i = 0, j = size;
            while (i != j) {
                int m = (i + j) / 2;
                if (tails[m] < num)
                    i = m + 1;
                else
                    j = m;
            }
            tails[i] = num;
            if (i == size) ++size;
        }
        return size;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        Solution sol = new Solution();
        System.out.println("Length of LIS: " + sol.longestIncreasingSubsequence(nums));
    }
}