300. Longest Increasing Subsequence

How to solve Longest Increasing Subsequence (LeetCode 300): the approach in brief

The problem

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

Pattern

Longest Increasing Subsequence is a Dynamic Programming (DP) Patterns problem, in the Longest Increasing Subsequence (LIS) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Find LIS using DP and binary search optimization. O(n log n) solution.

Approach outline

1. Think about how dynamic programming can help you break down the problem of finding the longest increasing subsequence by considering smaller subproblems.
2. Try defining a DP array where each element represents the length of the longest increasing subsequence ending at that index.
3. For each element, consider all previous elements and update the current DP value if you find a smaller element that can extend the subsequence.

Complexity

The reference solution runs in O(nlogn) time and O(n) space.

Asked at

Longest Increasing Subsequence has been reported in interviews at Apple, Amazon, Facebook, Bloomberg, Citrix, Google, ByteDance, Twitter.