300. Longest Increasing Subsequence


Problem Description

The problem is about finding the length of the longest strictly increasing subsequence within an array of integers named nums. A subsequence is defined as a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. A strictly increasing subsequence means each element must be larger than the previous one in the subsequence. For example, in [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101], and its length is 4.

Intuition

To solve this problem effectively, we can utilize the concept of Dynamic Programming (DP) or Binary Indexed Trees (Fenwick Tree). The intuition behind using these approaches is efficiency in both computation and memory usage.

Using Dynamic Programming to solve this problem would involve creating an array where each element dp[i] represents the length of the longest increasing subsequence that ends with the i-th element of the input array. To find the value of dp[i], we look at all previous elements j, where j < i, and if nums[j] < nums[i], that means nums[i] can extend the subsequence ending with nums[j], so we pick the maximum length out of all possible j.

However, the given solution uses a Binary Indexed Tree (BIT), which is a data structure that helps with efficiently updating elements and querying prefixes in a log-scaled time. The BIT is an advanced optimization usually used to improve the running time complexity from O(N^2) to O(N log N), where N is the number of elements in the input array.

The solution employs coordinate compression technique by sorting the unique elements to reduce the range of numbers, maintaining the original order of elements. This helps us to use the BIT effectively. For every element x in the compressed coords, we use 'query' to find the longest increasing subsequence that ends before x and 'update' to extend the subsequence ending at x if it's longer than the previously recorded one. Thus, we maintain the length of the LIS up to each point in the array leveraging the BIT's efficient update and query capabilities.

Learn more about Binary Search and Dynamic Programming patterns.

Solution Approach

The solution provided uses a Binary Indexed Tree (BIT), also known as a Fenwick Tree, to keep track of the maximum subsequence's length during the iteration of the numbers in nums. Here's a walkthrough of the implementation:

  1. Coordinate Compression: We start by compressing the coordinates of nums. This is done by creating a sorted list s of the unique elements in nums. This step is key because it maps the large or non-consecutive input space into a smaller and consecutive range, which is essential to correctly harness the power of BITs.

  2. Initialization: We initialize the BIT with the size equal to the number of unique elements in nums. The BIT is represented by a list self.c and supports the update and query operations.

    • Update: The update method updates the BIT with a new element's length of the longest increasing subsequence. It takes an input x representing the index in the BIT and v as the value to update (length of LIS). The method updates the elements in the BIT by comparing and setting the current indexed value with the maximum between the existing value and v.

      1self.c[x] = max(self.c[x], v)
    • Query: The query method retrieves the largest value of the subsequence's length from the BIT up to the index x. The result is the length of the longest increasing subsequence considering elements up to the index x.

      1mx = max(mx, self.c[x])
  3. Iteration: For each number x in the input list nums, we do the following:

    • Find the index of x in the compressed coordinates (the sorted list s). This index is used to look up and update the BIT.

    • Query the BIT for the index just below the current element (i.e., x - 1). The BIT returns the length of the longest subsequence before x.

    • Increment the length by 1, which represents that x can extend the subsequence.

    • Update the answer holding the maximum length observed so far, and also update the BIT at the position x with the new length of the subsequence.

  4. Result: Once the iteration is completed, the variable ans holds the length of the longest increasing subsequence.

The beauty of this approach lies in its efficiency. While a straightforward Dynamic Programming approach would have a time complexity of O(N^2), using a BIT brings it down to O(N log N) because both update and query operations on a BIT are performed in O(log N) time.

In conclusion, the reference approach mentioned that one can use either Dynamic Programming or a Binary Indexed Tree. The solution provided implements the latter for an efficient resolution of the Longest Increasing Subsequence problem.

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

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

Example Walkthrough

