2407. Longest Increasing Subsequence II

HardBinary Indexed TreeSegment TreeQueueArrayDivide and ConquerDynamic ProgrammingMonotonic Queue

Problem Description

The problem presents us with a scenario where we have an array of integers called nums and an integer k. Our goal is to find a longest subsequence within nums where each pair of adjacent elements in that subsequence has a difference that is less than or equal to k, and also the subsequence must be in strictly increasing order.

A subsequence is defined as a sequence that can be obtained from another sequence by deleting some or none of the elements without changing the order of the remaining elements. In the context of this problem, it implies we're allowed to skip some elements in nums if they don't fit the requirements, but we cannot reorder the elements.

The final result should be the length of the longest subsequence that satisfies both of these criteria.

Intuition

The solution applies dynamic programming and segment tree concepts to efficiently solve the problem.

Dynamic programming (DP) can be used to keep track of the longest strictly increasing subsequence ending at each element of nums. The main challenge is that we need to consider the additional constraint that the difference between adjacent elements should be at most k.

To find the longest subsequence ending at a specific element v, we look at the maximum value of the longest subsequence that ends at some value between (v-k) to (v-1), since any of those can be a potential candidate because they are within the allowed "k" difference range. We increment that maximum by 1, because v can be appended to that subsequence.

However, implementing this approach directly with an array for DP might lead to a time-consuming process because we would have to iterate over a range of values for each element of nums, leading to a complexity of O(nk), which isn't efficient especially when the numbers are large.

This is where a segment tree comes in. A segment tree allows us to quickly query for the maximum value over a range of indices, thus solving the inefficiency problem. We store the DP values in the segment tree and update them each time we process a new element in nums.

For each integer v in nums, we query the segment tree to find the longest subsequence ending with any integer between (v-k) and (v-1). We then update the segment tree with this value plus one at index v, because v could be potentially added to the subsequence.

By the end of iterating through the nums array, the maximum value in the segment tree will be the length of the longest subsequence that meets the requirements.

Learn more about Segment Tree, Queue, Divide and Conquer, Dynamic Programming and Monotonic Queue patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

Solution Approach

The solution leverages a segment tree to implement the dynamic programming approach efficiently.

Data Structure: Segment Tree

A segment tree is a binary tree data structure which provides the ability to access the collective segment characteristics (like sum, max, min, etc.) over a range of elements in an array efficiently.

In this specific solution, the segment tree is used to maintain the maximum length of the increasing subsequence for given ranges of values in nums.

Building the Segment Tree

First, we need to construct the segment tree. We start by building a tree with n nodes, where n is set to the maximum value present in nums. This ensures that each value in nums maps to a unique position in the segment tree.

In the SegmentTree class, the build function recursively initializes a Node for each segment of the array. Each node stores the bounds of the segment (l for left and r for right) and the value v, which represents the maximum length of the increasing subsequence for that segment.

Updating the Segment Tree

The modify function updates the segment tree when we find a longer subsequence ending at a particular value. It places the length of the new subsequence (v) at the correct index (x) in the segment tree.

When we update a node in the segment tree, we also need to update its ancestors, so the pushup function is called to ensure that each parent node has the correct maximum value after the child nodes change.

Querying the Segment Tree

The query function looks for the greatest length of the subsequence within a specified range (l to r). This is done by checking if the current node's segment is entirely within the range—the base case—or by querying the left and/or right child nodes and combining the results.

The Dynamic Programming Approach

The core logic of the solution is encapsulated in the lengthOfLIS function. We iterate over each value v in nums and use our segment tree to find the maximum length of any increasing subsequence that could end at v - k to v - 1. The longest subsequence ending with v will be one more than that maximum length (indicating v is added to that subsequence).

After querying the segment tree, we update the segment tree with this new maximum at position v, as v itself could be part of a new subsequence.

The Result

After iterating through all the elements of nums, we use the segment tree's query function to find the maximum value across the entire array, which will then give us the length of the longest subsequence satisfying the problem's criteria.

With the use of the segment tree for fast range queries and updates, the time complexity of the algorithm is improved, allowing the solution to work efficiently for larger inputs.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer technique does Quick Sort use?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

Example Walkthrough

Let's illustrate the solution approach with a small example:

Assume nums = [3, 4, 1, 5] and k = 2. According to the problem, we need to find the longest strictly increasing subsequence with adjacent elements having differences of k or less.

Initialization: We first construct a segment tree that can have nodes up to the maximum value in nums, which in this case is 5. Each node represents the maximum length of an increasing subsequence until that index.

Processing nums[0] (3): We query the segment tree for the maximum subsequence length from 1 to 2 (3 - k to 3 - 1) and get 0 because we haven't processed any elements yet. Thus, the longest subsequence ending at 3 is itself, i.e., length 1. We update the segment tree at index 3 with this value.

Processing nums[1] (4): Query the segment tree for the maximum subsequence length from 2 to 3 (4 - k to 4 - 1). The previous value at 3 was 1, so updating the value at index 4 with 1 + 1 = 2, as the subsequence [3, 4] is valid.

Processing nums[2] (1): Query the range from max(0, 1 - k) to 0. Since there are no valid indices before 1, we just update the segment tree at index 1 with length 1, representing the subsequence [1].

Processing nums[3] (5): Query the segment tree for the maximum subsequence length from 3 to 4 (5 - k to 5 - 1). The maximum value here is 2, from our previous update. Thus, the subsequence can be [3, 4, 5]. We update the segment tree at index 5 with 2 + 1 = 3.

Result: Finally, we query for the maximum value across the entire segment tree to find the length of the longest subsequence. In this case, we get 3, which corresponds to the subsequence [3, 4, 5].

This example walkthrough shows how we use the segment tree to keep track of the lengths of increasing subsequences in an efficient manner, allowing us to update and query subsequences' lengths in logarithmic time relative to the range of values in nums.

Solution Implementation

1class Node:
2    def __init__(self):
3        self.left = 0  # Left boundary of the segment
4        self.right = 0  # Right boundary of the segment
5        self.value = 0  # The value stored in the node
6
7
8class SegmentTree:
9    def __init__(self, n):
10        self.tree = [Node() for _ in range(4 * n)]  # Initialize the segment tree
11        self.build(1, 1, n)  # Build the segment tree starting with the root node
12
13    # Build function that initializes each node of the segment tree
14    def build(self, node_index, left, right):
15        self.tree[node_index].left = left
16        self.tree[node_index].right = right
17        if left == right:
18            # If the left and right boundaries are the same, we're at a leaf node
19            return
20        mid = (left + right) // 2  # Calculate mid-point to divide the segment
21        self.build(node_index * 2, left, mid)  # Initialize left child
22        self.build(node_index * 2 + 1, mid + 1, right)  # Initialize right child
23
24    # Modify the value of a single element and update the tree accordingly
25    def modify(self, node_index, index, value):
26        if self.tree[node_index].left == index and self.tree[node_index].right == index:
27            # If the current node corresponds to the element index, update its value
28            self.tree[node_index].value = value
29            return
30        mid = (self.tree[node_index].left + self.tree[node_index].right) // 2
31        if index <= mid:
32            self.modify(node_index * 2, index, value)  # Modify left child
33        else:
34            self.modify(node_index * 2 + 1, index, value)  # Modify right child
35        self.push_up(node_index)  # Update the current node's value based on its children
36
37    # Push up the changes from children to the parent node
38    def push_up(self, node_index):
39        self.tree[node_index].value = max(self.tree[node_index * 2].value, self.tree[node_index * 2 + 1].value)
40
41    # Query the maximum value in the given range [l, r]
42    def query(self, node_index, left, right):
43        if self.tree[node_index].left >= left and self.tree[node_index].right <= right:
44            # If the current segment is entirely within the query range, return its value
45            return self.tree[node_index].value
46        mid = (self.tree[node_index].left + self.tree[node_index].right) // 2
47        max_value = 0
48        if left <= mid:
49            max_value = self.query(node_index * 2, left, right)  # Query left child
50        if right > mid:
51            # Query right child and keep the maximum value found
52            max_value = max(max_value, self.query(node_index * 2 + 1, left, right))
53        return max_value
54
55
56class Solution:
57    def length_of_LIS(self, nums: List[int], k: int) -> int:
58        # Initialize the segment tree with the maximum value in nums as its size
59        tree = SegmentTree(max(nums))
60        max_length = 1
61        for value in nums:
62            # Query the longest increasing subsequence ending before value within the range [value-k, value-1]
63            length = tree.query(1, value - k, value - 1) + 1
64            max_length = max(max_length, length)  # Update the maximum LIS length
65            tree.modify(1, value, length)  # Update the tree with the new LIS ending at value
66        return max_length  # Return the maximum length of LIS found
67

