Given an array arr, the task is to find the length of The Longest Increasing Sequence using Binary Indexed Tree (BIT)
Examples:
Input: arr = {6, 5, 1, 3, 2, 4, 8, 7}
Output: 4
Explanation:
The possible subsequences are
{1 2 4 7}, {1 2 4 8},
{1 3 4 8}, {1 3 4 7}
Now insert the elements one by one from left to right:
6 is inserted: max length till 5 = 0, ans for 6 is 1
5 is inserted: max length till 4 = 0, ans for 5 is 1
1 is inserted: max length till 0 = 2, ans for 1 is 1
3 is inserted: max length till 2 = 1, ans for 3 is 2
2 is inserted: max length till 1 = 1, ans for 2 is 2
4 is inserted: max length till 3 = 2, ans for 4 is 3
8 is inserted: max length till 7 = 3, ans for 8 is 4
7 is inserted: max length till 6 = 3, ans for 7 is 4
Input: arr = {1, 2, 3, 4, 1, 5}
Output: 5
Prerequisite for this post: Binary Indexed Tree
Approach:
- First, use coordinate compression (replace all values of the array to numbers ranging from 1 to N). This will reduce the maximum number in the array and help us solve the above problem in NlogN time. Also, this will help us to reduce memory.
- Make a new array BIT of length N + 1.
- Now, traverse the array from left to right and add the current element to the BIT.
- When ith element (A[i]) is inserted in the BIT, check for the length of the longest subsequence that can be formed till A[i] – 1. Let this value be x. If x + 1 is greater than the current element in BIT, update the BIT.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to map// numbers using coordinate// compressionvoid coordinateCompression(int arr[], int n){ // Set will store // all unique numbers set<int> s; for (int i = 0; i < n; i++) { s.insert(arr[i]); } // Map will store // the new elements int index = 0; map<int, int> mp; set<int>::iterator itr; for (itr = s.begin(); itr != s.end(); itr++) { // For every new number in the set, index++; // Increment the index of the // current number and store it // in a hashmap. Here index // for every element is the // new value with the // current element is replaced mp[*itr] = index; } for (int i = 0; i < n; i++) { // now change the current element // to range 1 to N. arr[i] = mp[arr[i]]; }}// Function to calculate// length of maximum// increasing sequence till// i'th indexint query(int BIT[], int index, int n){ int ans = 0; while (index > 0) { ans = max(ans, BIT[index]); // Go to parent node index -= index & (-index); } return ans;}// Function for updating// BIT array for maximum// increasing sequence till// i'th indexvoid update(int BIT[], int index, int n){ // If 4 is inserted in BIT, // check for maximum length // subsequence till element 3. // Let this subsequence length be x. // If x + 1 is greater than // the current element in BIT, // update the BIT array int x = query(BIT, index - 1, n); int value = x + 1; while (index <= n) { // Store maximum length subsequence length till index // Here index is the // coordinate compressed element BIT[index] = max(BIT[index], value); // Go to child node and update that node index += index & (-index); }}// Function to calculate// maximum Longest Increasing// Sequence lengthint findLISLength(int arr[], int n){ coordinateCompression(arr, n); int BIT[n + 1]; // Initialising BIT array for (int i = 0; i <= n; i++) { BIT[i] = 0; } for (int i = 0; i < n; i++) { // Add elements // from left to right // in BIT update(BIT, arr[i], n); } int ans = query(BIT, n, n); return ans;}// Driver codeint main(){ int arr[] = { 6, 5, 1, 3, 2, 4, 8, 7 }; int n = sizeof(arr) / sizeof(int); int ans = findLISLength(arr, n); cout << ans << endl; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {// Function to map numbers using // coordinate compressionstatic void coordinateCompression(int arr[], int n){ // Set will store // all unique numbers Set<Integer> s = new HashSet<>(); for (int i = 0; i < n; i++) { s.add(arr[i]); } // Map will store // the new elements int index = 0; HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); for (int itr : s) { // For every new number in the set, index++; // Increment the index of the // current number and store it // in a hashmap. Here index // for every element is the // new value with the // current element is replaced mp.put(itr, index); } for (int i = 0; i < n; i++) { // now change the current element // to range 1 to N. arr[i] = mp.get(arr[i]); }}// Function to calculate length of maximum// increasing sequence till i'th indexstatic int query(int BIT[], int index, int n){ int ans = 0; while (index > 0) { ans = Math.max(ans, BIT[index]); // Go to parent node index -= index & (-index); } return ans;}// Function for updating BIT array for // maximum increasing sequence till// i'th indexstatic void update(int BIT[], int index, int n){ // If 4 is inserted in BIT, // check for maximum length // subsequence till element 3. // Let this subsequence length be x. // If x + 1 is greater than // the current element in BIT, // update the BIT array int x = query(BIT, index - 1, n); int value = x + 1; while (index <= n) { // Store maximum length subsequence length // till index. Here index is the // coordinate compressed element BIT[index] = Math.max(BIT[index], value); // Go to child node and update that node index += index & (-index); }}// Function to calculate maximum // Longest Increasing Sequence lengthstatic int findLISLength(int arr[], int n){ coordinateCompression(arr, n); int []BIT = new int[n + 1]; // Initialising BIT array for (int i = 0; i <= n; i++) { BIT[i] = 0; } for (int i = 0; i < n; i++) { // Add elements from left to right // in BIT update(BIT, arr[i], n); } int ans = query(BIT, n, n); return ans;}// Driver codepublic static void main(String[] args) { int arr[] = { 6, 5, 1, 3, 2, 4, 8, 7 }; int n = arr.length; int ans = findLISLength(arr, n); System.out.println(ans);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach# Function to map# numbers using coordinate# compressiondef coordinateCompression(arr, n): # Set will store # all unique numbers s = dict() for i in range(n): s[arr[i]] = 1 # Map will store # the new elements index = 0 mp = dict() for itr in sorted(s): # For every new number in the set, index += 1 # Increment the index of the # current number and store it # in a hashmap. Here index # for every element is the # new value with the # current element is replaced mp[itr] = index for i in range(n): # now change the current element # to range 1 to N. arr[i] = mp[arr[i]]# Function to calculate# length of maximum# increasing sequence till# i'th indexdef query(BIT, index, n): ans = 0 while (index > 0): ans = max(ans, BIT[index]) # Go to parent node index -= index & (-index) return ans# Function for updating# BIT array for maximum# increasing sequence till# i'th indexdef update(BIT, index, n): # If 4 is inserted in BIT, # check for maximum length # subsequence till element 3. # Let this subsequence length be x. # If x + 1 is greater than # the current element in BIT, # update the BIT array x = query(BIT, index - 1, n) value = x + 1 while (index <= n): # Store maximum length subsequence length till index # Here index is the # coordinate compressed element BIT[index] = max(BIT[index], value) # Go to child node and update that node index += index & (-index)# Function to calculate# maximum Longest Increasing# Sequence lengthdef findLISLength(arr, n): coordinateCompression(arr, n) BIT = [0]*(n + 1) for i in range(n): # Add elements # from left to right # in BIT update(BIT, arr[i], n) ans = query(BIT, n, n) return ans# Driver codearr=[6, 5, 1, 3, 2, 4, 8, 7]n = len(arr)ans = findLISLength(arr, n)print(ans)# This code is contributed mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{// Function to map numbers using // coordinate compressionstatic void coordinateCompression(int []arr, int n){ // Set will store // all unique numbers HashSet<int> s = new HashSet<int>(); for (int i = 0; i < n; i++) { s.Add(arr[i]); } // Map will store // the new elements int index = 0; Dictionary<int, int> mp = new Dictionary<int, int>(); foreach (int itr in s) { // For every new number in the set, index++; // Increment the index of the // current number and store it // in a hashmap. Here index // for every element is the // new value with the // current element is replaced mp.Add(itr, index); } for (int i = 0; i < n; i++) { // now change the current element // to range 1 to N. arr[i] = mp[arr[i]]; }}// Function to calculate // length of maximum increasing // sequence till i'th indexstatic int query(int []BIT, int index, int n){ int ans = 0; while (index > 0) { ans = Math.Max(ans, BIT[index]); // Go to parent node index -= index & (-index); } return ans;}// Function for updating BIT array for // maximum increasing sequence till// i'th indexstatic void update(int []BIT, int index, int n){ // If 4 is inserted in BIT, // check for maximum length // subsequence till element 3. // Let this subsequence length be x. // If x + 1 is greater than // the current element in BIT, // update the BIT array int x = query(BIT, index - 1, n); int value = x + 1; while (index <= n) { // Store maximum length subsequence length // till index. Here index is the // coordinate compressed element BIT[index] = Math.Max(BIT[index], value); // Go to child node and update that node index += index & (-index); }}// Function to calculate maximum // longest Increasing Sequence lengthstatic int findLISLength(int []arr, int n){ coordinateCompression(arr, n); int []BIT = new int[n + 1]; // Initialising BIT array for (int i = 0; i <= n; i++) { BIT[i] = 0; } for (int i = 0; i < n; i++) { // Add elements from // left to right in BIT update(BIT, arr[i], n); } int ans = query(BIT, n, n) / 2; return ans;}// Driver codepublic static void Main(String[] args) { int []arr = {6, 5, 1, 3, 2, 4, 8, 7}; int n = arr.Length; int ans = findLISLength(arr, n); Console.WriteLine(ans);}}// This code is contributed by gauravrajput1 |
Javascript
<script>// JavaScript implementation of the approach// Function to map numbers using// coordinate compressionfunction coordinateCompression(arr, n) { // Set will store // all unique numbers let s = new Set(); for (let i = 0; i < n; i++) { s.add(arr[i]); } // Map will store // the new elements let index = 0; let mp = new Map(); for (let itr of s) { // For every new number in the set, index++; // Increment the index of the // current number and store it // in a hashmap. Here index // for every element is the // new value with the // current element is replaced mp.set(itr, index); } for (let i = 0; i < n; i++) { // now change the current element // to range 1 to N. arr[i] = mp.get(arr[i]); }}// Function to calculate length of maximum// increasing sequence till i'th indexfunction query(BIT, index, n) { let ans = 0; while (index > 0) { ans = Math.max(ans, BIT[index]); // Go to parent node index -= index & (-index); } return ans;}// Function for updating BIT array for// maximum increasing sequence till// i'th indexfunction update(BIT, index, n) { // If 4 is inserted in BIT, // check for maximum length // subsequence till element 3. // Let this subsequence length be x. // If x + 1 is greater than // the current element in BIT, // update the BIT array let x = query(BIT, index - 1, n); let value = x + 1; while (index <= n) { // Store maximum length subsequence length // till index. Here index is the // coordinate compressed element BIT[index] = Math.max(BIT[index], value); // Go to child node and update that node index += index & (-index); }}// Function to calculate maximum// Longest Increasing Sequence lengthfunction findLISLength(arr, n) { coordinateCompression(arr, n); let BIT = new Array(n + 1); // Initialising BIT array for (let i = 0; i <= n; i++) { BIT[i] = 0; } for (let i = 0; i < n; i++) { // Add elements from left to right // in BIT update(BIT, arr[i], n); } let ans = query(BIT, n, n) / 2; return ans;}// Driver codelet arr = [6, 5, 1, 3, 2, 4, 8, 7];let n = arr.length;let ans = findLISLength(arr, n);document.write(ans);// This code is contributed by _saurabh_jaiswal</script> |
4
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Find More here on that Topic: geeksforgeeks.org/longest-increasing-subsequence-using-bit/ […]
… [Trackback]
[…] Find More Information here on that Topic: geeksforgeeks.org/longest-increasing-subsequence-using-bit/ […]
… [Trackback]
[…] Here you will find 89216 more Info on that Topic: geeksforgeeks.org/longest-increasing-subsequence-using-bit/ […]
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/longest-increasing-subsequence-using-bit/ […]