Let's consider an input array nums with the following integers: [3, 1, 5, 2, 6].

  1. Coordinate Compression:

    • We begin by sorting the unique elements of nums: [1, 2, 3, 5, 6].
    • Next, we map them to their indices in this sorted array: 1 -> 0, 2 -> 1, 3 -> 2, 5 -> 3, 6 -> 4.
  2. Initialization:

    • We then initialize a Binary Indexed Tree (BIT) to keep track of the maximum length of the increasing subsequence. Since we have 5 unique numbers, the BIT size will be 5.
  3. Iteration:

    • For each number in nums:
      • We find the index in the sorted array: 3 -> 2, 1 -> 0, 5 -> 3, 2 -> 1, 6 -> 4.
      • We query the BIT for the index just below the current element's index to find the longest subsequence before it and then add 1 for the current element. We also update the BIT at that index.
      • Iterative Steps:
        • For 3: Query BIT for index 1, get 0. Update BIT at index 2 with 0+1 = 1.
        • For 1: Query BIT for index -1, get 0. Update BIT at index 0 with 0+1 = 1.
        • For 5: Query BIT for index 2, get 1. Update BIT at index 3 with 1+1 = 2.
        • For 2: Query BIT for index 0, get 1. Update BIT at index 1 with 1+1 = 2.
        • For 6: Query BIT for index 3, get 2. Update BIT at index 4 with 2+1 = 3.
  4. Result:

    • The last update indicates that the longest increasing subsequence has a length of 3, which corresponds to either [1, 2, 6] or [1, 5, 6]. Hence, the result for this example is 3.

By using coordinate compression, we efficiently map our problem into a smaller space where the BIT can operate. With each iteration updating and querying the BIT, we maintain optimal running time. This approach significantly reduces the computational complexity from O(N^2) in the native dynamic programming approach to O(N log N).

Solution Implementation