1class Solution {
2    public int lengthOfLIS(int[] nums, int k) {
3        // Find the maximum value in nums to define the size of the Segment Tree
4        int maxVal = nums[0];
5        for (int value : nums) {
6            maxVal = Math.max(maxVal, value);
7        }
8      
9        // Initialize the Segment Tree
10        SegmentTree segmentTree = new SegmentTree(maxVal);
11      
12        // Variable to keep track of the length of the Longest Increasing Subsequence (LIS)
13        int maxLength = 0;
14      
15        // Iterate through all numbers in the array
16        for (int value : nums) {
17            // Query the segment tree for the longest subsequence that ends with a number less than 'value - k'
18            int t = segmentTree.query(1, Math.max(1, value - k), value - 1) + 1;
19            maxLength = Math.max(maxLength, t); // Update the length of the LIS
20          
21            // Modify the segment tree with the new value of the LIS ending with 'value'
22            segmentTree.modify(1, value, t);
23        }
24      
25        // Return the length of the LIS
26        return maxLength;
27    }
28}
29
30class SegmentTreeNode {
31    int left;
32    int right;
33    int value;
34}
35
36class SegmentTree {
37    private SegmentTreeNode[] tree;
38
39    public SegmentTree(int size) {
40        // Initialize the segment tree array based on the size
41        tree = new SegmentTreeNode[4 * size];
42        for (int i = 0; i < tree.length; ++i) {
43            tree[i] = new SegmentTreeNode();
44        }
45        // Build the segment tree
46        build(1, 1, size);
47    }
48
49    // Recursive method to build the segment tree
50    public void build(int node, int start, int end) {
51        tree[node].left = start;
52        tree[node].right = end;
53        if (start == end) {
54            // Leaf node
55            return;
56        }
57        int mid = (start + end) >> 1;
58        build(node * 2, start, mid); // Build left child
59        build(node * 2 + 1, mid + 1, end); // Build right child
60    }
61
62    // Method to modify the segment tree at a given index
63    public void modify(int node, int index, int value) {
64        if (tree[node].left == index && tree[node].right == index) {
65            // If the current node corresponds to the index, update its value
66            tree[node].value = value;
67            return;
68        }
69        int mid = (tree[node].left + tree[node].right) >> 1;
70        // Recursively call modify on the correct child
71        if (index <= mid) {
72            modify(node * 2, index, value);
73        } else {
74            modify(node * 2 + 1, index, value);
75        }
76        pushUp(node); // Update the current node's value
77    }
78
79    // Method to push up the value to the parent node
80    public void pushUp(int node) {
81        tree[node].value = Math.max(tree[node * 2].value, tree[node * 2 + 1].value);
82    }
83
84    // Method to query the segment tree in a range [l, r]
85    public int query(int node, int start, int end) {
86        if (tree[node].left >= start && tree[node].right <= end) {
87            // If the current node is completely within the range, return its value
88            return tree[node].value;
89        }
90        int mid = (tree[node].left + tree[node].right) >> 1;
91        int maxVal = 0;
92        // Query the left and/or right child based on the range and take the maximum value
93        if (start <= mid) {
94            maxVal = query(node * 2, start, end);
95        }
96        if (end > mid) {
97            maxVal = Math.max(maxVal, query(node * 2 + 1, start, end));
98        }
99        return maxVal;
100    }
101}
102

