Longest Harmonious Subsequence
You are given an array ‘ARR’ of 'N' integers. Your task is to find the longest harmonious subsequence of this array.

A sequence is Harmonious if the difference between the maximum and the minimum of all the elements is exactly 1.

For example

[3, 4, 3, 3, 3, 3, 4] is a harmonic array as the maximum of all the elements is 4 and minimum of all the elements is 3. So, the difference between the maximum and the minimum = 4 - 3 = 1.

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow. The first line of each test case contains an integer N, which denotes the number of integers in the array ‘ARR’. The second line of each test case contains 'N' integers of the array ‘ARR’, separated by space.

Output Format:

For each test case, return the size of the longest harmonious subsequence.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Longest Harmonious Subsequence

You are given an array ‘ARR’ of 'N' integers. Your task is to find the longest harmonious subsequence of this array.

A sequence is Harmonious if the difference between the maximum and the minimum of all the elements is exactly 1.

For example

[3, 4, 3, 3, 3, 3, 4] is a harmonic array as the maximum of all the elements is 4 and minimum of all the elements is 3. So, the difference between the maximum and the minimum = 4 - 3 = 1.

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains an integer N, which denotes the number of integers in the array ‘ARR’.

The second line of each test case contains 'N' integers of the array ‘ARR’, separated by space.

Output Format:

For each test case, return the size of the longest harmonious subsequence.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1<= T <= 100
1 <= N <= 10^4
1 <= ARR[i] <= 10^8

Time Limit: 1 sec

Accepted Answer

The idea is to generate all the possible subsequences using the bit masking technique. For each subsequence, check if it is a Harmonious subsequence or not. Take the maximum length of all the possible subsequences.

The steps are as follows:

Initialize 'ANSWER' to 0, which denotes the longest length of the Harmonic subsequence.
Iterate from ‘i’ = 0 to ‘2^N - 1’, where ‘N’ is the length of the given Array, ‘ARR’.
- Initialize three integers ‘MIN_VALUE’, ‘MAX_VALUE’, and ‘COUNT_LENGTH’ with INT_MAX, INT_MIN, and 0 respectively which stores the minimum, maximum values of the current subsequence and length of the current subsequence respectively.
- Iterate from ‘j’ = 0 to ‘N-1’:
  - If a jth bit of i is set and ‘MIN_VALUE’ is less than ARR[j], then update ‘MIN_VALUE’ to ARR[j].
  - If a jth bit of i is set and ‘MAX_VALUE’ is greater than ARR[j], then update ‘MAX_VALUE’ to ARR[j].
  - Increment the count as we are including the current element in the subsequence.
- If the difference between the ‘MAX_VALUE’ and ‘MIN_VALUE’ is 1. It means it is a valid subsequence. Update 'ANSWER' to a maximum of 'ANSWER' and ‘COUNT_LENGTH’. Also, take care of the integer overflow.
Return 'ANSWER’ as the final answer.

Accepted Answer

Brute Force

The idea is to generate all the possible subsequences using the bit masking technique. For each subsequence, check if it is a Harmonious subsequence or not. Take the maximum length of all the possible subsequences.

The steps are as follows:

Initialize 'ANSWER' to 0, which denotes the longest length of the Harmonic subsequence.
Iterate from ‘i’ = 0 to ‘2^N - 1’, where ‘N’ is the length of the given Array, ‘ARR’.
- Initialize three integers ‘MIN_VALUE’, ‘MAX_VALUE’, and ‘COUNT_LENGTH’ with INT_MAX, INT_MIN, and 0 respectively which stores the minimum, maximum values of the current subsequence and length of the current subsequence respectively.
- Iterate from ‘j’ = 0 to ‘N-1’:
  - If a jth bit of i is set and ‘MIN_VALUE’ is less than ARR[j], then update ‘MIN_VALUE’ to ARR[j].
  - If a jth bit of i is set and ‘MAX_VALUE’ is greater than ARR[j], then update ‘MAX_VALUE’ to ARR[j].
  - Increment the count as we are including the current element in the subsequence.
- If the difference between the ‘MAX_VALUE’ and ‘MIN_VALUE’ is 1. It means it is a valid subsequence. Update 'ANSWER' to a maximum of 'ANSWER' and ‘COUNT_LENGTH’. Also, take care of the integer overflow.
Return 'ANSWER’ as the final answer.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant space.

Time Complexity: OtherExplanation:

O(N*2^N), where ‘N’ is the length of the given array ‘arr’.

