2407. Longest Increasing Subsequence II

HardBinary Indexed TreeSegment TreeQueueArrayDivide and ConquerDynamic ProgrammingMonotonic Queue

Problem Description

You are given an integer array nums and an integer k.

Your task is to find the longest subsequence from nums that satisfies two conditions:

The subsequence must be strictly increasing (each element is greater than the previous one)
The difference between any two adjacent elements in the subsequence must be at most k (if we have adjacent elements a and b where b comes after a, then b - a ≤ k)

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

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

The key challenge here is that while we want the subsequence to be increasing, we also need to ensure that consecutive elements in our chosen subsequence don't differ by more than k. This means if we select an element v, the next element we can select must be greater than v but not greater than v + k.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Let's think about this problem step by step. For each element in the array, we need to decide whether to include it in our subsequence or not. If we include it, we want to know: what's the longest valid subsequence that can end at this element?

This naturally leads us to dynamic programming. We can define f[v] as the length of the longest increasing subsequence that ends with value v. When we encounter a new element v, we need to find the best subsequence we can extend.

Since our subsequence must be strictly increasing with adjacent differences at most k, if we want to end our subsequence at value v, the previous element in the subsequence must be:

Less than v (for strict increasing property)
At least v - k (to satisfy the difference constraint)

So we need to look at all values in the range [v-k, v-1] and find which one gives us the longest subsequence to extend. The recurrence relation becomes: f[v] = max(f[x]) + 1 where x ∈ [v-k, v-1].

The challenge now is efficiency. For each element, we need to query the maximum value in a range and update a single point. If we use a simple array and iterate through the range each time, it would be too slow for large inputs.

This is where the segment tree comes in. It's perfect for this scenario because:

We need range maximum queries (find the best subsequence length in range [v-k, v-1])
We need point updates (update f[v] after processing element v)
Both operations can be done in O(log n) time with a segment tree

The segment tree maintains the maximum subsequence length for any range of values efficiently, allowing us to solve the problem in O(n log m) time where n is the length of the array and m is the maximum value in the array.

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

Solution Approach

The solution uses a segment tree to efficiently maintain and query the maximum subsequence length for value ranges. Let's walk through the implementation:

Segment Tree Structure

The segment tree is built to handle values from 1 to max(nums). Each node in the tree stores:

l: left boundary of the interval
r: right boundary of the interval
v: maximum subsequence length in this interval

The tree is initialized with 4 * n nodes (a standard size for segment trees) where n is the maximum value in nums.

Building the Tree

The build function recursively constructs the tree:

Each node represents an interval [l, r]
Leaf nodes represent single values [x, x]
Internal nodes split their range at the midpoint: mid = (l + r) >> 1
Left child covers [l, mid], right child covers [mid + 1, r]

Core Operations

1. Query Operation (query)

Finds the maximum subsequence length in range [l, r]
If current node's interval is completely within query range, return its value
Otherwise, recursively query relevant children
Combines results from left and right subtrees using max

2. Modify Operation (modify)

Updates the subsequence length for a specific value x to v
Navigates to the leaf node representing value x
Updates the value and propagates changes up using pushup

3. Pushup Operation

Updates parent node's value as the maximum of its children
Ensures the tree maintains correct maximum values after modifications

Main Algorithm

def lengthOfLIS(self, nums: List[int], k: int) -> int:
    tree = SegmentTree(max(nums))
    ans = 1
    for v in nums:
        t = tree.query(1, v - k, v - 1) + 1
        ans = max(ans, t)
        tree.modify(1, v, t)
    return ans

For each element v in nums:

Query the maximum subsequence length in range [v-k, v-1] using tree.query(1, v - k, v - 1)
Calculate the new subsequence length ending at v: t = query_result + 1
Update the answer with the maximum length found so far
Modify the tree to record that the longest subsequence ending at value v has length t

Time Complexity

Building the tree: O(m) where m = max(nums)
Each query and modify operation: O(log m)
Total: O(m + n log m) where n is the length of nums

The segment tree efficiently handles the range maximum queries and point updates needed for the dynamic programming solution, making it possible to solve the problem for large inputs.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

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

