Longest Increasing Subsequence II - Practice Coding Problems

Longest Increasing Subsequence II - Problem

Array Divide and Conquer Dynamic Programming Binary Indexed Tree Segment Tree Queue Monotonic Queue Hard

You are given an integer array nums and an integer k. Your task is to find the longest subsequence that satisfies two important conditions:

The subsequence is strictly increasing
The difference between any two adjacent elements in the subsequence is at most k

A subsequence is derived from the original array by deleting some or no elements without changing the order of the remaining elements. For example, from array [4,2,1,4,3,4,5,8,15], a valid subsequence could be [2,4,5,8].

Return the length of the longest subsequence that meets both requirements.

Example: If nums = [4,2,1,4,3,4,5,8,15] and k = 3, one possible longest increasing subsequence with difference ≤ 3 could be [1,3,4,5,8] with length 5.

Input & Output

example_1.py — Basic Case

$ Input: nums = [4,2,1,4,3,4,5,8,15], k = 3

› Output: 5

💡 Note: One possible longest increasing subsequence is [1,3,4,5,8] with length 5. Each adjacent pair has difference ≤ 3: 3-1=2, 4-3=1, 5-4=1, 8-5=3.

example_2.py — Small Difference

$ Input: nums = [7,4,5,1,8,12,4,7], k = 5

› Output: 4

💡 Note: One possible longest increasing subsequence is [4,5,7,12] with length 4. Differences: 5-4=1, 7-5=2, 12-7=5 (all ≤ 5).

example_3.py — Edge Case

$ Input: nums = [1,5], k = 1

› Output: 1

💡 Note: Cannot form increasing subsequence of length > 1 because 5-1=4 > k=1. Maximum length is 1.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i], k ≤ 10⁵
The array can contain duplicate values
Subsequence must be strictly increasing (no equal elements)

Visualization

Tap to expand

Understanding the Visualization

Scan Array

Process each element from left to right

Find Valid Range

For current element x, find all previous elements in range [x-k, x-1]

Get Maximum

Query the maximum subsequence length ending in the valid range

Update Tree

Update data structure with new maximum length at current position

Key Takeaway

🎯 Key Insight: Use segment tree with coordinate compression to efficiently query the maximum subsequence length in any value range, reducing time complexity from O(n²) to O(n log n).

Asked in

G Google 15 a Amazon 12 f Meta 8 ⊞ Microsoft 6

The optimal solution uses coordinate compression with a segment tree to achieve O(n log n) time complexity. The key insight is to avoid checking all previous elements by using a data structure that can efficiently find the maximum subsequence length in a range of values that satisfy the constraint |nums[i] - nums[j]| ≤ k.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Dynamic Programming	O(n²)	O(n)	Check all previous elements for each position using O(n²) DP
Segment Tree / Binary Indexed Tree	O(n log n)	O(n)	Use segment tree to efficiently query and update maximum subsequence lengths

Brute Force Dynamic Programming — Algorithm Steps

Initialize dp array where dp[i] = 1 (each element forms subsequence of length 1)
For each element at index i, check all previous elements at index j
If nums[j] < nums[i] and nums[i] - nums[j] <= k, update dp[i] = max(dp[i], dp[j] + 1)
Return the maximum value in dp array

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP

Create dp array with all 1s

Check Previous

For each element, check all previous elements

Update DP

Update dp[i] if valid transition found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int lengthOfLIS(int* nums, int numsSize, int k) {
    if (numsSize == 0) return 0;
    
    int* dp = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
    }
    
    for (int i = 1; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && nums[i] - nums[j] <= k) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    
    int maxLen = dp[0];
    for (int i = 1; i < numsSize; i++) {
        maxLen = max(maxLen, dp[i]);
    }
    
    free(dp);
    return maxLen;
}

int main() {
    int nums[] = {4, 2, 1, 4, 3, 4, 5, 8, 15};
    int k = 3;
    printf("%d\n", lengthOfLIS(nums, 9, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n elements, we check all previous elements

⚠ Quadratic Growth

Space Complexity

O(n)

DP array to store the longest subsequence length ending at each position

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler