Longest Increasing Subsequence

Longest Increasing Subsequence

What is this problem about?

The Longest Increasing Subsequence (LIS) problem is one of the most famous algorithmic challenges. Given an unsorted array of integers, you must find the length of the longest strictly increasing subsequence. A subsequence allows you to delete elements from the array without changing the order of the remaining elements. For example, in [10, 9, 2, 5, 3, 7, 101, 18], the LIS is [2, 3, 7, 101], which has a length of 4.

Why is this asked in interviews?

LIS is the benchmark for testing a candidate's understanding of Dynamic Programming. Interviewers ask it because it has an intuitive $O(N^2)$ DP solution that is great for junior roles, but also a hidden, highly elegant $O(N \log N)$ Binary Search solution that separates senior candidates from the pack. It is an essential building block; many other complex array problems can be reduced to finding an LIS.

Algorithmic pattern used

There are two main patterns:

1. Dynamic Programming: Create a dp array where dp[i] is the length of the LIS ending at index i. Compare every element i with every element j before it.
2. Binary Search with DP (Optimal): Maintain an array tails that stores the smallest tail of all increasing subsequences of various lengths. Iterate through the array; if an element is larger than the last element of tails, append it. If not, use Binary Search to find the smallest element in tails that is $\ge$ the current element, and replace it.

Example explanation

Let's use the Binary Search approach on [10, 9, 2, 5, 3, 7]. We maintain a tails array.

• 10: tails is empty. Append 10. tails = [10].
• 9: 9 is smaller than 10. Replace 10. tails = [9]. (A subsequence of length 1 ending in 9 is better than one ending in 10).
• 2: 2 is smaller than 9. Replace 9. tails = [2].
• 5: 5 is larger than 2. Append 5. tails = [2, 5]. (Length is now 2).
• 3: Binary search for the smallest number $\ge 3$. It's 5. Replace 5 with 3. tails = [2, 3]. (We essentially swapped the tail of our length-2 sequence to be smaller, making it easier to append to later).
• 7: 7 is larger than 3. Append 7. tails = [2, 3, 7]. The length of the tails array is 3.

Common mistakes candidates make

A frequent misunderstanding with the $O(N \log N)$ approach is assuming that the resulting tails array represents the actual longest subsequence. It does not! It only accurately tracks the length of the longest subsequence and the optimal ending values. If the interviewer asks you to print the actual subsequence, you must keep track of parent pointers or rely on the $O(N^2)$ DP array.

Interview preparation tip

For the Longest Increasing Subsequence coding problem, practice both solutions. Start by writing the $O(N^2)$ nested loop solution so you deeply understand the subproblems. Then, memorize the tails array Binary Search optimization. Being able to explain why replacing the elements in tails works (it lowers the barrier for future elements to join the sequence) will severely impress your interviewer.