Longest Harmonious Subsequence

Problem: A harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1. Given an integer array, return the length of its longest harmonious subsequence among all its possible subsequences.

Example:

Input: nums = [2,3,2,2,8,2,3,7]
Output: 6
Explanation: The longest harmonious subsequence is [2,3,2,2,2,3].

Approach: We can use sorting here but that will take O(nlogn) time. We can use hashing to solve this problem efficiently. Basically we can have a frequency map in which key is the element of the input array and value is number of times the element occurs in the array. Once we fill this map, we can iterate over the keys of this map and see if key + 1 exist in the map or not. If yes, then we can update our result as:

result = Max(result, map[key] + map[key + 1])

That's all!

Implementation in C#:

        public int FindLHS(int[] nums)

        {

            Dictionary<int, int> countMap = new Dictionary<int, int>();

            foreach(int num in nums)

            {

                if (!countMap.ContainsKey(num))

                {

                    countMap.Add(num, 0);

                }

                ++countMap[num];

            }

            int lhs = 0;

            foreach(int key in countMap.Keys)

            {

                if (countMap.ContainsKey(key + 1))

                {

                    lhs = Math.Max(lhs, countMap[key] + countMap[key + 1]);

                }

            }

            return lhs;

        }

Complexity: O(n)