Longest Increasing Subsequence

Problem

LeetCode 300 — Longest Increasing Subsequence

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

Example

nums = [10, 9, 2, 5, 3, 7, 101, 18]  →  4

One valid LIS: [2, 3, 7, 18]

Approach 1 — Steps to Reach Each Index: O(n²)

Keep a steps[] array of length n where steps[i] = how many elements (steps) are in the longest increasing subsequence ending at index i.

Initialize every index to 1 — each element is a subsequence of length 1 by itself.

Then for each i, try to extend forward to every j > i:

• If nums[i] < nums[j], you can reach j in one more step from i
• Update steps[j] = max(steps[j], steps[i] + 1)

Return max(steps).

Same O(n²) as the backward-looking DP — just flipped: instead of asking “who can extend to me?”, ask “who can I extend to?”.

Walkthrough

nums   = [10, 9, 2, 5, 3, 7, 101, 18]
steps  = [ 1, 1, 1, 1, 1,  1,   1,  1]   // init

i=2 (2): extend to 5,3,7,101,18 → steps[3]=2, steps[4]=2, steps[5]=2, ...
i=4 (3): extend to 7,18           → steps[5]=3, steps[7]=3
i=5 (7): extend to 101,18         → steps[6]=4, steps[7]=4

max(steps) = 4

Complexity

• Time: O(n²)
• Space: O(n)

Good first solution. Works for LeetCode’s constraints but is not optimal.

Java Solution — O(n²) Steps

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] steps = new int[n];
        Arrays.fill(steps, 1);
        int max = 1;

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

Approach 2 — Patience Sorting + Binary Search: O(n log n)

Maintain a tails array where tails[i] is the smallest possible tail of any increasing subsequence of length i + 1 seen so far.

For each x:

1. Binary-search tails for the leftmost position with value >= x
2. If found → overwrite tails[pos] = x (same length, better tail)
3. If not found → append x (subsequence got longer)

Answer = tails.length.

Walkthrough

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

x=10   tails = [10]
x=9    tails = [9]
x=2    tails = [2]
x=5    tails = [2, 5]
x=3    tails = [2, 3]
x=7    tails = [2, 3, 7]
x=101  tails = [2, 3, 7, 101]
x=18   tails = [2, 3, 7, 18]

length = 4

tails is not the LIS itself

tails is sorted and its length is correct, but the array as a whole is not guaranteed to be a valid subsequence of nums in index order — each entry comes from a different underlying path.

Example: nums = [2, 6, 3, 4, 1, 5] → final tails = [1, 3, 4, 5], but 1 appears at index 4 while 3 and 4 appear earlier. You cannot pick [1, 3, 4, 5] left-to-right from the array.

Use this approach for length only. Reconstructing the actual sequence needs extra tracking (parent pointers or the O(n²) DP with backtracking).

Complexity

• Time: O(n log n) — binary search per element
• Space: O(n) — tails array

Java Solution — O(n log n)

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();

        for (int x : nums) {
            int pos = lowerBound(tails, x);
            if (pos == tails.size())
                tails.add(x);
            else
                tails.set(pos, x);
        }
        return tails.size();
    }

    // leftmost index where tails[i] >= x
    private int lowerBound(List<Integer> tails, int x) {
        int lo = 0, hi = tails.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails.get(mid) >= x)
                hi = mid;
            else
                lo = mid + 1;
        }
        return lo;
    }
}

Why It Teaches You Something

The jump from O(n²) to O(n log n) is the lesson: stop storing the full answer at every position and instead store a sufficient invariant — the best tail for each length.

Mental model: patience sorting — each pile’s top is tails[i]; place each card on the leftmost pile with top >= x; number of piles = LIS length.