300. Longest Increasing Subsequence
Longest Increasing Subsequence (LeetCode 300) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Longest Increasing Subsequence (LIS) subpattern.
- Blind 75 · #58 of 75 · 1-D Dynamic Programming
- NeetCode 150 · #109 of 150 · 1-D Dynamic Programming
- NeetCode 250 · #185 of 250 · 1-D Dynamic Programming
How to solve Longest Increasing Subsequence
Longest Increasing Subsequence is a Longest Increasing Subsequence problem, part of Dynamic Programming (DP) Patterns. Find LIS using DP and binary search optimization. O(n log n) solution.
Work towards the solution in these steps:
- Think about how dynamic programming can help you break down the problem of finding the longest increasing subsequence by considering smaller subproblems.
- Try defining a DP array where each element represents the length of the longest increasing subsequence ending at that index.
- For each element, consider all previous elements and update the current DP value if you find a smaller element that can extend the subsequence.
The reference solution runs in O(nlogn) time and O(n) space.
The Longest Increasing Subsequence solution and editorial walks through the full approach with reference code.
Problem statement
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3] Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7] Output: 1
Constraints:
- 1 <= nums.length <= 2500
- -104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
Topics and companies
Topics: Array, Binary Search, Dynamic Programming.
Reported in interviews at Apple, Amazon, Facebook, Bloomberg, Citrix, Google, ByteDance, Twitter, Microsoft, Nagarro.
How to practise Longest Increasing Subsequence on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(n) space.
Open Longest Increasing Subsequence in the code editor, or read the Longest Increasing Subsequence editorial for a worked solution with its approach and complexity analysis.
Where Longest Increasing Subsequence sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- Longest Increasing Subsequence (LIS) subpattern
- The full DSA patterns sheet
Problems related to Longest Increasing Subsequence
Other problems that use the same Longest Increasing Subsequence (LIS) and Dynamic Programming (DP) Patterns techniques:
- Longest Increasing Subsequence II — Hard, same subpattern
- Minimum Number of Removals to Make Mountain Array — Hard, same subpattern
- Russian Doll Envelopes — Hard, same subpattern
- Best Time to Buy and Sell Stock — Easy, same pattern
- Best Time to Buy and Sell Stock II — Medium, same pattern
- Best Time to Buy and Sell Stock III — Hard, same pattern
Longest Increasing Subsequence FAQ
What is the LeetCode number of Longest Increasing Subsequence?
Longest Increasing Subsequence is LeetCode problem 300, rated Medium.
What pattern is used to solve Longest Increasing Subsequence?
Longest Increasing Subsequence is a Longest Increasing Subsequence problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the Longest Increasing Subsequence (LIS) subpattern.
What is the time complexity of Longest Increasing Subsequence?
The reference solution runs in O(nlogn) time and O(n) space.
Which companies ask Longest Increasing Subsequence?
Longest Increasing Subsequence has been reported in interviews at Apple, Amazon, Facebook, Bloomberg, Citrix, Google, ByteDance, Twitter, Microsoft, Nagarro.