Longest Increasing Consecutive Subsequence

Difficulty Level Easy
Frequently asked in Amazon Google Microsoft
Array Dynamic ProgrammingViews 1872

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.

Example

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

Possible subsets

6,7

2,3,4,5

9,10

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!

Code

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++)
        {
            if(hash.containsKey(arr[i]-1))
            {
                hash.put(arr[i],hash.get(arr[i]-1)+1);
                hash.remove(arr[i]-1);
            }
            else
                hash.put(arr[i],1);
        }
        return Collections.max(hash.values());
    }
    public static void main(String args[]) 
    { 
        int arr[]={3, 10, 3, 11, 4, 5, 6, 7, 8, 12};
        System.out.println(LICS(arr));
    }
}
3, 10, 3, 11, 4, 5, 6, 7, 8, 12
6

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.

C++ Code to find Longest Increasing Consecutive Subsequence Length

#include<bits/stdc++.h>
using namespace std;
int maxs(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
int LICS(int arr[],int n)
{
    unordered_map<int,int>store;
    int max=-1;
    for(int i=0;i<n;i++)
    {
        if(store.find(arr[i]-1)!=store.end())
        {
            store[arr[i]]=store[arr[i]-1]+1;
        }
        else
            store[arr[i]]=1;
        max=maxs(max,store[arr[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
6

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)
Translate ยป