We are generating the binary values from 0 to 2^N - 1 and then iterating through the array. Hence the overall time complexity is O(N*2^N).

Accepted Answer

Optimized

The idea is to pivot each element of the array and then take only those elements which are equal or have a difference = 1 so that the maximum difference in the subsequence becomes 1.

The steps are as follows:

Initialize answer to 0, which denotes the longest length of the Harmonic subsequence.
Iterate from ‘i’ = 0 to ‘N - 1’:
- Initialize ‘COUNT_LENGTH’ with 0 respectively which stores the length of the current subsequence.
- Initialize a boolean flag to false, which will be true if it is possible to make the harmonic subsequence. Otherwise, it is false.
- Iterate from ‘j’ = 0 to ‘N - 1’:
  - If the element at the jth index is the same as the element at the ith index, then increment the count.
  - If the element at the jth index is 1 greater than the element at the ith index, then increment the count and set the flag to true as the maximum difference of the current subsequence is 1.
- If the flag is true, Update the answer to the maximum of ‘ANSWER’ and ‘CURRENT_LENGTH’.
Return ‘ANSWER’ as the final answer.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant space.

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the size of the given array.

We are pivoting each element of the array and then for each pivot, we are iterating through the array which will take O(N) time. Hence, the overall time complexity is O(N^2).

Python (3.5)

'''

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    where 'N' is the size of the given array.

'''





def lengthOfLHS(arr):



    answer = 0



    n = len(arr)



    # Iterating over the array.

    for i in range(n):

        flag = 0



        countLength = 0



        # Iterating over the array.

        for j in range(n):



            # If jth element of the array is same as ith element of the array.

            if (arr[j] == arr[i]):

                countLength += 1



            '''

                If jth element of the array is 1 greater than the ith element of the array

			    then we can call it harmonic subsequence.

            '''

            if (arr[j] == 1 + arr[i]):

                countLength += 1

                flag = 1



        # If it is harmonic subsequence.

        if (flag == 1):

            answer = max(answer, countLength)



    return answer

Java (SE 1.8)

/*
    Time Complexity: O(N^2)
    Space Complexity: O(1)

    where 'N' is the size of the given array.
*/
    
public class Solution {
    public static int lengthOfLHS(int[] arr){
        int answer = 0;

        int n = arr.length;

        // Iterating over the array.
        for (int i = 0; i < n; i++)
        {
            boolean flag = false;
            int countLength = 0;

            // Iterating over the array.
            for (int j = 0; j < n; j++)
            {
                // If jth element of the array is same as ith element of the array.
                if (arr[j] == arr[i])
                {
                    countLength++;
                }
                
                /*
                     If jth element of the array is 1 greater than the ith element of 
                     the array then we can call it harmonic subsequence.
                */
                if (arr[j] == 1 + arr[i])
                {
                    countLength++;
                    flag = true;
                }
            }
            
            // If it is harmonic subsequence.
            if (flag)
            {
                answer = Math.max(answer, countLength);
            }
            
        }

        return answer;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N^2)
    Space Complexity: O(1)

    where 'N' is the size of the given array.
*/

int lengthOfLHS(vector &arr)
{
    int answer = 0;

    int n = arr.size();

    // Iterating over the array.
    for (int i = 0; i < n; i++)
    {
        bool flag = 0;
        int countLength = 0;

        // Iterating over the array.
        for (int j = 0; j < n; j++)
        {
            // If jth element of the array is same as ith element of the array.
            if (arr[j] == arr[i])
            {
                countLength++;
            }
            
            /*
                 If jth element of the array is 1 greater than the ith element of 
                 the array then we can call it harmonic subsequence.
            */
            if (arr[j] == 1 + arr[i])
            {
                countLength++;
                flag = 1;
            }
        }
        
        // If it is harmonic subsequence.
        if (flag == 1)
        {
            answer = max(answer, countLength);
        }
        
    }

    return answer;
}

Accepted Answer

Using HashMap

The idea is to store the occurrences of each element in a HashMap. In each iteration, we will check two things:

If ARR[i] + 1 is present in the HashMap or not. If present, then our current length of the subsequence will be the number of occurrences of ARR[i] + number of occurrences of (ARR[i] + 1).
If ARR[i] - 1 is present in the HashMap or not. If present, then our current length of the subsequence will be a number of occurrences of ARR[i] + number of occurrences of (ARR[i] - 1).

The steps are as follows:

Initialize 'ANSWER' to 0, which denotes the longest length of the Harmonic subsequence.
Define a HashMap ‘FREQUENCY’ which stores the number of occurrences of each element in the ARR.
Iterate from ‘i’ = 0 to ‘N - 1’:
- Increment the count of ARR[i] in the HashMap.
- If ARR[i] + 1 is present in the HashMap, ie. FREQUENCY[ARR[i] + 1] >0, then update the 'ANSWER' to the maximum of 'ANSWER' and (FREQUENCY[ARR[i]] + FREQUENCY[ARR[i] + 1]).
- If ARR[i] - 1 is present in the HashMap, ie. FREQUENCY[ARR[i] - 1] >0, then update the 'ANSWER' to maximum of 'ANSWER' and (FREQUENCY[ARR[i]] + FREQUENCY[ARR[i] - 1]).
Return ‘ANSWER’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the given array.

As the maximum size of the HashMap can grow up to the size of the given array. Hence, the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the given array.

We are iterating over the array and incrementing the count of every element in the HashMap which has amortized time complexity of O(1). Hence, the overall time complexity is O(N).

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where 'N' is the size of the given array.

'''



from collections import defaultdict





def lengthOfLHS(arr):



    answer = 0

    n = len(arr)



    # HashMap to store the count of every element.

    frequency = defaultdict(int)



    # Iterating over the array.

    for i in range(n):



        # Increment the count of arr[i].

        frequency[arr[i]] += 1



        '''

