Longest Increasing Subsequence
Updated
Problem statement
Given an integer array nums, return the length of its longest strictly increasing subsequence. A subsequence is formed by deleting zero or more elements without changing the order of those that remain; its elements need not be consecutive in the original array.
Equal neighboring values do not extend a strictly increasing subsequence. For this exercise, assume an empty array has answer 0.
Function
lisLength(nums: int[]) → intExamples
Example 1
nums = [3,1,2,5,4]return = 3One longest increasing subsequence is [1,2,5]. No increasing subsequence has length four.
Example 2
nums = [2,2,2]return = 1The increase must be strict, so at most one copy of 2 can be selected.
Constraints
- For this exercise, assume
0 <= nums.length <= 10^5. -10^9 <= nums[i] <= 10^9.
More PeopleStrong Onsite Interview questions
- Add Two Binary StringsONSITE INTERVIEW · Seen Mar 2026
- Four SumONSITE INTERVIEW · Seen Mar 2026
- LRU Cache OperationsONSITE INTERVIEW · Seen Mar 2026
- Sliding Window MaximumONSITE INTERVIEW · Seen Mar 2026
- Find the Entry of a Linked List CycleONSITE INTERVIEW · Seen Sep 2025
- Integer to English Words: Up to 20 DigitsONSITE INTERVIEW · Seen Sep 2025
- Word Ladder II: All Shortest TransformationsONSITE INTERVIEW · Seen Sep 2025
- Detect a Cycle in a Linked ListONSITE INTERVIEW · Seen May 2025
- First Nonrepeating CharacterONSITE INTERVIEW · Seen May 2025
- Longest Subarray with a Target SumONSITE INTERVIEW · Seen May 2025
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
- Longest Increasing SubsequenceExpedia · ONSITE INTERVIEWExpedia interview questions
- Minimum Cost for TicketsRoku · ONSITE INTERVIEWRoku 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