139 — Longest Increasing Subsequence

139 — Longest Increasing Subsequence

LeetCode 300 · Medium. Given an integer array nums, return the length of the longest strictly increasing subsequence.

---

🍽️ Intuition

For every element in nums, ask "if the increasing subsequence I'm building had to end right here, how long could it be?" That length depends on every earlier element smaller than the current one — specifically, on the longest increasing subsequence ending at any of them, plus one for the current element. Scanning back over all earlier elements to find the best one to extend gives a correct but quadratic answer. The faster idea is stranger: instead of tracking subsequences by where they end, track the smallest possible tail value for every achievable subsequence length. Grow that "smallest tails" list greedily, and its final length — not its contents — is the answer.

---

🚩 Pattern-Recognition Cue

"Length of the longest strictly increasing subsequence" (not contiguous — elements may be skipped) is the LIS tell. The O(n^2) DP version is recognizable as "each position's best ending-here length depends on every smaller, earlier position's best length" — a variable, data-dependent lookback rather than a fixed window. The O(n log n) version is recognizable by its shape: maintaining a sorted "tails" array and binary-searching it is the patience-sorting signature.

---

🐢 Brute Force

For every position i, look back over every earlier position j, and if nums[j] < nums[i], extend the best subsequence ending at j by one.

func lengthOfLISBruteForce(_ nums: [Int]) -> Int {
    let n = nums.count
    guard n > 0 else { return 0 }

    var dp = Array(repeating: 1, count: n)   // dp[i]: length of the longest increasing subsequence ending at i
    var best = 1

    for i in 0..<n {
        for j in 0..<i where nums[j] < nums[i] {
            dp[i] = max(dp[i], dp[j] + 1)
        }
        best = max(best, dp[i])
    }

    return best
}

// smoke test
print(lengthOfLISBruteForce([10, 9, 2, 5, 3, 7, 101, 18]))   // 4  ([2, 3, 7, 101] or [2, 5, 7, 101])
print(lengthOfLISBruteForce([0, 1, 0, 3, 2, 3]))             // 4
print(lengthOfLISBruteForce([7, 7, 7, 7]))                   // 1

Big-O: O(n^2) time — for each of the n positions, scan all earlier positions. O(n) space for the dp array.

---

🚀 Optimal

Maintain a tails array where tails[k] is the smallest possible tail value of any increasing subsequence of length k + 1 seen so far. For each new number, binary-search tails for the first entry >= it and overwrite that entry (or append, if the number is larger than every current tail) — the final size of tails is the LIS length.

func lengthOfLIS(_ nums: [Int]) -> Int {
    var tails: [Int] = []   // tails[k] = smallest tail value of any increasing subsequence of length k+1

    for num in nums {
        var lo = 0
        var hi = tails.count

        // binary search for the leftmost index where tails[index] >= num
        while lo < hi {
            let mid = (lo + hi) / 2
            if tails[mid] < num {
                lo = mid + 1
            } else {
                hi = mid
            }
        }

        if lo == tails.count {
            tails.append(num)   // num extends the longest subsequence found so far
        } else {
            tails[lo] = num     // num gives a smaller tail for an existing length — improves future extensions
        }
    }

    return tails.count
}

// smoke test — same cases as the brute force
print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))   // 4
print(lengthOfLIS([0, 1, 0, 3, 2, 3]))             // 4
print(lengthOfLIS([7, 7, 7, 7]))                   // 1

Big-O: O(n log n) time — n numbers, each requiring an O(log n) binary search over tails. O(n) space for the tails array.

---

🔑 The Key Insight

The O(n^2) version answers "what's the best subsequence ending exactly at position i?" for every i, which forces a full backward scan since any earlier smaller element could be the right predecessor. The O(n log n) version stops asking "where does a subsequence end?" and asks instead "for each achievable length, what's the smallest value it could possibly end on?" — because a smaller tail is strictly better for extending later (more future numbers can beat a smaller tail than a larger one), there's never a reason to keep more than one candidate tail per length, and that one candidate can always be found and updated with a binary search instead of a linear scan. tails itself usually isn't a real subsequence of nums by the end — it's a running record of "best possible tail per length" — but its length always exactly equals the true LIS length, which is the only thing the problem asks for.

---

🔗 Related Chapters

• 1D Dynamic Programming — the brute force's dp[i] = 1 + max(dp[j]) over all valid earlier j is a variable-lookback 1-D recurrence, the same family as Coin Change's per-denomination lookback.
• Arrays and Strings — both versions build their answer through a left-to-right sweep over nums, accumulating either a dp array or a tails array as they go.
• Binary Search — the optimal solution's inner loop is a textbook lower-bound binary search over the sorted tails array, finding the leftmost insertion point in O(log n).

---

🧸 Memory Sentence

Longest Increasing Subsequence's fast path is patience sorting — keep the smallest possible tail for every achievable subsequence length, binary-search to find and improve the right one for each new number, and the length of that tails list is the answer.

---

✅ Check Your Understanding

1. Why is it always safe to overwrite tails[lo] with a smaller num, rather than worrying that doing so "loses" the subsequence that produced the old value?
2. Trace tails through lengthOfLIS([0, 1, 0, 3, 2, 3]) step by step. At what point does tails stop matching any actual subsequence of the input, and why doesn't that matter for the final answer?
3. Why does tails.count correctly give the LIS length even though tails is not, in general, an actual increasing subsequence found within nums?

---

⬅️ Previous: Word Break · Next: Partition Equal Subset Sum ➡️