Longest Increasing Subsequence
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
