Longest Increasing Subsequence (LC 300)

Pattern: Dynamic Programming / Patience sorting + binary search
Difficulty: Medium
Key Concept: dp[i] = LIS length ending at i (O(n²)); or maintain smallest tail values per length (O(n log n)).

Problem Statement

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

A subsequence is derived by deleting some (or zero) elements without changing the order of the remaining elements. Strictly increasing means each chosen element is greater than the previous.

Input: int[] nums.

Output: Integer length of the LIS.

Example: [10, 9, 2, 5, 3, 7, 101, 18] → 4 (e.g. [2, 3, 7, 101]).

---

1. Algorithm & Pseudocode

Brute force: Enumerate all 2^n subsequences; check if strictly increasing; track max length.

DP O(n²)

dp[i] = length of LIS ending at index i
initialize dp[i] = 1 for all i
for i from 0 to n-1:
    for j from 0 to i-1:
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j] + 1)
answer = max(dp)

O(n log n) — tails + binary search

tails = empty list (conceptually: tails[len] = smallest tail value for an increasing subsequence of that length)
for x in nums:
    find position pos = first index in tails where tails[pos] >= x   // lower bound
    if pos == tails.size: append x
    else: tails[pos] = x
return tails.size

The tails array is not the actual LIS—it stores the minimum possible tail for each length so future extensions are easiest.

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why dp[i] counts only subsequences ending at i?
   When you extend a subsequence with nums[i], the previous value must be some nums[j] with j < i and nums[j] < nums[i]. Taking the best dp[j] among such j gives the best length ending at i.

2. Why is brute force 2^n?
   Each index is “in or out” of the subsequence; you check validity for each choice—exponential.

3. Why does the tails method work?
   For a fixed length L, a smaller tail is always better (more numbers can extend it). Replacing with a smaller x keeps length L achievable without hurting longer lengths.

4. Why binary search?
   tails is built to be sorted, so the first position where tails[pos] >= x is found in O(log n) per element.

5. Arrays.binarySearch quirk: If x is not found, Java returns -(insertionPoint) - 1, where insertionPoint is where x would go. So pos = -(result + 1) gives the lower-bound index.

---

3. The Dry Run

Sample: nums = [10, 9, 2, 5, 3, 7, 101, 18].

O(n²) DP — table of dp[i] after inner loops complete for each i:

i	nums[i]	dp[i]	Reason (max over valid j)
0	10	1	only itself
1	9	1	no earlier smaller
2	2	1	no earlier smaller
3	5	2	extends dp[2] (2 < 5)
4	3	2	extends dp[2] (2 < 3)
5	7	3	best from dp[3] or dp[4] (5 or 3 < 7)
6	101	4	e.g. extends dp[5]
7	18	4	extends dp[5] (7 < 18)

max(dp) = 4.

O(n log n) tails — state of tails after each x (list representation):

Step	x	Action	tails after
1	10	append	[10]
2	9	replace at 0	[9]
3	2	replace at 0	[2]
4	5	append	[2, 5]
5	3	replace at 1	[2, 3]
6	7	append	[2, 3, 7]
7	101	append	[2, 3, 7, 101]
8	18	replace at 3	[2, 3, 7, 18]

Length = 4. Note: tails ends with [2, 3, 7, 18], not the true LIS [2, 3, 7, 101]—only the length matches.

---

4. Java Solution

Brute Force

Generate subsequences via bitmasking or recursion. Time: O(n × 2^n). Space: O(n).

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int best = 0;
        int total = 1 << n;
        for (int mask = 0; mask < total; mask++) {
            int prev = Integer.MIN_VALUE;
            int len = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    if (nums[i] <= prev) {
                        len = 0;
                        break;
                    }
                    prev = nums[i];
                    len++;
                }
            }
            best = Math.max(best, len);
        }
        return best;
    }
}

Optimal

O(n²) DP

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int best = 1;
        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;
    }
}

O(n log n) — Arrays.binarySearch on tails

import java.util.Arrays;

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

        for (int x : nums) {
            int idx = Arrays.binarySearch(tails, 0, size, x);
            if (idx < 0) {
                idx = -(idx + 1);
            }
            tails[idx] = x;
            if (idx == size) {
                size++;
            }
        }
        return size;
    }
}

For strictly increasing, binarySearch on exact x finds an equal element if present; we need first position ≥ x. When x exists in tails[0:size), binarySearch returns some index of x, which is correct for replacement (we still replace that slot). When duplicates appear in nums, replacing the found x keeps lengths correct for strict LIS. Alternatively, implement explicit lowerBound for clarity in interviews.

---

5. The “Java vs. Others” Edge

• Arrays.binarySearch(tails, 0, size, x): Searches only the filled prefix [0, size). Negative return → -(insertionPoint) - 1; convert with -(idx + 1) for insertion index (same idea as C++ lower_bound on sorted range).
• Python: bisect_left(tails, x) is the direct analog.
• tails is not the LIS: Reconstructing the actual subsequence needs parent pointers or a separate technique—many interviews only ask for length.
• Strict vs non-strict: For non-decreasing LIS, use lower_bound on x+1 or adjust comparison; LC 300 is strict.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n × 2^n)	O(1) extra	Bitmask only practical for tiny n
Optimal DP	O(n²)	O(n)	dp[i] = LIS ending at i; easy to explain
Optimal + binary search	O(n log n)	O(n)	Patience sorting; tails sorted, binary search each x