Fetching algorithms...

Longest Increasing Subsequence | Rulcode

85. Longest Increasing Subsequence

Medium

Topics

Companies

Hint

Understand Before Coding

Loading visualization...

Visualize This Problem

Open Visualizer

Draw Your Approach

Draw

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:

Time Complexity

O(n log n)

Space Complexity

O(n)

Loading problem details...

rulcode

85. Longest Increasing Subsequence

Medium

Topics

Companies

Hint

Understand Before Coding

Step 1 / 38

Speed: 1.0x

Input Array (nums)

101

DP Array (Longest Sequence Starting Here)

Step Explanation

Initialize LIS array with 1s. Every single element is an increasing subsequence of length 1.

Why this works

For each element `nums[i]`, we look at all elements `nums[j]` to its right. If `nums[i] < nums[j]`, then `nums[i]` can extend the increasing subsequence starting at `j`.

We compute `LIS[i] = max(LIS[i], 1 + LIS[j])` for all valid `j`.

The final result is the maximum value in the entire `LIS` array.

Variables

nums[i]-

nums[j]-

LIS[i]-

max_lis1

Loading visualization...

Visualize This Problem

Open Visualizer

Draw Your Approach

Draw

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:

Time Complexity

O(n log n)

Space Complexity

O(n)

Step 1 / 38

Speed: 1.0x

Input Array (nums)

101

DP Array (Longest Sequence Starting Here)

Step Explanation

Initialize LIS array with 1s. Every single element is an increasing subsequence of length 1.

Why this works

For each element `nums[i]`, we look at all elements `nums[j]` to its right. If `nums[i] < nums[j]`, then `nums[i]` can extend the increasing subsequence starting at `j`.

We compute `LIS[i] = max(LIS[i], 1 + LIS[j])` for all valid `j`.

The final result is the maximum value in the entire `LIS` array.

Variables

nums[i]-

nums[j]-

LIS[i]-

max_lis1

85. Longest Increasing Subsequence

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Example 3:

Constraints:

Learn

Topics

Companies

Hint

Use Cases

85. Longest Increasing Subsequence

Understand Before Coding

Input Array (nums)

DP Array (Longest Sequence Starting Here)

Step Explanation

Why this works

Variables

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Example 3:

Constraints:

Learn

Topics

Companies

Hint

Use Cases

Input Array (nums)

DP Array (Longest Sequence Starting Here)

Step Explanation

Why this works

Variables