            If arr[i] + 1 is present, it means we can make a harmonic subsequence

            using all the occurences of arr[i] and arr[i] + 1.

        '''

        if (arr[i] + 1 in frequency):

            answer = max(answer, frequency[arr[i]] + frequency[arr[i] + 1])



        '''

            If arr[i] - 1 is present, it means we can make a harmonic subsequence

            using all the occurences of arr[i] and arr[i] - 1.

        '''

        if (arr[i] - 1 in frequency):

            answer = max(answer, frequency[arr[i]] + frequency[arr[i] - 1])



    return answer

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    Where 'N' is the size of the given array.
*/

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static int lengthOfLHS(int[] arr){
        int answer = 0;
        int n = arr.length;
        // HashMap to store the count of every element.
        Map frequency = new HashMap();

        // Iterating over the array.
        for (int i = 0; i < n; i++)
        {
            // Increment the count of arr[i].
            int cnt = (frequency.containsKey(arr[i]))?frequency.get(arr[i]):0;
            frequency.put(arr[i], cnt+1);

            /*
                If arr[i] + 1 is present, it means we can make a harmonic subsequence
                using all the occurences of arr[i] and arr[i] + 1.
            */
            if (frequency.containsKey(arr[i] + 1))
            {
                answer = Math.max(answer, frequency.get(arr[i]) + frequency.get(arr[i] + 1));

            }

            /*
                If arr[i] - 1 is present, it means we can make a harmonic subsequence
                using all the occurences of arr[i] and arr[i] - 1.
            */
            if (frequency.containsKey(arr[i] - 1))
            {
                answer = Math.max(answer, frequency.get(arr[i]) + frequency.get(arr[i] - 1));
            }
        }

        return answer;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    Where 'N' is the size of the given array.
*/

#include

int lengthOfLHS(vector &arr)
{

    int answer = 0;
    int n = arr.size();
    // HashMap to store the count of every element.
    unordered_map frequency;

    // Iterating over the array.
    for (int i = 0; i < n; i++)
    {
        // Increment the count of arr[i].
        frequency[arr[i]]++;

        /*
            If arr[i] + 1 is present, it means we can make a harmonic subsequence
            using all the occurences of arr[i] and arr[i] + 1.
        */
        if (frequency.count(arr[i] + 1) > 0)
        {
            answer = max(answer, frequency[arr[i]] + frequency[arr[i] + 1]);

        }

        /*
            If arr[i] - 1 is present, it means we can make a harmonic subsequence
            using all the occurences of arr[i] and arr[i] - 1.
        */
        if (frequency.count(arr[i] - 1) > 0)
        {
            answer = max(answer, frequency[arr[i]] + frequency[arr[i] - 1]);

        }
    }

    return answer;
}

You are given an array ‘ARR’ of 'N' integers. Your task is to find the longest harmonious subsequence of this array.

A sequence is Harmonious if the difference between the maximum and the minimum of all the elements is exactly 1.

For example

Input Format:

Output Format:

Note:

Constraints:

Top LTIMindtree Java Developer interview questions & answers

Popular interview questions of Java Developer

Top HR questions asked in LTIMindtree Java Developer