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
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question