We'll build a segment tree for values 1 to 5 (max of nums). The tree will store f[v] - the length of the longest increasing subsequence ending at value v.

Initial State:

Segment tree initialized with all values as 0
f[1] = 0, f[2] = 0, f[3] = 0, f[4] = 0, f[5] = 0

Processing nums[0] = 4:

Query range [4-2, 4-1] = [2, 3]: max(f[2], f[3]) = max(0, 0) = 0
New length ending at 4: t = 0 + 1 = 1
Update: f[4] = 1
Current answer: ans = 1

Processing nums[1] = 2:

Query range [2-2, 2-1] = [0, 1]: max(f[1]) = 0 (0 is out of bounds)
New length ending at 2: t = 0 + 1 = 1
Update: f[2] = 1
Current answer: ans = 1

Processing nums[2] = 1:

Query range [1-2, 1-1] = [-1, 0]: no valid values in range, returns 0
New length ending at 1: t = 0 + 1 = 1
Update: f[1] = 1
Current answer: ans = 1

Processing nums[3] = 4:

Query range [4-2, 4-1] = [2, 3]: max(f[2], f[3]) = max(1, 0) = 1
New length ending at 4: t = 1 + 1 = 2
Update: f[4] = 2 (we found subsequence [2, 4])
Current answer: ans = 2

Processing nums[4] = 3:

Query range [3-2, 3-1] = [1, 2]: max(f[1], f[2]) = max(1, 1) = 1
New length ending at 3: t = 1 + 1 = 2
Update: f[3] = 2 (we can have [1, 3] or [2, 3])
Current answer: ans = 2

Processing nums[5] = 5:

Query range [5-2, 5-1] = [3, 4]: max(f[3], f[4]) = max(2, 2) = 2
New length ending at 5: t = 2 + 1 = 3
Update: f[5] = 3 (we found subsequence [2, 4, 5] or [2, 3, 5])
Current answer: ans = 3

Final Result: 3

The longest valid subsequence is [2, 4, 5] or [2, 3, 5], both with length 3. Notice how:

Each subsequence is strictly increasing
Adjacent differences are at most k=2 (4-2=2, 5-4=1 for first; 3-2=1, 5-3=2 for second)
The segment tree efficiently tracked the best subsequence length ending at each value

Solution Implementation

