Longest Increasing Subsequence

NeetCode: Longest Increasing Subsequence · LeetCode: 300. Longest Increasing Subsequence · Difficulty: Medium

Given an integer array nums, return the length of the longest strictly increasing subsequence (elements keep their order but need not be contiguous).

Example

Text

Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]    Output: 4    (2, 3, 7, 18)
Input:  nums = [0, 1, 0, 3, 2, 3]              Output: 4
Input:  nums = [7, 7, 7, 7]                    Output: 1

Brute force: take or skip every element

Walk left to right carrying the index of the last chosen element (-1 when nothing is chosen yet). At each index, either skip the element or take it if it is larger than the last chosen one.

Java

class Solution {
    // prev is the index of the last chosen element, or -1 if none has been chosen.
    private int go(int[] nums, int i, int prev) {
        if (i == nums.length) {
            return 0;
        }
        int skip = go(nums, i + 1, prev);
        int take = 0;
        if (prev == -1 || nums[prev] < nums[i]) {
            take = 1 + go(nums, i + 1, i);
        }
        return Math.max(skip, take);
    }

    public int lengthOfLIS(int[] nums) {
        return go(nums, 0, -1);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
        System.out.println(solution.lengthOfLIS(new int[]{0, 1, 0, 3, 2, 3}));
        System.out.println(solution.lengthOfLIS(new int[]{7, 7, 7, 7}));
        System.out.println(solution.lengthOfLIS(new int[]{}));
    }
}

Output

Every element has two branches, so up to 2^n subsequences are explored. Time: O(2^n). Space: O(n) stack.

Better: quadratic DP

Let dp[i] be the length of the longest increasing subsequence that ends at index i. It is 1 plus the best dp[j] over earlier j with nums[j] < nums[i]. The answer is the maximum over all i.

Java

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int best = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
        System.out.println(solution.lengthOfLIS(new int[]{0, 1, 0, 3, 2, 3}));
        System.out.println(solution.lengthOfLIS(new int[]{7, 7, 7, 7}));
        System.out.println(solution.lengthOfLIS(new int[]{}));
    }
}

Output

Time: O(n^2). Space: O(n).

Optimal: patience sorting with binary search

Keep an array tails where tails[k] is the smallest possible last element of an increasing subsequence of length k + 1. The array is always sorted. For each number x, find the first tail that is >= x (a hand-written lower bound, because Arrays.binarySearch does not say which of several equal elements it returns); because the subsequence must be strictly increasing, an equal value replaces a tail instead of extending the array. If no such tail exists, x extends the longest subsequence, so append it. Otherwise overwrite that tail with x, since a smaller ending is never worse. The array tails has capacity n, and size counts the slots in use. size is the answer. The array itself is not the subsequence, only the bookkeeping that yields its length.

x	tails after
10	[10]
9	[9]
2	[2]
5	[2, 5]
3	[2, 3]
7	[2, 3, 7]
101	[2, 3, 7, 101]
18	[2, 3, 7, 18]

Java

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length]; // only tails[0..size) is in use
        int size = 0;
        for (int x : nums) {
            // Binary search for the first index in tails[0..size) with tails[idx] >= x.
            int lo = 0;
            int hi = size;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (tails[mid] < x) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            tails[lo] = x;
            if (lo == size) {
                size++;
            }
        }
        return size;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
        System.out.println(solution.lengthOfLIS(new int[]{0, 1, 0, 3, 2, 3}));
        System.out.println(solution.lengthOfLIS(new int[]{7, 7, 7, 7}));
        System.out.println(solution.lengthOfLIS(new int[]{}));
    }
}

Output

Time: O(n log n), one binary search per element. Space: O(n) for tails.