Longest Increasing Subsequence

MEDIUM✓ CHIP-TIMEDLC #300 — FULL STATEMENT ↗

The drill: Find the length of the longest run of values you can pick out of an array, keeping their original order, such that each pick is strictly bigger than the one before — skipping is free, ties break the run.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of integers arrives, and the goal is to pick out as long a chain of its values as possible — moving left to right, keeping their original order — where every picked value is strictly bigger than the one picked right before it.

Skipping values costs nothing; the chain doesn't need to be a contiguous run of the array, just values that appear somewhere in it in the same relative order they started in. Equal values back to back can never both belong to the same chain, since the rule demands strictly bigger, not bigger-or-equal.

Only the length of the longest such chain is asked for, not the chain's actual contents.

EX 01

nums = [3, 1, 4, 1, 5, 9, 2, 6]

→ 4

MIXED RUN, NO OBVIOUS STARTING POINT

EX 02

nums = [9, 8, 7, 6, 5]

→ 1

STRICTLY DECREASING, ANY SINGLE ELEMENT IS THE BEST RUN

EX 03

nums = [1, 2, 3, 4, 5]

→ 5

ALREADY SORTED, THE WHOLE ARRAY IS THE ANSWER

arrays can be empty, and an empty array's answer is zero
values may repeat, be negative, zero, or positive
strictly increasing means ties break the chain
only the length is required, not the subsequence itself

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Trying every subsequence is exponential. But the best run ending exactly at some index only cares about the best runs ending at smaller earlier values — what state would let you build up from there?

HINT 2 THE STRUCTURE

dp[i] = the longest increasing run that ends at index i. It's one plus the best dp[j] among every earlier index whose value is smaller than nums[i]; the answer is the largest dp anywhere.

HINT 3 ONE STEP FROM THE ANSWER

That still rescans everyone before each index. Instead keep the smallest tail value achievable for each run length seen so far, and binary-search where the new value belongs — it either extends the longest run or cheapens an earlier length.

COACH'S BOARD — THE PATTERN, STEP BY STEP

PATIENCE PILESPATTERN · PATIENCE PILES, BINARY SEARCHnums = [3, 1, 4, 1, 5, 9, 2, 6]

TAILS PILE

— empty —

STEP 1

Keep tails: the smallest ending value reachable for each run length so far. Binary-search each new value in.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/longest-increasing-subsequence.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []  # tails[k] = smallest possible tail of a run of length k + 1
        for x in nums:
            i = bisect.bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)

TIME O(N LOG N)SPACE O(N)PYTHON · RACE PACE · 10 LN

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n  # dp[i] = longest increasing run ending exactly at i
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp) if dp else 0

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 9 LN

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int lo = 0, hi = size;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (tails[mid] < x) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            tails[lo] = x;
            if (lo == size) {
                size++;
            }
        }
        return size;
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · RACE PACE · 22 LN

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int best = n == 0 ? 0 : 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);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 17 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED