
Problem Statement
In the task, a "harmonious array" is characterized specifically as one where the maximum and minimum values have a precise difference of 1
. From a given integer array nums
, the challenge is to determine the length of the longest harmonious subsequence that can be derived from possible subsequences within the array. A subsequence is a sequence derived from another sequence where elements are picked without changing their original order, but not necessarily consecutively. The solution must efficiently dig through permutations to spot this highest-scoring harmonious subsequence.
Examples
Example 1
Input:
nums = [1,3,2,2,5,2,3,7]
Output:
5
Explanation:
The longest harmonious subsequence is `[3,2,2,2,3]`.
Example 2
Input:
nums = [1,2,3,4]
Output:
2
Explanation:
The longest harmonious subsequences are `[1,2]`, `[2,3]`, and `[3,4]`, all of which have a length of 2.
Example 3
Input:
nums = [1,1,1,1]
Output:
0
Explanation:
No harmonic subsequence exists.
Constraints
1 <= nums.length <= 2 * 104
-109 <= nums[i] <= 109
Approach and Intuition
The primary intuition to solve this problem lies in identifying and counting elements that form potential pairs (difference of 1) and then determining the most numerous occurrence of such pairs in the given list. The steps mentioned below outline a conceptual approach:
- First, compute the frequency of each number in the array using a hashmap or a dictionary.
- After building the frequency dictionary, the next step is to iterate through all unique numbers seen.
- For each number, check if the number
+1
exists in the dictionary. - If both the number and the number +1 are in the dictionary, calculate the combined length of these numbers from their frequencies.
- Track the maximum combined length during the iteration.
- This maximum value depicts the length of the longest harmonious subsequence.
Let's break down the thought process through the examples provided:
- Example 1: Looking at the array
[1,3,2,2,5,2,3,7]
,2
and3
appear multiple times and are consecutive integers. Therefore, the longest subsequence combining these would be[3,2,2,2,3]
, having the length of5
. - Example 2: In the array
[1,2,3,4]
, possible consecutive integer pairs are[1,2]
,[2,3]
, and[3,4]
, each of length2
. No pair exceeds the length of 2, hence the answer is2
. - Example 3: The array
[1,1,1,1]
contains no harmonious subsequences as it does not have two different numbers that are consecutive integers. Hence, the result is0
.
Following this approach allows for a structured way to determine the optimal solution within the constraints stipulated, ensuring efficiency and clarity in the process.
Solutions
- Java
public class Solution {
public int longestHarmoniousSubsequence(int[] elements) {
HashMap<Integer, Integer> frequencyMap = new HashMap<>();
int longestLength = 0;
for (int value : elements) {
frequencyMap.put(value, frequencyMap.getOrDefault(value, 0) + 1);
if (frequencyMap.containsKey(value + 1))
longestLength = Math.max(longestLength, frequencyMap.get(value) + frequencyMap.get(value + 1));
if (frequencyMap.containsKey(value - 1))
longestLength = Math.max(longestLength, frequencyMap.get(value) + frequencyMap.get(value - 1));
}
return longestLength;
}
}
The solution involves finding the longest harmonious subsequence in an array of integers where the difference between the maximum and minimum elements in the subsequence is exactly 1. The code implementation is in Java.
Review the following key points used in the solution:
- A
HashMap
namedfrequencyMap
stores the frequency of each element in the array. - The
longestLength
variable maintains the length of the longest harmonious subsequence encountered during the iteration. - The solution iterates over each element in the provided array:
- It updates the frequency of the current element in
frequencyMap
. - If the next consecutive element (
value + 1
) exists in the map, calculate the potential subsequence length including the current and consecutive element, updatinglongestLength
if this subsequence is longer. - Similarly, if the previous element (
value - 1
) exists, check for a subsequence that includes the current element and its predecessor, and updatelongestLength
accordingly.
- It updates the frequency of the current element in
- The method finally returns
longestLength
, which represents the length of the longest harmonious subsequence found.
To effectively implement this solution, ensure you handle edge cases such as empty arrays or arrays where no harmonious subsequence exists, although such scenarios are not shown in the initial code excerpt. The use of a hash map ensures that the frequency count and subsequence length checks are efficient, primarily operating in average O(1) time complexity due to the hash operations.
No comments yet.