Longest Increasing Subsequence
Atlassian
Meta
PayPalThe problem
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3, 6, 2, 7] is a subsequence of [0, 3, 1, 6, 2, 2, 7].
The task is to find the length of the longest subsequence in which every element is greater than the previous one.
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18] Output: 4 Explanation: The longest increasing subsequence is [2, 3, 7, 101], and its length is 4.
Input: nums = [0, 1, 0, 3, 2, 3] Output: 4 Explanation: The longest increasing subsequence is [0, 1, 2, 3], and its length is 4
Input: nums = [7, 7, 7, 7, 7, 7, 7]
- 1 <= nums.length <= 105
- -106 <= nums[i] <= 106
cpp
class Solution {
public:
int LIS(vector<int>& nums) {
}
};java
class Solution {
public int LIS(int[] nums) {
}
}python
class Solution:
def LIS(self, nums):javascript
class Solution {
LIS(nums) {
}
}csharp
public class Solution
{
public int LIS(int[] nums)
{
}
}go
func LIS(nums []int) int {
}Stuck? Show a way to structure it+
- 01Maintain tails where tails[len] is the smallest tail for that length.
- 02Binary-search the first tail greater than or equal to each value.
- 03Replace that tail or append a new one.
- 04Return the number of tails.
Reference answer
Then expect these follow-ups
How would you reconstruct one actual LIS?
Tests: parent pointers
How do you adapt this to non-decreasing subsequences?
Tests: binary-search boundary
Hiring now
PayPal has 254 open roles right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Sr Manager, Partnership Marketing
Chicago, Illinois, United States of America
Lead Product Manager
San Jose, California, United States of America
Sr Software Engineer
Bangalore, Karnataka, India
Next question