Longest Increasing Subsequence | Dataford Interview Questions

Given a list of integers, write a function to find the longest increasing subsequence.

Return one valid longest strictly increasing subsequence, preserving the original order but not necessarily contiguity. If the input is empty, return an empty list. The expected solution should run in O(n log n) time.

Input: nums, a list of integers.

Output: A list containing one longest increasing subsequence.

Constraints

0 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
The output must preserve the original order
The subsequence must be strictly increasing

Function Signature

def longest_increasing_subsequence(nums):

Your question is Longest Increasing Subsequence. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem