Longest Increasing Subsequence
Updated
Problem statement
You are given an integer array nums. A subsequence is what is left after you delete zero or more values without changing the order of the rest. For example, [3, 4, 6] is a subsequence of [3, 8, 4, 9, 5, 6].
Return the length of the longest subsequence whose values are strictly increasing, which means every value is larger than the one before it. Equal values next to each other are not allowed.
Function
longestIncreasingSubsequence(nums: int[]) → intExamples
Example 1
nums = [3,8,4,9,5,6]return = 4One longest choice is 3, 4, 5, 6 (positions 0, 2, 4 and 5). Any choice that uses 8 or 9 has at most 3 values, such as 3, 8, 9 or 3, 4, 9. So the answer is 4.
Example 2
nums = [6,6,6]return = 1The values must go strictly up, and 6, 6 does not. Any single value is a valid subsequence, so the answer is 1.
Example 3
nums = [-2,10,-5,0,7,7,8]return = 4Both -5, 0, 7, 8 and -2, 0, 7, 8 have 4 values. A choice that uses 10 has at most 2 values, because only -2 comes before it and nothing after it is bigger. Without 10, you can use at most one of -2 and -5 (the -5 comes later but is smaller), at most one of the two 7s, plus 0 and 8. That is at most 4 values, so the answer is 4.
Constraints
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
- Maximum Supplier ProfitONSITE INTERVIEW · Seen Aug 2024
Similar questions at other companies
- Longest Increasing SubsequenceAmazon · ONSITE INTERVIEW
- Minimum Removals for a Nice ArrayAdobe · ONSITE INTERVIEWAdobe interview questions
- Longest Increasing SubsequenceMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Minimum Cost for TicketsRoku · ONSITE INTERVIEWRoku interview questions
- Longest Increasing SubsequencePeopleStrong · ONSITE INTERVIEWPeopleStrong interview questions
- Maximum Total Length of Non-Overlapping IntervalsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Russian Doll EnvelopesGoogle · ONSITE INTERVIEWGoogle interview questions
- Russian Doll EnvelopesInMobi · ONSITE INTERVIEWInMobi interview questions
- Longest Increasing SubsequenceByteDance · PHONE SCREENByteDance interview questions
- Longest Increasing SubsequenceAngel One · PHONE SCREEN
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)