Longest Increasing Subsequence

Medium· LIS· binary search

Problem

Given an integer array, return the length of the longest subsequence whose values are strictly increasing. A subsequence keeps the original order but may skip elements.

Examples

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

Output: 4

One such subsequence is [2,3,7,101].

Input: nums = [7,7,7,7]

Output: 1

Constraints

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

Hints & approach

Hint 1

The O(n²) DP: lis[i] = 1 + max lis[j] over j < i with nums[j] < nums[i].

Hint 2

For each length, only the smallest possible tail value matters.

Hint 3

Keep a sorted array of tails and binary-search where each number goes.

Approachtry the hints first

Maintain tails, where tails[k] is the smallest tail of any increasing subsequence of length k+1 seen so far; this array is always sorted. For each number, binary-search the first tail that is ≥ it. If none exists, append the number (a longer subsequence); otherwise overwrite that tail with the smaller value. The length of tails is the answer. The simpler O(n²) DP is a valid stepping stone.

Time O(n log n) · Space O(n)

← PreviousTarget Sum Next →Longest Common Subsequence