Problem Statement

We have to write a function that takes an integer array as an input and returns the length of its longest " Harmonic" subsequence. A Harmonic subsequence is any subsequence where the difference between the maximum and minimum values is exactly 1.

Example

If our input array is: [1,3,2,2,5,2,3,7], the longest Harmonic subsequence is [3,2,2,2,3], so our function should return 5.

Approach

To solve this problem, we can use the following approach:

1. Initialize an unordered_map to hold the frequency of each integer in the array.
2. For each integer in the array, increment its count in the map.
3. Loop through each entry in the map. For each entry, check if there exists another entry with integer value equal to current integer + 1. If it exists, it means there is a harmonic sequence and you calculate its length and update the maximum length if this length is more than the maximum length calculated so far.
4. Return the maximum length.

Example

Input: nums = [1,2,2,5,2,3,7]

• Initialize count as an empty map.
• For each number in nums, increment its count in the map. After this step, count will be {1:1, 2:3, 3:1, 5:1, 7:1}.
• Loop through each entry in the map.
  • For first entry [1:1], we check if there is an entry with key 1+1=2 in the map. Yes, there is. So we calculate the length of this harmonic sequence as 1+3=4 and update our answer to be maximum of 0 and 4. So, answer becomes 4.
  • Likewise, for [2:3], [2, 3] makes a harmonic sequence. Length is: 4. It does not change our answer.
  • Likewise, for [3:1], [3, 7] does not make a harmonic sequence as the difference is not 1.
  • Likewise, we check this for all entries in the map.
• Finally, the value of answer is 4. So, we return 4.

Python Solution

1
2python
3from collections import defaultdict
4
5class Solution:
6    def findLHS(self, nums):
7        ans = 0
8        count = defaultdict(int)
9
10        for num in nums:
11            count[num] += 1
12
13        for num, freq in count.items():
14            if num+1 in count:
15                ans = max(ans, freq + count[num+1])
16
17        return ans     

Java Solution

1
2java
3import java.util.HashMap;
4import java.util.Map;
5
6class Solution {
7	public int findLHS(int[] nums) {
8		int ans = 0;
9		Map<Integer, Integer> count = new HashMap<>();
10
11		for (int num : nums) {
12			count.put(num, count.getOrDefault(num, 0) + 1);
13		}
14
15		for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
16			if (count.containsKey(entry.getKey() + 1)) {
17				ans = Math.max(ans, entry.getValue() + count.get(entry.getKey() + 1));
18			}
19		}
20
21		return ans;
22	}
23}

JavaScript Solution

1
2javascript
3class Solution {
4	findLHS(nums) {
5		let ans = 0;
6		const count = new Map();
7
8		for (let num of nums) {
9			count.set(num, (count.get(num) || 0) + 1);
10		}
11
12		for (let [num, freq] of count.entries()) {
13			if (count.has(num + 1)) {
14				ans = Math.max(ans, freq + count.get(num + 1));
15			}
16		}
17
18		return ans;
19	}
20}

C++ Solution

1
2cpp
3#include <unordered_map>
4using namespace std;
5
6class Solution {
7public:
8	int findLHS(vector<int>& nums) {
9		int ans = 0;
10		unordered_map<int, int> count;
11
12		for (int num : nums) {
13			++count[num];
14		}
15
16		for (const auto& entry : count) {
17			if (count.count(entry.first + 1)) {
18				ans = max(ans, entry.second + count[entry.first + 1]);
19			}
20		}
21
22		return ans;
23	}
24};

C# Solution

1
2csharp
3using System;
4using System.Collections.Generic;
5
6class Solution {
7    public int FindLHS(int[] nums) {
8        int ans = 0;
9        Dictionary<int, int> count = new Dictionary<int, int>();
10
11        foreach (int num in nums) {
12            if (count.ContainsKey(num)) {
13                count[num]++;
14            }
15            else {
16                count[num] = 1;
17            }
18        }
19
20        foreach (KeyValuePair<int, int> entry in count) {
21            if (count.ContainsKey(entry.Key + 1)) {
22                ans = Math.Max(ans, entry.Value + count[entry.Key + 1]);
23            }
24        }
25
26        return ans;
27    }
28}

This code can be run and tested using an IDE for the respective languages. For instance, for Python one can use PyCharm or Jupyter notebook and for JavaScript, one may use NodeJS.

In all these solutions, we are creating a map where keys are the distinct numbers from the input array and the corresponding value is the count of that number in the array. This map is then used to check for the occurrence of a harmonic sequence (pair of numbers with a difference of 1) in the array and if found, the sum of their counts becomes a possible answer. The maximum of such sums from all the harmonic sequences in the array is the length of the longest harmonic subsequence.

This approach involves just two iterations over the array - one to build a map and the second to check for harmonic sequences - hence it is quite efficient with a time complexity of O(n), where n is the length of the input array.

Conclusion

In this article, we have learned how to find the longest harmonic subsequence in an array. We showed a step by step approach for the problem and provided implementations in Python, Java, JavaScript, C++ and C#.