Q22: How do you solve Longest Increasing Subsequence (LIS) in O(n log n) time using Patience Sorting?

Maintain a dynamic list tails storing the smallest tail element for all increasing subsequences of various lengths. Iterate through nums. Use Arrays.binarySearch() to locate insertion index of x in tails:

If x is larger than all elements, append to tails.
Otherwise, overwrite the first element in tails $ge x$. Length of tails is the LIS length.

O(n log n) LIS Patience Sorting Solution

import java.util.Arrays;

public class LIS {
    public static int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int i = 0, j = size;
            while (i < j) {
                int mid = (i + j) / 2;
                if (tails[mid] < x) i = mid + 1;
                else j = mid;
            }
            tails[i] = x;
            if (i == size) size++;
        }
        return size;
    }
}

💡 Uses binary search to update tail elements in $O(n log n)$ time.

Key Takeaways

Patience Sorting with Binary Search provides $O(n log n)$ performance.
Maintains smallest tail values for increasing subsequences.

Knowledge Check

What does the size variable represent at the end of the Patience Sorting algorithm?

Q22: How do you solve Longest Increasing Subsequence (LIS) in O(n log n) time using Patience Sorting?

STAY UPDATED WITH BYTES!