Longest Increasing Consecutive Subsequence  

Difficulty Level Easy
Frequently asked in Amazon Google Microsoft
Array Dynamic Programming

Subsequences are another topic loved by interviewers. Tweaking them around can always give them new opportunities for testing candidates. It can check the candidate’s ability to think and analyze things and come up with the best and optimal solutions. Today we are solving a subsequence problem that will be doing the same “Longest Increasing Consecutive Subsequences”.

Problem Statement  

Firstly let us look at what the problem has to convey. We are given an array of integers. This array is unsorted. Our task is to find out the largest subset which is increasing. The rule is stating that these integers should have a difference of one between them.


6, 7, 2, 3, 4, 5, 9, 10

Possible subsets


Please click Like if you loved this article?



Length of Longest Increasing Subsequence: 4

As an image is worth a thousand words. Let us look at an image illustrating the same. The red region in the image shows the eligible subset.

Longest Increasing Consecutive Subsequence

Approach for LICS length  

There are several methods to solve this problem ranging from Brute force to DP. Whenever such questions are asked we tend to take the easier road and look into Brute Force. But, do not worry. I am here to save you the embarrassment with the best solution.

  • Firstly, we create a HashMap
  • This HashMap stores the length of subsequences we have
  • The key in this HashMap is the number.
  • The value is the length of the subsequence associated with it.
  • Secondly, we iterate through the array
  • We check for arr[i]-1.
  • If the HashMap has the key we add to the subsequence
  • We can delete the previous key for our convenience and to store space
  • If the HashMap does not have the key
  • We add 1 as the key of the current element
  • Lastly, we find the maximum of all length
  • Thus, we have the LICS now!
See also
Minimum Absolute Difference Leetcode Solution


Now that we have understood how are solving this problem. Firstly let us put our ideas to code with a Java Code.

Java Code to find Longest Increasing Consecutive Subsequence length

import java.util.*;
public class Main
    public static int LICS(int[] arr)
        HashMap<Integer,Integer>hash=new HashMap<Integer,Integer>();
        for(int i=0;i<arr.length;i++)
        return Collections.max(hash.values());
    public static void main(String args[]) 
        int arr[]={3, 10, 3, 11, 4, 5, 6, 7, 8, 12};
3, 10, 3, 11, 4, 5, 6, 7, 8, 12

As we are switching from Java to C++. We are switching from Collection Framework to STL. Thus, we are transitioning to unordered maps from HashMap. Now that we know the changes let us switch the language.

Please click Like if you loved this article?

C++ Code to find Longest Increasing Consecutive Subsequence Length

using namespace std;
int maxs(int a,int b)
        return a;
        return b;
int LICS(int arr[],int n)
    int max=-1;
    for(int i=0;i<n;i++)
    return max;
int main()
    int a[] = { 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 }; 
    int n = sizeof(a) / sizeof(a[0]); 
    cout << LICS(a, n); 
    return 0; 
3, 10, 3, 11, 4, 5, 6, 7, 8, 12

Complexity Analysis  

Time Complexity=O(N)

  • We loop through the entire array
  • We are considering one element at a time
  • Thus, the time complexity is O(N)

Space Complexity=O(N)

  • We are putting the keys as numbers
  • Even on removing keys, in the best case, there can be just one key
  • However, in the worse case, we might end up adding all the elements to the HashMap
  • Which leads to space complexity of O(N)
Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.