1from typing import List
2
3
4class Node:
5    """Represents a node in the segment tree."""
6  
7    def __init__(self):
8        self.left_bound = 0   # Left boundary of the segment
9        self.right_bound = 0  # Right boundary of the segment
10        self.value = 0        # Maximum value in this segment
11
12
13class SegmentTree:
14    """
15    Segment tree for range maximum queries and point updates.
16    Used to efficiently find maximum values in ranges.
17    """
18  
19    def __init__(self, n: int):
20        """
21        Initialize segment tree with size n.
22      
23        Args:
24            n: Maximum value in the range [1, n]
25        """
26        # Allocate 4*n nodes for the segment tree
27        self.tree = [Node() for _ in range(4 * n)]
28        self.build(1, 1, n)
29  
30    def build(self, node_idx: int, left: int, right: int) -> None:
31        """
32        Build the segment tree recursively.
33      
34        Args:
35            node_idx: Current node index in the tree array
36            left: Left boundary of current segment
37            right: Right boundary of current segment
38        """
39        self.tree[node_idx].left_bound = left
40        self.tree[node_idx].right_bound = right
41      
42        # Base case: leaf node
43        if left == right:
44            return
45      
46        # Recursively build left and right subtrees
47        mid = (left + right) >> 1  # Equivalent to // 2
48        self.build(node_idx << 1, left, mid)           # Left child at index 2*node_idx
49        self.build(node_idx << 1 | 1, mid + 1, right)  # Right child at index 2*node_idx + 1
50  
51    def modify(self, node_idx: int, position: int, value: int) -> None:
52        """
53        Update the value at a specific position.
54      
55        Args:
56            node_idx: Current node index in the tree array
57            position: Position to update
58            value: New value to set
59        """
60        current_node = self.tree[node_idx]
61      
62        # Base case: reached the target leaf node
63        if current_node.left_bound == position and current_node.right_bound == position:
64            current_node.value = value
65            return
66      
67        # Recursively update the appropriate child
68        mid = (current_node.left_bound + current_node.right_bound) >> 1
69        if position <= mid:
70            self.modify(node_idx << 1, position, value)
71        else:
72            self.modify(node_idx << 1 | 1, position, value)
73      
74        # Update current node's value based on children
75        self.pushup(node_idx)
76  
77    def pushup(self, node_idx: int) -> None:
78        """
79        Update parent node value based on its children's values.
80      
81        Args:
82            node_idx: Current node index to update
83        """
84        left_child_value = self.tree[node_idx << 1].value
85        right_child_value = self.tree[node_idx << 1 | 1].value
86        self.tree[node_idx].value = max(left_child_value, right_child_value)
87  
88    def query(self, node_idx: int, query_left: int, query_right: int) -> int:
89        """
90        Query the maximum value in range [query_left, query_right].
91      
92        Args:
93            node_idx: Current node index in the tree array
94            query_left: Left boundary of query range
95            query_right: Right boundary of query range
96          
97        Returns:
98            Maximum value in the specified range
99        """
100        current_node = self.tree[node_idx]
101      
102        # Current segment is completely within query range
103        if current_node.left_bound >= query_left and current_node.right_bound <= query_right:
104            return current_node.value
105      
106        # Query both children if they overlap with query range
107        mid = (current_node.left_bound + current_node.right_bound) >> 1
108        max_value = 0
109      
110        # Check if left child overlaps with query range
111        if query_left <= mid:
112            max_value = self.query(node_idx << 1, query_left, query_right)
113      
114        # Check if right child overlaps with query range
115        if query_right > mid:
116            max_value = max(max_value, self.query(node_idx << 1 | 1, query_left, query_right))
117      
118        return max_value
119
120
121class Solution:
122    def lengthOfLIS(self, nums: List[int], k: int) -> int:
123        """
124        Find length of longest increasing subsequence with constraint that
125        difference between consecutive elements is at most k.
126      
127        Args:
128            nums: Input array of integers
129            k: Maximum allowed difference between consecutive elements
130          
131        Returns:
132            Length of the longest increasing subsequence with the given constraint
133        """
134        # Initialize segment tree with range up to maximum value in nums
135        segment_tree = SegmentTree(max(nums))
136        max_length = 1
137      
138        for current_value in nums:
139            # Query maximum length ending with values in range [current_value - k, current_value - 1]
140            # This ensures the difference constraint is satisfied
141            prev_max_length = segment_tree.query(1, current_value - k, current_value - 1)
142            current_length = prev_max_length + 1
143          
144            # Update the answer if we found a longer subsequence
145            max_length = max(max_length, current_length)
146          
147            # Update the segment tree with the length of subsequence ending at current_value
148            segment_tree.modify(1, current_value, current_length)
149      
150        return max_length
151

1class Solution {
2    /**
3     * Finds the length of the longest increasing subsequence where the difference
4     * between consecutive elements is at most k.
5     * 
6     * @param nums the input array
7     * @param k the maximum allowed difference between consecutive elements
8     * @return the length of the longest increasing subsequence
9     */
10    public int lengthOfLIS(int[] nums, int k) {
11        // Find the maximum value in the array to determine segment tree size
12        int maxValue = nums[0];
13        for (int num : nums) {
14            maxValue = Math.max(maxValue, num);
15        }
16      
17        // Initialize segment tree with range [1, maxValue]
18        SegmentTree segmentTree = new SegmentTree(maxValue);
19        int maxLength = 0;
20      
21        // Process each number in the array
22        for (int currentValue : nums) {
23            // Query the maximum length of subsequence ending with values in range [currentValue - k, currentValue - 1]
24            // Add 1 to include current element
25            int currentLength = segmentTree.query(1, currentValue - k, currentValue - 1) + 1;
26            maxLength = Math.max(maxLength, currentLength);
27          
28            // Update the segment tree with the new length for currentValue
29            segmentTree.modify(1, currentValue, currentLength);
30        }
31      
32        return maxLength;
33    }
34}
35
36/**
37 * Node class representing a node in the segment tree
38 */
39class Node {
40    int left;   // Left boundary of the range
41    int right;  // Right boundary of the range
42    int value;  // Maximum value in this range
43}
44
45/**
46 * Segment Tree implementation for range maximum queries
47 */
48class SegmentTree {
49    private Node[] tree;
50  
51    /**
52     * Constructor to initialize the segment tree
53     * @param n the maximum value in the range [1, n]
54     */
55    public SegmentTree(int n) {
56        // Allocate 4*n nodes for the segment tree
57        tree = new Node[4 * n];
58        for (int i = 0; i < tree.length; ++i) {
59            tree[i] = new Node();
60        }
61        // Build the tree structure
62        build(1, 1, n);
63    }
64  
65    /**
66     * Builds the segment tree recursively
67     * @param nodeIndex current node index
68     * @param left left boundary of current range
69     * @param right right boundary of current range
70     */
71    public void build(int nodeIndex, int left, int right) {
72        tree[nodeIndex].left = left;
73        tree[nodeIndex].right = right;
74      
75        // Base case: leaf node
76        if (left == right) {
77            return;
78        }
79      
80        // Recursively build left and right subtrees
81        int mid = (left + right) >> 1;
82        build(nodeIndex << 1, left, mid);
83        build(nodeIndex << 1 | 1, mid + 1, right);
84    }
85  
86    /**
87     * Updates a single position in the segment tree
88     * @param nodeIndex current node index
89     * @param position the position to update
90     * @param newValue the new value to set
91     */
92    public void modify(int nodeIndex, int position, int newValue) {
93        // Base case: reached the target leaf node
94        if (tree[nodeIndex].left == position && tree[nodeIndex].right == position) {
95            tree[nodeIndex].value = newValue;
96            return;
97        }
98      
99        // Recursively update the appropriate child
100        int mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1;
101        if (position <= mid) {
102            modify(nodeIndex << 1, position, newValue);
103        } else {
104            modify(nodeIndex << 1 | 1, position, newValue);
105        }
106      
107        // Update current node's value based on children
108        pushup(nodeIndex);
109    }
110  
111    /**
112     * Updates parent node value based on children values
113     * @param nodeIndex current node index
114     */
115    public void pushup(int nodeIndex) {
116        tree[nodeIndex].value = Math.max(
117            tree[nodeIndex << 1].value, 
118            tree[nodeIndex << 1 | 1].value
119        );
120    }
121  
122    /**
123     * Queries the maximum value in a given range
124     * @param nodeIndex current node index
125     * @param queryLeft left boundary of query range
126     * @param queryRight right boundary of query range
127     * @return maximum value in the range [queryLeft, queryRight]
128     */
129    public int query(int nodeIndex, int queryLeft, int queryRight) {
130        // Current range is completely within query range
131        if (tree[nodeIndex].left >= queryLeft && tree[nodeIndex].right <= queryRight) {
132            return tree[nodeIndex].value;
133        }
134      
135        int mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1;
136        int result = 0;
137      
138        // Query left subtree if needed
139        if (queryLeft <= mid) {
140            result = query(nodeIndex << 1, queryLeft, queryRight);
141        }
142      
143        // Query right subtree if needed
144        if (queryRight > mid) {
145            result = Math.max(result, query(nodeIndex << 1 | 1, queryLeft, queryRight));
146        }
147      
148        return result;
149    }
150}
151

