300. Longest Increasing Subsequence (Medium)

Problem

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 ([2, 3, 7, 101])
• nums = [0, 1, 0, 3, 2, 3] → 4
• nums = [7, 7, 7, 7] → 1

Follow-up: can you do it in $O(n log n)$?

LeetCode 300 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Approach 1: Brute force, try every subsequence

Enumerate all 2ⁿ subsequences; keep the longest strictly increasing.

Python

def length_of_lis(nums):
    n = len(nums)
    best = 0
    for mask in range(1 << n):                                  # L1: 2^n bitmasks
        subseq = [nums[i] for i in range(n) if mask & (1 << i)]
        if all(subseq[i] < subseq[i + 1] for i in range(len(subseq) - 1)):
            best = max(best, len(subseq))
    return best

Swift

final class Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int { func solve(_ i: Int, _ previous: Int?) -> Int { if i == nums.count { return 0 }; let skip = solve(i + 1, previous); let canTake = previous.map { nums[i] > $0 } ?? true; let take = canTake ? 1 + solve(i + 1, nums[i]) : 0; return max(skip, take) }; return solve(0, nil) }
}

Bitmask enumerates all subsequences; for each, checking strict-increase is $O(n)$. Total $O(2^n · n)$. Don’t run this past n ≈ 20.

Complexity

• Time: $O(2ⁿ · n)$.
• Space: $O(n)$.

Skip.

Approach 2: DP, $O(n²)$

dp[i] = length of LIS ending at i. dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]).

Python

def length_of_lis(nums):
    n = len(nums)                          # L1: O(1)
    dp = [1] * n                           # L2: O(n) init, every element is a LIS of length 1
    for i in range(1, n):                  # L3: outer loop, n-1 iterations
        for j in range(i):                 # L4: inner loop, up to i iterations
            if nums[j] < nums[i]:          # L5: O(1) comparison
                dp[i] = max(dp[i], dp[j] + 1)  # L6: O(1) update
    return max(dp)                         # L7: O(n) scan

TypeScript

function lengthOfLIS(nums: number[]): number {
    const n = nums.length;                          // L1: O(1)
    const dp = new Array(n).fill(1);               // L2: O(n) init, every element is LIS of 1
    for (let i = 1; i < n; i++) {                 // L3: outer loop, n-1 iterations
        for (let j = 0; j < i; j++) {             // L4: inner loop, up to i iterations
            if (nums[j] < nums[i]) {              // L5: O(1) comparison
                dp[i] = Math.max(dp[i], dp[j] + 1);  // L6: O(1) update
            }
        }
    }
    return Math.max(...dp);                        // L7: O(n) scan
}

Swift

final class Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int { var dp = Array(repeating: 1, count: nums.count); for i in nums.indices { for j in 0..<i where nums[j] < nums[i] { dp[i] = max(dp[i], dp[j] + 1) } }; return dp.max() ?? 0 }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2 (init dp)	$O(1)$	n	$O(n)$
L3 (outer loop)	$O(1)$	n-1	$O(n)$
L4, L6 (inner loop + update)	$O(1)$	0+1+2+…+(n-1) = n(n-1)/2	$O(n²)$ ← dominates
L7 (max scan)	$O(1)$	n	$O(n)$

The triangular sum at L4 is the bottleneck. For each index i, we scan all j < i, giving 1 + 2 + … + (n-1) = $O(n²)$ iterations total.

Complexity

• Time: $O(n²)$, driven by L4/L6 (the nested loop).
• Space: $O(n)$ for the dp array.

Canonical “beginner” DP.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Patience sort / binary search (optimal)

Maintain tails[k] = the smallest tail of any increasing subsequence of length k + 1. For each new number, replace the first tails[k] ≥ num (or append). len(tails) is the LIS length.

Python

from bisect import bisect_left

