Longest Increasing Subsequence

Longest Increasing Subsequence 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.

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
• All coding practice problems

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