# Longest Harmonious Subsequence
**Difficulty:** EASY
[External](https://leetcode.com/problems/longest-harmonious-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/longest-harmonious-subsequence
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [LiveRamp](https://scaleengineer.com/companies/liveramp), [ZS Associates](https://scaleengineer.com/companies/zs-associates)
---
## Problem
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.

**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`

# Approaches
## Brute Force Iteration
This approach iterates through each unique number in the array. For each number `x`, it checks if `x+1` also exists. If it does, it then re-iterates through the entire original array to count the occurrences of `x` and `x+1` to find the length of the harmonious subsequence they form. This process is repeated for every unique number, and the maximum length found is the result.
**Time:** O(U * N), where N is the number of elements in `nums` and U is the number of unique elements. In the worst-case scenario where all elements are unique, U = N, leading to a time complexity of O(N^2). · **Space:** O(U), where U is the number of unique elements in `nums`. In the worst case, all elements are unique, so the space complexity is O(N).
**Pros:** Simple to understand and implement.; Does not require complex data structures other than a set.
**Cons:** Highly inefficient due to nested iteration. The time complexity is quadratic in the worst case.; Redundant counting work. For a pair `(x, x+1)`, the counts are recalculated by iterating over the entire array.
### Explanation
The brute-force method systematically checks every possible base number for a harmonious subsequence. First, we identify all unique numbers present in the input array `nums` by storing them in a `HashSet`. Then, for each unique number `currentNum`, we verify if its counterpart, `currentNum + 1`, is also present in the set. If both exist, they form a potential harmonious subsequence. To calculate its length, we perform a full scan of the original `nums` array, counting every occurrence of `currentNum` and `currentNum + 1`. This sum gives the length of the subsequence formed by this pair. We maintain a variable, `maxLength`, to keep track of the largest length found across all such pairs. While straightforward, this method is computationally expensive because of the repeated scans of the input array.

```java
class Solution {
    public int findLHS(int[] nums) {
        int maxLength = 0;
        java.util.Set<Integer> uniqueNums = new java.util.HashSet<>();
        for (int num : nums) {
            uniqueNums.add(num);
        }

        for (int num : uniqueNums) {
            if (uniqueNums.contains(num + 1)) {
                int currentLength = 0;
                for (int val : nums) {
                    if (val == num || val == num + 1) {
                        currentLength++;
                    }
                }
                maxLength = Math.max(maxLength, currentLength);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Create a `Set` of unique numbers from the input array `nums` to avoid redundant checks.
- Initialize a variable `maxLength` to 0.
- Iterate through each unique number `num` in the set.
- For each `num`, check if `num + 1` also exists in the set.
- If it does, this pair can form a harmonious subsequence. We then need to find its length.
- To find the length, iterate through the original `nums` array and count all elements that are equal to `num` or `num + 1`.
- Update `maxLength` with the maximum length found so far.
- After checking all unique numbers, return `maxLength`.

## Sorting and Sliding Window
This approach improves upon the brute-force method by first sorting the array. Once the array is sorted, all identical elements are grouped together, and potential harmonious pairs (`x` and `x+1`) are located near each other. We can then use a sliding window (or two-pointer) technique to efficiently find the longest subarray where the difference between the maximum and minimum element is exactly 1. This avoids the repeated scanning of the entire array.
**Time:** O(N log N), which is dominated by the initial sorting step. The subsequent two-pointer scan of the array takes O(N) time. · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm used. For instance, `Arrays.sort` in Java for primitives uses a variant of quicksort which has an average space complexity of O(log N) for the recursion stack.
**Pros:** Significantly more efficient than the brute-force approach.; The sliding window logic is efficient, scanning the array only once after sorting.
**Cons:** The sorting step has a time complexity of O(N log N), which is not as efficient as the linear time solution.; The sorting modifies the original array's order, which might not be desirable in some contexts (though a copy can be made).
### Explanation
By sorting the array `nums`, we can efficiently find harmonious subsequences. After sorting, we can use a sliding window approach with two pointers, `left` and `right`. The `right` pointer expands the window by moving from left to right through the array. For each position of `right`, we check the difference `nums[right] - nums[left]`. If this difference is greater than 1, it means the window is too wide to be harmonious, so we shrink it by incrementing the `left` pointer. If the difference is exactly 1, we have found a valid harmonious subsequence. Its length is `right - left + 1`, and we update our `maxLength` if this is the longest one we've seen. If the difference is 0, all elements in the window are the same, which is not a harmonious subsequence, but we continue expanding the window as it might become part of one.

```java
import java.util.Arrays;

class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int maxLength = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            while (nums[right] - nums[left] > 1) {
                left++;
            }
            if (nums[right] - nums[left] == 1) {
                maxLength = Math.max(maxLength, right - left + 1);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- First, sort the input array `nums` in non-decreasing order.
- Initialize two pointers, `left = 0`, and a variable `maxLength = 0`.
- Iterate through the array with a `right` pointer from `0` to `nums.length - 1`.
- Inside the loop, advance the `left` pointer while the condition `nums[right] - nums[left] > 1` is true. This shrinks the window from the left to ensure the difference between the max and min in the window is at most 1.
- After adjusting `left`, check if `nums[right] - nums[left] == 1`. If it is, the current window `[left, right]` represents a harmonious subsequence.
- Calculate its length as `right - left + 1` and update `maxLength = max(maxLength, right - left + 1)`.
- After the loop finishes, return `maxLength`.

## Hash Map for Frequency Counting
This is the most optimal approach. It uses a hash map to efficiently count the frequencies of all numbers in the input array in a single pass. After building this frequency map, it iterates through the unique numbers (the map's keys). For each number `x`, it checks if `x+1` also exists in the map. If it does, the length of the harmonious subsequence is simply the sum of their frequencies, `count(x) + count(x+1)`. The maximum of these sums is the answer.
**Time:** O(N). The first pass to build the frequency map takes O(N). The second pass iterates through the unique keys of the map, which is O(U) where U <= N. Thus, the overall time complexity is O(N). · **Space:** O(U), where U is the number of unique elements in `nums`. In the worst case, all elements are unique, so the space complexity is O(N).
**Pros:** Optimal time complexity of O(N).; Conceptually clean, directly addressing the problem by counting frequencies.; Only requires two passes over the data (one on the array, one on the unique keys).
**Cons:** Requires extra space to store the frequency map, which can be O(N) in the worst case where all elements are unique.
### Explanation
The core idea is that a harmonious subsequence is composed of only two distinct numbers, `x` and `x+1`. Therefore, its length is the total number of times `x` and `x+1` appear in the original array. A hash map is the perfect data structure to solve this efficiently. 

First, we iterate through the `nums` array and populate a hash map, where each key is a number from the array and its corresponding value is its frequency. This takes linear time.

Next, we iterate through the keys of the newly created frequency map. For each key `num`, we check if `num + 1` also exists as a key in the map. If it does, we have found a valid pair for a harmonious subsequence. We calculate the length by summing their frequencies: `freqMap.get(num) + freqMap.get(num + 1)`. We compare this length with our current `maxLength` and update it if the new length is greater. This second pass over the unique keys ensures we find the maximum possible length.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        int maxLength = 0;
        for (int key : freqMap.keySet()) {
            if (freqMap.containsKey(key + 1)) {
                maxLength = Math.max(maxLength, freqMap.get(key) + freqMap.get(key + 1));
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Create a `HashMap` to store the frequency of each number.
- Iterate through the input array `nums` once. For each number, update its count in the hash map.
- Initialize a variable `maxLength` to 0.
- Iterate through the keys (the unique numbers) of the hash map.
- For each key `num`, check if the map also contains the key `num + 1`.
- If `num + 1` exists in the map, it means we have a pair that forms a harmonious subsequence.
- The length of this subsequence is the sum of the frequencies: `map.get(num) + map.get(num + 1)`.
- Update `maxLength` with the maximum sum found.
- After iterating through all keys, return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int findLHS(int[] nums) {
    Map<Integer, Integer> counter = new HashMap<>();
    for (int num : nums) {
      counter.put(num, counter.getOrDefault(num, 0) + 1);
    }
    int ans = 0;
    for (int num : nums) {
      if (counter.containsKey(num + 1)) {
        ans = Math.max(ans, counter.get(num) + counter.get(num + 1));
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findLHS(vector<int> &nums) {
    unordered_map<int, int> counter;
    for (int num : nums) {
      ++counter[num];
    }
    int ans = 0;
    for (int num : nums) {
      if (counter.count(num + 1)) {
        ans = max(ans, counter[num] + counter[num + 1]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findLHS(self, nums: List[int]) -> int: counter = Counter(nums) ans = 0 for num in nums: if num + 1 in counter: ans = max(ans, counter[num] + counter[num + 1]) return ans

```