Given an array arr[] of size N, the task is to find the length of the Longest Increasing Subsequence (LIS) i.e., the longest possible subsequence in which the elements of the subsequence are sorted in increasing order, in O(N log N).
Examples:
Input: arr[] = {3, 10, 2, 1, 20}
Output: 3
Explanation: The longest increasing subsequence is 3, 10, 20Input: arr[] = {3, 2}
Output:1
Explanation: The longest increasing subsequences are {3} and {2}Input: arr[] = {50, 3, 10, 7, 40, 80}
Output: 4
Explanation: The longest increasing subsequence is {3, 7, 40, 80}
Longest Increasing Subsequence using Binary Search:
The main idea of the approach is to simulate the process of finding a subsequence by maintaining a list of “buckets” where each bucket represents a valid subsequence. Initially, we start with an empty list and iterate through the input vector nums from left to right.
For each number in nums, we perform the following steps:
- If the number is greater than the last element of the last bucket (i.e., the largest element in the current subsequence), we append the number to the end of the list. This indicates that we have found a longer subsequence.
- Otherwise, we perform a binary search on the list of buckets to find the smallest element that is greater than or equal to the current number. This step helps us maintain the property of increasing elements in the buckets.
- Once we find the position to update, we replace that element with the current number. This keeps the buckets sorted and ensures that we have the potential for a longer subsequence in the future.
Below is the implementation of the above approach:
C++
// Binary Search Approach of Finding LIS by// reducing the problem to longest// common Subsequence#include <bits/stdc++.h>using namespace std;int lengthOfLIS(vector<int>& nums){ // Binary search approach int n = nums.size(); vector<int> ans; // Initialize the answer vector with the // first element of nums ans.push_back(nums[0]); for (int i = 1; i < n; i++) { if (nums[i] > ans.back()) { // If the current number is greater // than the last element of the answer // vector, it means we have found a // longer increasing subsequence. // Hence, we append the current number // to the answer vector. ans.push_back(nums[i]); } else { // If the current number is not // greater than the last element of // the answer vector, we perform // a binary search to find the smallest // element in the answer vector that // is greater than or equal to the // current number. // The lower_bound function returns // an iterator pointing to the first // element that is not less than // the current number. int low = lower_bound(ans.begin(), ans.end(), nums[i]) - ans.begin(); // We update the element at the // found position with the current number. // By doing this, we are maintaining // a sorted order in the answer vector. ans[low] = nums[i]; } } // The length of the answer vector // represents the length of the // longest increasing subsequence. return ans.size();}// Driver program to test above functionint main(){ vector<int> nums = { 10, 22, 9, 33, 21, 50, 41, 60 }; // Function call printf("Length of LIS is %d\n", lengthOfLIS(nums)); return 0;} |
Java
import java.util.*;public class GFG { static int lengthOfLIS(int[] nums) { // Binary search approach int n = nums.length; List<Integer> ans = new ArrayList<>(); // Initialize the answer list with the // first element of nums ans.add(nums[0]); for (int i = 1; i < n; i++) { if (nums[i] > ans.get(ans.size() - 1)) { // If the current number is greater // than the last element of the answer // list, it means we have found a // longer increasing subsequence. // Hence, we append the current number // to the answer list. ans.add(nums[i]); } else { // If the current number is not // greater than the last element of // the answer list, we perform // a binary search to find the smallest // element in the answer list that // is greater than or equal to the // current number. // The binarySearch method returns // the index of the first element that is not less than // the current number. int low = Collections.binarySearch(ans, nums[i]); // We update the element at the // found position with the current number. // By doing this, we are maintaining // a sorted order in the answer list. if (low < 0) { low = -(low + 1); } ans.set(low, nums[i]); } } // The size of the answer list // represents the length of the // longest increasing subsequence. return ans.size(); } // Driver program to test above function public static void main(String[] args) { int[] nums = {10, 22, 9, 33, 21, 50, 41, 60}; // Function call System.out.println("Length of LIS is " + lengthOfLIS(nums)); }} |
Python3
def lengthOfLIS(nums): # Binary search approach n = len(nums) ans = [] # Initialize the answer list with the # first element of nums ans.append(nums[0]) for i in range(1, n): if nums[i] > ans[-1]: # If the current number is greater # than the last element of the answer # list, it means we have found a # longer increasing subsequence. # Hence, we append the current number # to the answer list. ans.append(nums[i]) else: # If the current number is not # greater than the last element of # the answer list, we perform # a binary search to find the smallest # element in the answer list that # is greater than or equal to the # current number. low = 0 high = len(ans) - 1 while low < high: mid = low + (high - low) // 2 if ans[mid] < nums[i]: low = mid + 1 else: high = mid # We update the element at the # found position with the current number. # By doing this, we are maintaining # a sorted order in the answer list. ans[low] = nums[i] # The length of the answer list # represents the length of the # longest increasing subsequence. return len(ans)# Driver program to test above functionif __name__ == "__main__": nums = [10, 22, 9, 33, 21, 50, 41, 60] # Function call print("Length of LIS is", lengthOfLIS(nums)) |
C#
using System;using System.Collections.Generic;class GFG{ static int LengthOfLIS(List<int> nums) { // Binary search approach int n = nums.Count; List<int> ans = new List<int>(); // Initialize the answer list with the // first element of nums ans.Add(nums[0]); for (int i = 1; i < n; i++) { if (nums[i] > ans[ans.Count - 1]) { // If the current number is greater // than the last element of the answer // list, it means we have found a // longer increasing subsequence. // Hence, we append the current number // to the answer list. ans.Add(nums[i]); } else { // If the current number is not // greater than the last element of // the answer list, we perform // a binary search to find the smallest // element in the answer list that // is greater than or equal to the // current number. // The BinarySearch method returns // the index of the first element that is not less than // the current number. int low = ans.BinarySearch(nums[i]); // We update the element at the // found position with the current number. // By doing this, we are maintaining // a sorted order in the answer list. if (low < 0) { low = ~low; } ans[low] = nums[i]; } } // The count of the answer list // represents the length of the // longest increasing subsequence. return ans.Count; } // Driver program to test above function static void Main() { List<int> nums = new List<int> { 10, 22, 9, 33, 21, 50, 41, 60 }; // Function call Console.WriteLine("Length of LIS is " + LengthOfLIS(nums)); }} |
Javascript
function lengthOfLIS(nums) { // Binary search approach const n = nums.length; const ans = []; // Initialize the answer array with the first element of nums ans.push(nums[0]); for (let i = 1; i < n; i++) { if (nums[i] > ans[ans.length - 1]) { // If the current number is greater than the last element // of the answer array, it means we have found a // longer increasing subsequence. Hence, we push the current number // to the answer array. ans.push(nums[i]); } else { // If the current number is not greater than the last element of // the answer array, we perform a binary search to find the smallest // element in the answer array that is greater than or equal to the // current number. // The indexOf function returns the first index at which the current // number can be inserted to maintain sorted order. const low = ans.findIndex((el) => el >= nums[i]); // We update the element at the found position with the current number. // By doing this, we are maintaining a sorted order in the answer array. ans[low] = nums[i]; } } // The length of the answer array represents the length of the // longest increasing subsequence. return ans.length;}// Driver program to test the functionconst nums = [10, 22, 9, 33, 21, 50, 41, 60];// Function callconsole.log("Length of LIS is " + lengthOfLIS(nums)); |
Output
Length of LIS is 5
Time Complexity: O(n*log(n)) where n is the size of the input vector nums.
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!