1class Node {
2public:
3    int left;   // Left boundary of the segment
4    int right;  // Right boundary of the segment
5    int value;  // Maximum value in this segment
6};
7
8class SegmentTree {
9public:
10    vector<Node*> tree;  // Segment tree nodes array
11
12    // Constructor: Initialize segment tree with size n
13    SegmentTree(int n) {
14        tree.resize(4 * n);  // Allocate 4*n nodes for the tree
15        for (int i = 0; i < tree.size(); ++i) {
16            tree[i] = new Node();
17        }
18        build(1, 1, n);  // Build tree starting from root (index 1)
19    }
20
21    // Build the segment tree recursively
22    void build(int nodeIndex, int left, int right) {
23        tree[nodeIndex]->left = left;
24        tree[nodeIndex]->right = right;
25      
26        // Leaf node - no need to recurse further
27        if (left == right) {
28            return;
29        }
30      
31        // Build left and right subtrees
32        int mid = (left + right) >> 1;  // Equivalent to (left + right) / 2
33        build(nodeIndex << 1, left, mid);  // Build left child (2 * nodeIndex)
34        build(nodeIndex << 1 | 1, mid + 1, right);  // Build right child (2 * nodeIndex + 1)
35    }
36
37    // Update the value at position x to v
38    void modify(int nodeIndex, int position, int newValue) {
39        // Found the target leaf node
40        if (tree[nodeIndex]->left == position && tree[nodeIndex]->right == position) {
41            tree[nodeIndex]->value = newValue;
42            return;
43        }
44      
45        // Recurse to appropriate child
46        int mid = (tree[nodeIndex]->left + tree[nodeIndex]->right) >> 1;
47        if (position <= mid) {
48            modify(nodeIndex << 1, position, newValue);  // Go to left child
49        } else {
50            modify(nodeIndex << 1 | 1, position, newValue);  // Go to right child
51        }
52      
53        // Update current node's value based on children
54        pushup(nodeIndex);
55    }
56
57    // Update parent node value based on children (maintain max property)
58    void pushup(int nodeIndex) {
59        tree[nodeIndex]->value = max(
60            tree[nodeIndex << 1]->value,      // Left child's value
61            tree[nodeIndex << 1 | 1]->value   // Right child's value
62        );
63    }
64
65    // Query maximum value in range [left, right]
66    int query(int nodeIndex, int queryLeft, int queryRight) {
67        // Current segment is completely within query range
68        if (tree[nodeIndex]->left >= queryLeft && tree[nodeIndex]->right <= queryRight) {
69            return tree[nodeIndex]->value;
70        }
71      
72        int mid = (tree[nodeIndex]->left + tree[nodeIndex]->right) >> 1;
73        int maxValue = 0;
74      
75        // Query left child if needed
76        if (queryLeft <= mid) {
77            maxValue = query(nodeIndex << 1, queryLeft, queryRight);
78        }
79      
80        // Query right child if needed
81        if (queryRight > mid) {
82            maxValue = max(maxValue, query(nodeIndex << 1 | 1, queryLeft, queryRight));
83        }
84      
85        return maxValue;
86    }
87};
88
89class Solution {
90public:
91    // Find length of longest increasing subsequence with difference constraint k
92    int lengthOfLIS(vector<int>& nums, int k) {
93        // Create segment tree with size equal to maximum element in nums
94        SegmentTree* segTree = new SegmentTree(*max_element(nums.begin(), nums.end()));
95      
96        int maxLength = 1;  // Minimum LIS length is 1
97      
98        // Process each number in the array
99        for (int currentNum : nums) {
100            // Query maximum LIS length ending with values in range [currentNum - k, currentNum - 1]
101            // This ensures the difference constraint is satisfied
102            int currentLength = 1;  // Start with length 1 (current element alone)
103          
104            if (currentNum > 1) {  // Avoid querying invalid range
105                int rangeStart = max(1, currentNum - k);
106                int rangeEnd = currentNum - 1;
107                currentLength = segTree->query(1, rangeStart, rangeEnd) + 1;
108            }
109          
110            maxLength = max(maxLength, currentLength);
111          
112            // Update the segment tree with the best LIS length ending at currentNum
113            segTree->modify(1, currentNum, currentLength);
114        }
115      
116        return maxLength;
117    }
118};
119

