2407. Longest Increasing Subsequence II
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.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
671class 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}
1021#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};
871// 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}
67Time 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__andbuild): Building the segment tree is aO(n)operation, wherenis the number of nodes in the tree. Since the segment tree is a full binary tree withO(n)leaves, we have a total ofO(4 * n)nodes in the tree, including non-leaf nodes. Herenis the maximum value in thenumslist. -
Modifying a Value in the Segment Tree (
modify): Each modification requires traversing from the root of the segment tree to the leaf, which takesO(log n)time. -
Querying the Segment Tree (
query): Similar to modification, each query in the segment tree requiresO(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.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is
[3, 7, 40, 80].
What is the recurrence relation?
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger
Want a Structured Path to Master System Design Too? Don’t Miss This!