300. Longest Increasing Subsequence

At a Glance

Topic: dp-1d
Pattern: Dynamic Programming (O(n^2)); patience sorting + binary search (O(n log n))
Difficulty: Medium
Companies: Google, Amazon, Microsoft, Bloomberg, Facebook
Frequency: Very High
LeetCode: 300

Problem (one-liner)

Given integer array nums, return the length of the longest strictly increasing subsequence (not necessarily contiguous). Input: nums. Output: length (non-negative).

Recognition Cues

“Longest increasing subsequence” / LIS
Subsequence (can skip elements), not substring
Patience piles → binary search for length in O(n log n)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — all 2^n bitmasks — exponential.
Better — dp[index] = 1 + max(dp[j]) for j < index and nums[j] < nums[index] — O(n^2) time / O(n) space.
Optimal — maintain sorted “tails” array, binary search position — O(n log n) time / O(n) space. <- pick this in interview.

Optimal Solution

Go

package main

func lengthOfLISTable(nums []int) int {
	length := len(nums)
	if length == 0 {
		return 0
	}
	dp := make([]int, length)
	best := 1
	for right := 0; right < length; right++ {
		dp[right] = 1
		for left := 0; left < right; left++ {
			if nums[left] < nums[right] && dp[left]+1 > dp[right] {
				dp[right] = dp[left] + 1
			}
		}
		if dp[right] > best {
			best = dp[right]
		}
	}
	return best
}

func lengthOfLIS(nums []int) int {
	tails := make([]int, 0, len(nums))
	for _, value := range nums {
		left, right := 0, len(tails)
		for left < right {
			mid := left + (right-left)/2
			if tails[mid] < value {
				left = mid + 1
			} else {
				right = mid
			}
		}
		if left == len(tails) {
			tails = append(tails, value)
		} else {
			tails[left] = value
		}
	}
	return len(tails)
}

JavaScript

function lengthOfLISTable(nums) {
	const length = nums.length;
	if (length === 0) return 0;
	const dp = new Array(length).fill(1);
	let best = 1;
	for (let right = 0; right < length; right++) {
		for (let left = 0; left < right; left++) {
			if (nums[left] < nums[right]) {
				dp[right] = Math.max(dp[right], dp[left] + 1);
			}
		}
		best = Math.max(best, dp[right]);
	}
	return best;
}

function lengthOfLIS(nums) {
	const tails = [];
	for (const value of nums) {
		let left = 0;
		let right = tails.length;
		while (left < right) {
			const mid = Math.floor((left + right) / 2);
			if (tails[mid] < value) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		if (left === tails.length) {
			tails.push(value);
		} else {
			tails[left] = value;
		}
	}
	return tails.length;
}