Longest Increasing Subsequence
A hiking app records the elevation, in metres, at each checkpoint of a route in nums; checkpoints below sea level have negative elevations. For its "best climb" badge it looks for the longest selection of checkpoints, kept in route order but allowed to skip any checkpoints in between, in which every chosen checkpoint is strictly higher than the one before it.
Return the length of that longest strictly increasing subsequence of nums. For example, [2,5,9] is a valid selection from [2,7,5,1,9], while [7,5] is not, because it goes down.
Input: nums = [3,8,4,5,1,9] Output: 4
Explanation: Picking 3, 4, 5, 9 climbs at every step, and no selection of five checkpoints does.
Input: nums = [-2,-7,-1,0,-3] Output: 3
Explanation: Both -2, -1, 0 and -7, -1, 0 have length 3.
Input: nums = [9,6,4,2] Output: 1
Explanation: The route only goes down, so the best selection is a single checkpoint.
Constraints
numshas between 1 and 2500 checkpoints.- Each elevation is an integer from -10^4 to 10^4.
Follow-up: Can you also reconstruct one longest subsequence, not just its length?
💡 Hint 1
An O(n²) DP works: len[i] = 1 + the largest len[j] with j < i and nums[j] < nums[i].
💡 Hint 2
For O(n log n), keep tails[k] = the smallest possible last value of an increasing subsequence of length k + 1. This array is always sorted.
💡 Hint 3
For each number, binary-search the first tail that is >= it and overwrite it (or append if none). The final length of tails is the answer.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Maintain tails, where tails[k] is the smallest value that can end an increasing subsequence of length k + 1 seen so far. It is always sorted, so for each x binary-search the leftmost tail >= x. If there is none, x extends the longest subsequence (append). Otherwise replace that tail with x: same length, smaller ending, which only makes future extensions easier. Searching for >= x (not > x) keeps equal values from counting as increasing. The length of tails is the answer (the array itself is not necessarily a real subsequence).
function lengthOfLIS(nums) {
const tails = [];
for (const x of nums) {
let lo = 0;
let hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
}
return tails.length;
}class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int lo = 0, hi = size;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
if (lo == size) size++;
}
return size;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} nums
* @return {number}
*/
function lengthOfLIS(nums) {
}Run your code to see results here.