Given an array of integers, find the length of the longest strictly increasing subsequence.
For example, given [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101] with length 4.
Explain your approach to solving this problem and state the time and space complexity.
How to approach it
- Hint 1
For each element, think about what the longest increasing subsequence ending at that element would be.
- Hint 2
dp[i] = the length of the longest increasing subsequence ending at index i. For each j < i where nums[j] < nums[i], dp[i] = max(dp[i], dp[j] + 1).
- Hint 3
There is also an O(n log n) approach using a patience sorting technique with binary search.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.