1// Node structure for segment tree
2interface Node {
3    left: number;   // Left boundary of the segment
4    right: number;  // Right boundary of the segment
5    value: number;  // Maximum value in this segment
6}
7
8// Global segment tree nodes array
9let tree: Node[] = [];
10
11// Initialize segment tree with size n
12function initializeSegmentTree(n: number): void {
13    // Allocate 4*n nodes for the tree
14    tree = new Array(4 * n);
15    for (let i = 0; i < tree.length; i++) {
16        tree[i] = {
17            left: 0,
18            right: 0,
19            value: 0
20        };
21    }
22    // Build tree starting from root (index 1)
23    build(1, 1, n);
24}
25
26// Build the segment tree recursively
27function build(nodeIndex: number, left: number, right: number): void {
28    tree[nodeIndex].left = left;
29    tree[nodeIndex].right = right;
30  
31    // Leaf node - no need to recurse further
32    if (left === right) {
33        return;
34    }
35  
36    // Build left and right subtrees
37    const mid = (left + right) >> 1;  // Equivalent to Math.floor((left + right) / 2)
38    build(nodeIndex << 1, left, mid);  // Build left child (2 * nodeIndex)
39    build((nodeIndex << 1) | 1, mid + 1, right);  // Build right child (2 * nodeIndex + 1)
40}
41
42// Update the value at position to newValue
43function modify(nodeIndex: number, position: number, newValue: number): void {
44    // Found the target leaf node
45    if (tree[nodeIndex].left === position && tree[nodeIndex].right === position) {
46        tree[nodeIndex].value = newValue;
47        return;
48    }
49  
50    // Recurse to appropriate child
51    const mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1;
52    if (position <= mid) {
53        modify(nodeIndex << 1, position, newValue);  // Go to left child
54    } else {
55        modify((nodeIndex << 1) | 1, position, newValue);  // Go to right child
56    }
57  
58    // Update current node's value based on children
59    pushup(nodeIndex);
60}
61
62// Update parent node value based on children (maintain max property)
63function pushup(nodeIndex: number): void {
64    tree[nodeIndex].value = Math.max(
65        tree[nodeIndex << 1].value,      // Left child's value
66        tree[(nodeIndex << 1) | 1].value // Right child's value
67    );
68}
69
70// Query maximum value in range [queryLeft, queryRight]
71function query(nodeIndex: number, queryLeft: number, queryRight: number): number {
72    // Current segment is completely within query range
73    if (tree[nodeIndex].left >= queryLeft && tree[nodeIndex].right <= queryRight) {
74        return tree[nodeIndex].value;
75    }
76  
77    const mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1;
78    let maxValue = 0;
79  
80    // Query left child if needed
81    if (queryLeft <= mid) {
82        maxValue = query(nodeIndex << 1, queryLeft, queryRight);
83    }
84  
85    // Query right child if needed
86    if (queryRight > mid) {
87        maxValue = Math.max(maxValue, query((nodeIndex << 1) | 1, queryLeft, queryRight));
88    }
89  
90    return maxValue;
91}
92
93// Find length of longest increasing subsequence with difference constraint k
94function lengthOfLIS(nums: number[], k: number): number {
95    // Create segment tree with size equal to maximum element in nums
96    const maxElement = Math.max(...nums);
97    initializeSegmentTree(maxElement);
98  
99    let maxLength = 1;  // Minimum LIS length is 1
100  
101    // Process each number in the array
102    for (const currentNum of nums) {
103        // Query maximum LIS length ending with values in range [currentNum - k, currentNum - 1]
104        // This ensures the difference constraint is satisfied
105        let currentLength = 1;  // Start with length 1 (current element alone)
106      
107        if (currentNum > 1) {  // Avoid querying invalid range
108            const rangeStart = Math.max(1, currentNum - k);
109            const rangeEnd = currentNum - 1;
110            currentLength = query(1, rangeStart, rangeEnd) + 1;
111        }
112      
113        maxLength = Math.max(maxLength, currentLength);
114      
115        // Update the segment tree with the best LIS length ending at currentNum
116        modify(1, currentNum, currentLength);
117    }
118  
119    return maxLength;
120}
121

Time and Space Complexity

Time Complexity: O(n × log m), where n is the length of the array nums and m is the maximum value in nums.

The segment tree initialization takes O(m) time to build a tree with m leaf nodes
For each of the n elements in nums:
- The query operation traverses from root to leaf, taking O(log m) time
- The modify operation also traverses from root to leaf and calls pushup back up, taking O(log m) time
Total: O(m) + n × O(log m) = O(n × log m) since typically n × log m > m

Note: The reference answer states O(n × log n), which would be accurate if the segment tree was built on indices rather than values. In this implementation, the tree is built on the value range [1, max(nums)], making the complexity dependent on m = max(nums) rather than n.

Space Complexity: O(m), where m is the maximum value in nums.