1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6// Node class representing a node in the segment tree.
7class Node {
8public:
9    int left;
10    int right;
11    int value;
12};
13
14// SegmentTree class representing a segment tree data structure.
15class SegmentTree {
16private:
17    vector<Node*> tree; // Vector of Node pointers representing the segment tree structure.
18
19    // Private helper method to push-up the value to the parent node after modifications.
20    void pushUp(int index) {
21        tree[index]->value = max(tree[index * 2]->value, tree[index * 2 + 1]->value);
22    }
23
24public:
25    // Constructor to initialize segment tree with `n` elements.
26    SegmentTree(int n) {
27        tree.resize(4 * n);
28        for (int i = 0; i < tree.size(); ++i) tree[i] = new Node();
29        build(1, 1, n);
30    }
31
32    // Method to build the segment tree recursively.
33    void build(int index, int left, int right) {
34        tree[index]->left = left;
35        tree[index]->right = right;
36        if (left == right) return; // Base case: reach a leaf node.
37        int mid = (left + right) >> 1;
38        build(index * 2, left, mid);
39        build(index * 2 + 1, mid + 1, right);
40    }
41
42    // Method to modify the value at a specific position in the segment tree.
43    void modify(int index, int position, int value) {
44        if (tree[index]->left == position && tree[index]->right == position) {
45            tree[index]->value = value;
46            return;
47        }
48        int mid = (tree[index]->left + tree[index]->right) >> 1;
49        if (position <= mid)
50            modify(index * 2, position, value);
51        else
52            modify(index * 2 + 1, position, value);
53        pushUp(index);
54    }
55
56    // Method to query the maximum value within a range [left, right] in the segment tree.
57    int query(int index, int left, int right) {
58        if (tree[index]->left >= left && tree[index]->right <= right) return tree[index]->value;
59        int mid = (tree[index]->left + tree[index]->right) >> 1;
60        int maxValue = 0;
61        if (left <= mid) maxValue = query(index * 2, left, right);
62        if (right > mid) maxValue = max(maxValue, query(index * 2 + 1, left, right));
63        return maxValue;
64    }
65};
66
67// Solution class to solve the problem.
68class Solution {
69public:
70    // Method to find the length of the Longest Increasing Subsequence (LIS)
71    // where the difference between adjacent elements is at most `k`.
72    int lengthOfLIS(vector<int>& nums, int k) {
73        int maxNum = *max_element(nums.begin(), nums.end());
74        SegmentTree* tree = new SegmentTree(maxNum);
75        int longest = 1;
76        for (int val : nums) {
77            // Get the LIS ending at val considering the constraint 'k'.
78            int localMax = tree->query(1, max(1, val - k), val - 1) + 1;
79            // Update the global LIS length.
80            longest = max(longest, localMax);
81            // Modify the segment tree to include the new LIS length for val.
82            tree->modify(1, val, localMax);
83        }
84        return longest;
85    }
86};
87

