300. Longest Increasing Subsequence

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