1from bisect import bisect_left
2
3class BinaryIndexedTree:
4    def __init__(self, size: int):
5        # Initialize the size of the binary indexed tree and the storage array
6        self.size = size
7        self.tree = [0] * (size + 1)
8
9    def update(self, index: int, value: int):
10        # Update the tree with the given value at the given index
11        while index <= self.size:
12            self.tree[index] = max(self.tree[index], value)
13            index += index & -index
14
15    def query(self, index: int) -> int:
16        # Query the max value up to the given index
17        max_value = 0
18        while index:
19            max_value = max(max_value, self.tree[index])
20            index -= index & -index
21        return max_value
22
23
24class Solution:
25    def length_of_lis(self, nums: List[int]) -> int:
26        # Sort and deduplicate the input numbers to map the values to tree indices
27        sorted_unique_nums = sorted(set(nums))
28        tree = BinaryIndexedTree(len(sorted_unique_nums))
29      
30        # Initialize the answer to the length of the LIS found so far
31        longest_increasing_subseq_length = 1
32      
33        # Process each number in the input list
34        for num in nums:
35            # Get the index of the number in the sorted unique array, plus one
36            tree_index = bisect_left(sorted_unique_nums, num) + 1
37          
38            # Query the tree for the current length of LIS ending with a number less than the current one
39            length_up_to_num = tree.query(tree_index - 1) + 1
40          
41            # Update the answer with the maximal length found
42            longest_increasing_subseq_length = max(longest_increasing_subseq_length, length_up_to_num)
43          
44            # Update the tree for this index with the current length of LIS
45            tree.update(tree_index, length_up_to_num)
46      
47        # Return the length of the longest increasing subsequence
48        return longest_increasing_subseq_length
49
1class Solution {
2    public int lengthOfLIS(int[] nums) {
3        // Clone nums array and sort it to remove duplicates and to have a sorted reference array
4        int[] sortedArray = nums.clone();
5        Arrays.sort(sortedArray);
6      
7        // Remove duplicates in the sorted array to construct a unique set of numbers
8        int uniqueNumsCount = 0;
9        int length = sortedArray.length;
10        for (int i = 0; i < length; ++i) {
11            if (i == 0 || sortedArray[i] != sortedArray[i - 1]) {
12                sortedArray[uniqueNumsCount++] = sortedArray[i];
13            }
14        }
15      
16        // Initialize a Binary Indexed Tree, or Fenwick Tree
17        BinaryIndexedTree tree = new BinaryIndexedTree(uniqueNumsCount);
18      
19        // Initialize the answer with 1 considering a single element will have LIS as 1
20        int maxLISLength = 1;
21      
22        // Iterate over the original array and update Fenwick Tree for each number
23        for (int num : nums) {
24            int index = binarySearch(sortedArray, num, uniqueNumsCount);
25            int currentLISLength = tree.query(index - 1) + 1;
26            maxLISLength = Math.max(maxLISLength, currentLISLength);
27            tree.update(index, currentLISLength);
28        }
29        return maxLISLength;
30    }
31
32    private int binarySearch(int[] nums, int target, int rightBound) {
33        // Perform binary search for the position of target in nums within bounds [0, rightBound]
34        int left = 0;
35        while (left < rightBound) {
36            int mid = (left + rightBound) >> 1;
37            if (nums[mid] >= target) {
38                rightBound = mid;
39            } else {
40                left = mid + 1;
41            }
42        }
43        // Return the position index of the target incremented by 1 to adjust for BIT index
44        return left + 1;
45    }
46}
47
48class BinaryIndexedTree {
49    private int size;
50    private int[] tree;
51
52    public BinaryIndexedTree(int size) {
53        this.size = size;
54        tree = new int[size + 1];
55    }
56
57    public void update(int index, int value) {
58        // Update the tree with new value at the given index 
59        // (BIT index is 1-based, hence increment the input index by 1)
60        while (index <= size) {
61            tree[index] = Math.max(tree[index], value);
62            index += index & -index;
63        }
64    }
65
66    public int query(int index) {
67        // Query the largest value up to the given index
68        int maxValue = 0;
69        while (index > 0) {
70            maxValue = Math.max(maxValue, tree[index]);
71            index -= index & -index;
72        }
73        return maxValue;
74    }
75}
76
1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6// BinaryIndexedTree (a.k.a. Fenwick Tree) helps to perform efficient
7// range queries and updates on an array of numbers.
8class BinaryIndexedTree {
9public:
10    // Constructor initializes the tree with the given size.
11    explicit BinaryIndexedTree(int size)
12        : size_(size)
13        , tree_(size + 1) {}
14
15    // Update the tree by setting the maximum value at position x to v.
16    void Update(int x, int v) {
17        while (x <= size_) {
18            tree_[x] = max(tree_[x], v); // Ensure we only store the maximum value.
19            x += x & -x; // Move to the next index to update.
20        }
21    }
22
23    // Query the maximum value from 1 to x in the tree.
24    int Query(int x) const {
25        int max_value = 0;
26        while (x > 0) {
27            max_value = max(max_value, tree_[x]); // Update the max_value with the maximum up to index x.
28            x -= x & -x; // Move to the preceding elements' index.
29        }
30        return max_value;
31    }
32
33private:
34    int size_;               // The size of the tree.
35    vector<int> tree_;       // The tree represented as a vector where the tree's values are stored.
36};
37
38// Solution class contains the method lengthOfLIS which computes
39// the length of the Longest Increasing Subsequence in an array of numbers.
40class Solution {
41public:
42    // Computes the length of the longest increasing subsequence.
43    int lengthOfLIS(vector<int>& nums) {
44        vector<int> sortedNums = nums;
45      
46        // Sort the elements and remove duplicates to compress the values.
47        sort(sortedNums.begin(), sortedNums.end());
48        auto lastUnique = unique(sortedNums.begin(), sortedNums.end());
49        sortedNums.erase(lastUnique, sortedNums.end());
50      
51        // Initialize the Binary Indexed Tree with the size of the unique sorted list.
52        BinaryIndexedTree tree(sortedNums.size());
53      
54        int longest = 1; // Base case: the minimum length of LIS is 1.
55
56        // Iterating through each number in nums.
57        for (int num : nums) {
58            // Map the number to its index in the sorted array (1-indexed).
59            int index = lower_bound(sortedNums.begin(), sortedNums.end(), num) - sortedNums.begin() + 1;
60          
61            // Query the tree to find the length of the LIS ending before the current number.
62            int prevLIS = tree.Query(index - 1) + 1; // Adding 1 includes the current number in the sequence.
63          
64            // Update the answer with the maximum LIS found so far.
65            longest = max(longest, prevLIS);
66
67            // Update the tree with the LIS for this index.
68            tree.Update(index, prevLIS);
69        }
70
71        // Return the length of the longest increasing subsequence.
72        return longest;
73    }
74};
75
1// Number of elements handled by the tree
2let treeSize: number;
3// BIT data structure array
4let bitTree: number[];
5
6// Initialize the Binary Indexed Tree with a given size
7function initializeBIT(size: number) {
8    treeSize = size;
9    bitTree = new Array(size + 1).fill(0);
10}
11
12// Update the BIT with a value at a specific index
13function updateBIT(index: number, value: number) {
14    // Loop until end of tree array
15    while (index <= treeSize) {
16        // Update maximum value for index
17        bitTree[index] = Math.max(bitTree[index], value);
18        // Move to next index
19        index += index & -index;
20    }
21}
22
23// Query the maximum value up to a specific index
24function queryBIT(index: number): number {
25    let maxVal = 0;
26    // Accumulate maximum values from the tree
27    while (index) {
28        maxVal = Math.max(maxVal, bitTree[index]);
29        // Move to previous index
30        index -= index & -index;
31    }
32    return maxVal;
33}
34
35// Find the length of the Longest Increasing Subsequence (LIS) in an array
36function lengthOfLIS(nums: number[]): number {
37    // Remove duplicates and sort the elements
38    const uniqueSortedNums = [...new Set(nums)].sort((a, b) => a - b);
39    // Initialize the BIT with the size of unique elements
40    initializeBIT(uniqueSortedNums.length);
41    let ans = 1;
42
43    for (let num of nums) {
44        // Map current number to its index in the sorted array
45        let mappedIndex = binarySearch(uniqueSortedNums, num);
46        // Query the maximum value found before the current number's index
47        const maxVal = queryBIT(mappedIndex - 1) + 1;
48        // Update answer with the maximum value found
49        ans = Math.max(ans, maxVal);
50        // Update the BIT with the new value
51        updateBIT(mappedIndex, maxVal);
52    }
53
54    return ans;
55}
56
57// Perform binary search to find the index of a given number 'target' in 'nums'
58function binarySearch(nums: number[], target: number): number {
59    let left = 0;
60    let right = nums.length - 1;
61    while (left < right) {
62        // Go to the middle index
63        const mid = (left + right) >> 1;
64        // Narrow down left or right boundary
65        if (nums[mid] >= target) {
66            right = mid;
67        } else {
68            left = mid + 1;
69        }
70    }
71    // Convert 0-based index to 1-based for BIT operations
72    return left + 1;
73}
74

Time and Space Complexity

Time Complexity

The lengthOfLIS function has several components to analyze:

  1. Sorting the set of unique elements: O(U * log(U)), where U is the number of unique elements in nums.

  2. Binary indexed tree operations:

    • Each update operation is O(log(N)), where N is the length of the unique set after sorting.
    • Each query operation is also O(log(N)).

    Since both tree operations occur inside a loop that runs once for each element in nums, the complexity for these is O(N * log(N)), where "N" here refers to the number of elements in nums.

Therefore, combining sorting with the tree operations, the overall time complexity is O(U * log(U) + N * log(N)). Since the set of unique elements U cannot be larger than the total number of elements N, the time complexity simplifies to O(N * log(N)).

Space Complexity

  1. The space for the sorted set of unique elements: O(U).
  2. The space for the BinaryIndexedTree class, which includes an array c: O(N + 1) for the + 1 is appended to handle 1-based indexing.

The overall space complexity thus is the larger of the two, which is O(N) due to the binary indexed tree array adding an element for 1-based indexing.

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


Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