1// Represents a node in the segment tree with a value and range it covers.
2interface Node {
3    left: number;
4    right: number;
5    value: number;
6}
7
8// The segment tree is represented by an array of nodes.
9let tree: Node[] = [];
10
11// Push-up operation to update the parent node after modifications in the tree.
12function pushUp(index: number): void {
13    tree[index].value = Math.max(tree[index * 2].value, tree[index * 2 + 1].value);
14}
15
16// Builds the segment tree recursively.
17function build(index: number, left: number, right: number): void {
18    tree[index] = {left, right, value: 0};
19    if (left === right) return; // Base case: leaf node is reached.
20    let mid = Math.floor((left + right) / 2);
21    build(index * 2, left, mid);
22    build(index * 2 + 1, mid + 1, right);
23}
24
25// Modifies the value at a specific position in the segment tree.
26function modify(index: number, position: number, value: number): void {
27    if (tree[index].left === position && tree[index].right === position) {
28        tree[index].value = value;
29        return;
30    }
31    let mid = Math.floor((tree[index].left + tree[index].right) / 2);
32    if (position <= mid)
33        modify(index * 2, position, value);
34    else
35        modify(index * 2 + 1, position, value);
36    pushUp(index);
37}
38
39// Queries the maximum value within a range [left, right] in the segment tree.
40function query(index: number, left: number, right: number): number {
41    if (left <= tree[index].left && right >= tree[index].right) return tree[index].value;
42    let mid = Math.floor((tree[index].left + tree[index].right) / 2);
43    let maxValue = 0;
44    if (left <= mid) maxValue = query(index * 2, left, right);
45    if (right > mid) maxValue = Math.max(maxValue, query(index * 2 + 1, left, right));
46    return maxValue;
47}
48
49// Finds the length of the Longest Increasing Subsequence (LIS)
50// where the difference between adjacent elements is at most `k`.
51function lengthOfLIS(nums: number[], k: number): number {
52    let maxNum = Math.max(...nums);
53    // Initialize the segment tree with the size based on the maximum number in the array.
54    tree = new Array<Node>(4 * maxNum);
55    build(1, 1, maxNum);
56    let longest = 1;
57    for (let val of nums) {
58        // Get the longest subsequence length ending in `val` that respects the difference limit `k`.
59        let localMax = query(1, Math.max(1, val - k), val - 1) + 1;
60        // Update the result if the new LIS is longer.
61        longest = Math.max(longest, localMax);
62        // Update the segment tree with the new maximum LIS up to `val`.
63        modify(1, val, localMax);
64    }
65    return longest;
66}
67

Not Sure What to Study? Take the 2-min Quiz：

Which of these pictures shows the visit order of a depth-first search?

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the lengthOfLIS function is governed by three main operations: building the segment tree, querying the segment tree, and modifying the segment tree.

Building the Segment Tree (SegmentTree.__init__ and build): Building the segment tree is a O(n) operation, where n is the number of nodes in the tree. Since the segment tree is a full binary tree with O(n) leaves, we have a total of O(4 * n) nodes in the tree, including non-leaf nodes. Here n is the maximum value in the nums list.
Modifying a Value in the Segment Tree (modify): Each modification requires traversing from the root of the segment tree to the leaf, which takes O(log n) time.
Querying the Segment Tree (query): Similar to modification, each query in the segment tree requires O(log n) time.

The lengthOfLIS function iterates over all the values in the nums list, and for each value, it performs one query and one modification operation. If there are m values in nums, the total time for all queries and modifications is O(m log n).

Combining these complexities, the total time complexity of the lengthOfLIS function is O(n + m log n).

Space Complexity

The space complexity is governed by the space required to store the segment tree.

The segment tree has 4 * n nodes due to how it is constructed (each node except for the leaves has two children, and there are n leaves representing the array's individual elements). Each node consists of a constant amount of space. Therefore, the space required for the segment tree is O(n).

As a result, the overall space complexity of the lengthOfLIS function is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2407. Longest Increasing Subsequence II

Problem Description

Intuition

Solution Approach

Data Structure: Segment Tree

Building the Segment Tree

Updating the Segment Tree

Querying the Segment Tree

The Dynamic Programming Approach

The Result

Example Walkthrough