Understanding Longest Increasing Subsequence in Java

What We're Solving

The Longest Increasing Subsequence (LIS) problem is a classic dynamic programming challenge frequently encountered in technical interviews. The goal is to determine the length of the longest subsequence of a given array of integers such that all elements of the subsequence are sorted in strictly increasing order.

It is important to distinguish a subsequence from a substring (or subarray). While a substring requires adjacent indices, a subsequence is derived by deleting zero or more elements from the array without changing the relative order of the remaining items.

For instance, given the array [10, 9, 2, 5, 3, 7, 101, 18], a valid increasing subsequence is [2, 3, 7, 101] or [2, 3, 7, 18], yielding a maximum length of 4. A basic dynamic programming solution solves this in O(n2) time. However, by combining dynamic programming with binary search (derived from the Patience Sorting algorithm), we can optimize this to a highly efficient O(n log n) time complexity.

The Approach

DP with Binary Search (O(n log n) Time, O(n) Space)

In our code, we maintain an active list (or array) sub representing the smallest tail elements of all increasing subsequences found so far. As we iterate through each number num in our input array:

• Search Position: We perform a binary search on sub to locate the insertion index of num.
• Extension: If num is larger than the largest tail in sub, it means we can extend our longest increasing subsequence. We append num to the end of sub.
• Greedy Substitution: If num falls within the bounds of sub, we locate the first element in sub that is greater than or equal to num and replace it with num.

This replacement is a greedy optimization: by lowering the tail values of our subsequences, we increase the likelihood of appending larger numbers that appear later in the stream. At the end of the array traversal, the length of the sub array represents the length of the LIS. Note that the elements inside sub at the end of the run do not necessarily represent the actual LIS subsequence elements, but the total count is guaranteed to be correct.

Detailed Trace Walkthrough

Let's trace the execution on the input array nums = [10, 9, 2, 5, 3]:

1. Step 1 (Initialization): Create an empty list: sub = [].
2. Step 2 (Element: 10):
   • Binary search for 10 in [] returns insertion index 0.
   • Since index == sub.size(), we append 10 → sub = [10].
3. Step 3 (Element: 9):
   • Binary search for 9 in [10] returns insertion index 0.
   • We replace the element at index 0 (10) with 9 → sub = [9]. (An increasing subsequence of length 1 ending in 9 is more optimal than one ending in 10).
4. Step 4 (Element: 2):
   • Binary search for 2 in [9] returns insertion index 0.
   • We replace 9 with 2 → sub = [2].
5. Step 5 (Element: 5):
   • Binary search for 5 in [2] returns insertion index 1.
   • Since index == sub.size(), we append 5 → sub = [2, 5].
6. Step 6 (Element: 3):
   • Binary search for 3 in [2, 5] returns insertion index 1.
   • We replace 5 with 3 → sub = [2, 3]. (An increasing subsequence of length 2 ending in 3 is more optimal than one ending in 5).
7. Step 7 (Final Output):
   • The loop terminates. The size of sub is 2. We return 2 as the LIS length.

Code Breakdown

Understanding the Java implementation helper methods:

• Collections.binarySearch(sub, num) returns the index of the search key if it is contained in the list. If it is not found, it returns -(insertion_point + 1).
• index = -(index + 1) converts a negative search result into the correct zero-indexed insertion point.
• sub.set(index, num) performs the greedy replacement, swapping out the larger tail value to optimize future compatibility.

Full Code Solution

Below is the complete Java implementation featuring the optimized binary search algorithm, along with a main method for trace logging.

package io.practise.dsa;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
 
public class LongestIncreasingSubsequence {
 
    // DP with Binary Search: Time O(N log N), Space O(N)
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
 
        List<Integer> sub = new ArrayList<>();
 
        for (int num : nums) {
            // Find the index of the first element >= num
            int index = Collections.binarySearch(sub, num);
            
            // If not found, binarySearch returns -(insertionPoint + 1)
            if (index < 0) {
                index = -(index + 1);
            }
 
            // If num is larger than all elements in sub, append it
            if (index == sub.size()) {
                sub.add(num);
            } else {
                // Otherwise, replace the first element that is >= num
                sub.set(index, num);
            }
        }
 
        return sub.size();
    }
 
    public static void main(String[] args) {
        LongestIncreasingSubsequence solver = new LongestIncreasingSubsequence();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
 
        System.out.println("--- Longest Increasing Subsequence Demonstration ---");
        System.out.println("Input Array: " + Arrays.toString(nums));
        int length = solver.lengthOfLIS(nums);
        System.out.println("Length of LIS: " + length); // Expected: 4 (e.g., [2, 3, 7, 18])
    }
}

Conclusion & Takeaways

Dynamic programming alone solves the LIS problem in quadratic time. By combining subproblem storage with binary search, we optimize search operations, achieving a highly efficient O(n log n) solution.