How do you approach Longest Increasing Subsequence?

DP approach: dp[i] = length of LIS ending at index i.

What is the time complexity of Longest Increasing Subsequence?

Time complexity: O(n log n). Space complexity: O(n).

What are common mistakes on Longest Increasing Subsequence?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

Sitelet https://gitgood.dev/coding/longest-increasing-subsequence

gitGood.dev

← Back to problems

Longest Increasing Subsequence

HardAlgorithms

Description

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 - -10^4 <= nums[i] <= 10^4

Longest Increasing Subsequence: approach, complexity and pitfalls

A hard dynamic programming problem, graded against 6 test cases (3 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 3-step hint ladder

DP approach: dp[i] = length of LIS ending at index i.
For O(n log n): maintain a list where tails[i] is the smallest tail of all LIS of length i+1.
Use binary search to find where to place each element.

The optimal approach

Show the approach: Binary Search with Tails Array

Maintain an array where tails[i] is the smallest tail element for all increasing subsequences of length i+1. Use binary search to update.

Time: O(n log n)
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

← Back to problems

Longest Increasing Subsequence

HardAlgorithms

Description

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 - -10^4 <= nums[i] <= 10^4

Longest Increasing Subsequence: approach, complexity and pitfalls

A hard dynamic programming problem, graded against 6 test cases (3 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 3-step hint ladder

DP approach: dp[i] = length of LIS ending at index i.
For O(n log n): maintain a list where tails[i] is the smallest tail of all LIS of length i+1.
Use binary search to find where to place each element.

The optimal approach

Show the approach: Binary Search with Tails Array

Maintain an array where tails[i] is the smallest tail element for all increasing subsequences of length i+1. Use binary search to update.

Time: O(n log n)
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.