Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3] Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7] Output: 1

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Approach: Dynamic Programming (O(n²))

Algorithm

1. Let dp[i] be the length of the longest strictly increasing subsequence ending at index i
2. Initialize dp[i] = 1 for every index (a single element is always a valid subsequence)
3. For each i, scan all previous j < i: if nums[j] < nums[i], then dp[i] = max(dp[i], dp[j] + 1)
4. The answer is the maximum value in the dp array

Time & Space Complexity

• Time Complexity: O(n²) - nested loops over the array
• Space Complexity: O(n) - the dp array

Java Implementation

import java.util.Arrays;

public class LongestIncreasingSubsequence {

    /**
     * Return the length of the longest strictly increasing subsequence.
     * @param nums Input array
     * @return Length of the LIS
     */
    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        int maxLen = 1;

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

        return maxLen;
    }

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]");
        System.out.println("Output: " + lengthOfLIS(nums1)); // Expected: 4

        int[] nums2 = {0, 1, 0, 3, 2, 3};
        System.out.println("Input: nums = [0, 1, 0, 3, 2, 3]");
        System.out.println("Output: " + lengthOfLIS(nums2)); // Expected: 4

        int[] nums3 = {7, 7, 7, 7, 7, 7, 7};
        System.out.println("Input: nums = [7, 7, 7, 7, 7, 7, 7]");
        System.out.println("Output: " + lengthOfLIS(nums3)); // Expected: 1
    }
}

Optimal Approach: Patience Sorting with Binary Search (O(n log n))

Maintain a tails array where tails[k] is the smallest possible tail value of an increasing subsequence of length k + 1. Binary search finds the position where the current number can extend or replace a tail.

public class LongestIncreasingSubsequenceBinarySearch {

    public static int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;

        for (int num : nums) {
            int lo = 0;
            int hi = size;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (tails[mid] < num) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            tails[lo] = num;
            if (lo == size) {
                size++;
            }
        }

        return size;
    }
}

Time & Space Complexity

• Time Complexity: O(n log n) - each element performs a binary search
• Space Complexity: O(n) - the tails array

Key Points

1. Strictly Increasing: Equal values cannot extend a subsequence
2. DP Definition: dp[i] tracks the longest increasing subsequence ending at i
3. O(n log n) Follow-up: The tails array with binary search achieves the optimal bound
4. Not the Subsequence Itself: The tails technique computes the length, not the actual subsequence
5. Edge Cases: Arrays with all equal values return length 1