def length_of_lis(nums):
    tails = []                             # L1: O(1), empty tails array
    for x in nums:                         # L2: outer loop, n iterations
        i = bisect_left(tails, x)          # L3: O(log k) binary search, k = len(tails)
        if i == len(tails):                # L4: O(1) check
            tails.append(x)               # L5: O(1) amortized, extend LIS
        else:
            tails[i] = x                  # L6: O(1), update smallest tail
    return len(tails)                      # L7: O(1)

TypeScript

function lengthOfLIS(nums: number[]): number {
    function bisectLeft(arr: number[], x: number): number {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    const tails: number[] = [];                    // L1: O(1), empty tails array
    for (const x of nums) {                        // L2: outer loop, n iterations
        const i = bisectLeft(tails, x);            // L3: O(log k) binary search
        if (i === tails.length) tails.push(x);    // L4/L5: O(1) extend LIS
        else tails[i] = x;                        // L6: O(1) update smallest tail
    }
    return tails.length;                           // L7: O(1)
}

Swift

final class Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int { var tails: [Int] = []; for value in nums { var low = 0, high = tails.count; while low < high { let mid = (low + high) / 2; if tails[mid] < value { low = mid + 1 } else { high = mid } }; if low == tails.count { tails.append(value) } else { tails[low] = value } }; return tails.count }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2 (outer loop)	$O(1)$	n	$O(n)$
L3 (binary search)	$O(log n)$	n	$O(n log n)$ ← dominates
L5, L6 (append/assign)	$O(1)$ amortized	n total	$O(n)$
L7 (return)	$O(1)$	1	$O(1)$

L3 does a binary search over tails, which grows to at most n elements. Each of the n elements is processed once with one binary search call, giving $O(n log n)$ total. The append at L5 is $O(1)$ amortized over the whole loop.

Complexity

• Time: $O(n log n)$, driven by L3 (binary search inside the loop).
• Space: $O(n)$ for the tails array.

Note

tails is not itself a valid LIS, it’s the length-indexed smallest tails. But len(tails) equals the LIS length, which is all we need.

For the actual sequence, track predecessor indices alongside (more bookkeeping).

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Enumerate subsequences	$O(2ⁿ · n)$	$O(n)$
DP	$O(n²)$	$O(n)$
Patience sort + binary search	$O(n log n)$	$O(n)$

Patience sort is the canonical $O(n log n)$ answer. Same template: Longest Bitonic Subsequence, Russian Doll Envelopes (354), Minimum Number of Operations to Make Array Increasing (1827 variants).

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_300.py and run.
# Uses the canonical implementation (Approach 3: patience sort + binary search).

from bisect import bisect_left

def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

def _run_tests():
    assert length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]) == 4  # LeetCode example: [2,3,7,101]
    assert length_of_lis([0, 1, 0, 3, 2, 3]) == 4
    assert length_of_lis([7, 7, 7, 7]) == 1                   # all duplicates
    assert length_of_lis([1]) == 1                             # single element
    assert length_of_lis([1, 2, 3, 4, 5]) == 5                # already sorted
    assert length_of_lis([5, 4, 3, 2, 1]) == 1                # strictly decreasing
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function lengthOfLIS(nums: number[]): number {
    function bisectLeft(arr: number[], x: number): number {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
    const tails: number[] = [];
    for (const x of nums) {
        const i = bisectLeft(tails, x);
        if (i === tails.length) tails.push(x);
        else tails[i] = x;
    }
    return tails.length;
}

console.assert(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]) === 4);
console.assert(lengthOfLIS([0, 1, 0, 3, 2, 3]) === 4);
console.assert(lengthOfLIS([7, 7, 7, 7]) === 1);
console.assert(lengthOfLIS([1]) === 1);
console.assert(lengthOfLIS([1, 2, 3, 4, 5]) === 5);
console.assert(lengthOfLIS([5, 4, 3, 2, 1]) === 1);
console.log('all tests pass');

Related data structures

• Arrays, DP array / tails binary search

Related concepts

• Sequence DP, the prefix or position state pattern used for strings and ordered arrays.
• Dynamic Programming, the state and transition model for reusing answers to overlapping subproblems.