Longest Harmonious Subsequence - Leetcode Solution

Problem statement: We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1. Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences. A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example: Input: nums = [1,3,2,2,5,2,3,7] Output: 5 Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Solution: To find the longest harmonious subsequence, we need to first count the frequency of each number in the given array. We can use a hash map to store the frequency of each number. Then we can iterate over the keys of the map and for each key check if its adjacent numbers (the number itself + 1 and the number itself - 1) exists in the map. If they exist, then we can calculate the length of the subsequence by adding the frequency of both numbers. We then update the maximum length obtained so far.

Pseudo-code: freq_map = {} for num in nums: freq_map[num] = freq_map.get(num, 0) + 1 max_length = 0 for key in freq_map: if key + 1 in freq_map: max_length = max(max_length, freq_map[key] + freq_map[key + 1]) return max_length

Time Complexity: The time complexity of the above algorithm is O(n)

• n = length of the nums array

Space Complexity: The space complexity of the algorithm is O(n)

• n = length of the nums array

1