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> |
Output:
4
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
