We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.
Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.
Input: [1,3,2,2,5,2,3,7] Output: 5 Explanation: The longest harmonious subsequence is [3,2,2,2,3].
Note: The length of the input array will not exceed 20,000.
In the brute force solution, we consider every possible subsequence that can be formed using the elements of the given array. For every subsequence, we find the maximum and minimum values in the subsequence. If the difference between the maximum and the minimum values obtained is 1, it means the current subsequence forms a harmonious subsequence. Thus, we can consider the number of elements in this subsequence to be compared with the length of the last longest harmonious subsequence.\n
In order to obtain all the subseqeuences possible, we make use of binary number representation of decimal numbers. For a binary number of size , a total of different binary numbers can be generated. We generate all these binary numbers from to . For every binary number generated, we consider the subsequence to be comprised of only those elements of which have a 1 at the corresponding position in the current binary number. The following figure shows an example of the way the elements of are considered in the current subsequence.\n
Time complexity : . Number of subsequences generated will be .\n
Space complexity : . Constant space required.\n
In the last approach, we created every possible subsequence, and for every such subsequence, we found out if it satisfies the harmonicity condition. Instead of doing this, we can do as follows. We can consider every element of the given array one by one. For chosen to be the current element, we determine the of all the elements in the array, which satisfy the harmonicity condition with , i.e. the of all such satisfying or . When we reach the end of the array for being the current element, we compare this obtained with the result obtained from the previous traversals and update the result appropriately. When all the elements of the array have been chosen as the element to be chosen as the base for harmonicity check, we get the required length of the longest harmonic subsequence.\n
The following animation illustrates the process:\n
Time complexity : . Two nested loops are there.\n
Space complexity : . Constant space required.\n
Since we are concerned only with the count of elements which are at a difference of 1, we can use sorting to our advantage. If we sort the given array, the related elements will get arranged close to each other. Thus, we can traverse over the sorted array, and find the count of similar elements and elements one larger than the current ones, which occur consecutively(all the similar elements will be lying consecutively now). Initially, this value is stored in variable. Then, if we encounter an element which is just 1 larger than the last elements, we count the occurences of such elements as well. This value is stored in variable.\n
Thus, now for the harmonic subsequence comprised of only these two elements is a subsequence of length . This result is stored in for each subsequence found. When we move forward to considering the next set of similar consecutive elements, we need to update the with the \'s value, since now will act as the count of the elements 1 lesser than the next elements encountered. The value of is always updated to be the larger of previous and the current value.\n
When we are done traversing over the whole array, the value of gives us the required result.\n\n
Time complexity : . Sorting takes time.\n
Space complexity : . space is required by sorting in average case.\n
In this approach, we make use of a hashmap which stores the number of times an element occurs in the array along with the element\'s value in the form , where refers to an element in the array and refers to the number of times this occurs in the array. We traverse over the array and fill this once.\n
After this, we traverse over the keys of the created. For every key of the considered, say , we find out if the map contains the . Such an element is found, since only such elements can be counted for the harmonic subsequence if is considered as one of the element of the harmonic subsequence. We need not care about , because if is present in the harmonic subsequence, at one time either or only could be included in the harmonic subsequence. The case of being in the harmonic subsequence will automatically be considered, when is encountered as the current key.\n
Now, whenver we find that exists in the keys of , we determine the count of the current harmonic subsequence as , where refers to the value corresponding to the key in , which reprents the number of times occurs in the array .\n
Look at the animation below for a pictorial view of the process:\n
Time complexity : . One loop is required to fill and one for traversing the .\n
Space complexity : . In worst case map size grows upto size .\n
Instead of filling the first and then traversing over the to determine the lengths of the harmonic subsequences encountered, we can traverse over the array, and while doing the traversals, we can determine the lengths of the harmonic subsequences possible till the current index of the array.\n
The method of finding the length of harmonic subsequence remains the same as the last approach. But, this time, we need to consider the existence of both and exclusively and determine the counts corresponding to both the cases. This is needed now because it could be possible that has already been added to the and later on is encountered. In this case, if we consider the presence of only, we\'ll go in the wrong direction.\n
Thus, we consider the s corresponding to both the cases separately for every and determine the maximum out of them. \nThus, now the same task can be done only in a single traveral of the array.\n
See the animation below for understanding the process:\n
Time complexity : . Only one loop is there.\n
Space complexity : . size grows upto size .\n
Analysis written by: @vinod23\n