Longest Increasing Subsequence — Medium Coding Interview Question

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

Example

Input: nums = [10,9,2,5,3,7,101,18]

Output: 4

Explanation: LIS is [2,3,7,101].

Constraints

• 1 ≤ nums.length ≤ 2500
• -10⁴ ≤ nums[i] ≤ 10⁴

Topics & Companies

Topics: dp, binary-search

Asked by: Amazon, Google, Meta, Microsoft, Apple, Bloomberg

Optimal Solution Complexity

Time complexity: O(n log n). Space complexity: O(n).

Practice more

• All DSA Problems
• DSA Patterns