The segment tree uses 4 × m nodes to store the tree structure
Each node stores three integers (l, r, v)
Total space: O(4m) = O(m)

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

Common Pitfalls

1. Handling Edge Cases with Invalid Query Ranges

One critical pitfall in this solution is when querying for values at the boundaries. When current_value - k is less than 1 or when current_value - 1 is less than current_value - k (which happens when current_value = 1), the query range becomes invalid.

The Problem:

# When current_value = 1, this becomes:
prev_max_length = segment_tree.query(1, 1 - k, 0)  # Invalid range!

This creates an invalid range where the left boundary is greater than the right boundary, potentially causing incorrect results or runtime errors.

Solution:

def lengthOfLIS(self, nums: List[int], k: int) -> int:
    segment_tree = SegmentTree(max(nums))
    max_length = 1
  
    for current_value in nums:
        # Handle edge case: ensure valid query range
        if current_value > 1:
            query_left = max(1, current_value - k)
            query_right = current_value - 1
            prev_max_length = segment_tree.query(1, query_left, query_right)
            current_length = prev_max_length + 1
        else:
            # When current_value = 1, it must be the first element of any subsequence
            current_length = 1
      
        max_length = max(max_length, current_length)
        segment_tree.modify(1, current_value, current_length)
  
    return max_length

2. Memory Optimization for Large Value Ranges

Another significant pitfall occurs when the maximum value in nums is very large (e.g., 10^9), but the array itself is small. The current implementation allocates 4 * max(nums) nodes, which can cause memory issues.

The Problem:

# If max(nums) = 10^9 and len(nums) = 100
# We allocate 4 * 10^9 nodes unnecessarily!
segment_tree = SegmentTree(max(nums))

Solution using Coordinate Compression:

def lengthOfLIS(self, nums: List[int], k: int) -> int:
    # Coordinate compression
    unique_values = sorted(set(nums))
    value_to_index = {v: i + 1 for i, v in enumerate(unique_values)}
  
    # Build segment tree with compressed size
    segment_tree = SegmentTree(len(unique_values))
    max_length = 1
  
    for current_value in nums:
        compressed_value = value_to_index[current_value]
      
        # Find range of valid previous values
        left_value = current_value - k
        right_value = current_value - 1
      
        # Binary search for compressed indices
        import bisect
        left_idx = bisect.bisect_left(unique_values, left_value)
        right_idx = bisect.bisect_right(unique_values, right_value) - 1
      
        if left_idx <= right_idx:
            prev_max_length = segment_tree.query(1, left_idx + 1, right_idx + 1)
            current_length = prev_max_length + 1
        else:
            current_length = 1
      
        max_length = max(max_length, current_length)
        segment_tree.modify(1, compressed_value, current_length)
  
    return max_length

3. Integer Overflow in Bit Operations

While Python handles large integers automatically, in other languages or when porting this code, bit operations might cause issues with large indices.

The Problem:

# For very deep trees, this might overflow in other languages
self.build(node_idx << 1, left, mid)  # 2 * node_idx might overflow

Solution: Add bounds checking or use regular multiplication for clarity:

def build(self, node_idx: int, left: int, right: int) -> None:
    # Add safety check
    if node_idx >= len(self.tree):
        raise ValueError("Tree index out of bounds")
  
    self.tree[node_idx].left_bound = left
    self.tree[node_idx].right_bound = right
  
    if left == right:
        return
  
    mid = (left + right) // 2  # Use regular division for clarity
    left_child = 2 * node_idx
    right_child = 2 * node_idx + 1
  
    # Ensure children indices are valid
    if right_child < len(self.tree):
        self.build(left_child, left, mid)
        self.build(right_child, mid + 1, right)

These modifications make the solution more robust and handle edge cases that could cause incorrect results or runtime errors in production environments.

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

2407. Longest Increasing Subsequence II

Problem Description

Intuition

Solution Approach

Segment Tree Structure

Building the Tree

Core Operations

Main Algorithm

Time Complexity

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Handling Edge Cases with Invalid Query Ranges

2. Memory Optimization for Large Value Ranges

3. Integer Overflow in Bit Operations

Recommended Readings