07-Longest-Harmonious-Subsequence.md

Longest Harmonious Subsequence

Problem Link

https://leetcode.com/problems/longest-harmonious-subsequence/

---

Pattern

• Hash Table

---

Approach

Count frequencies, then for each number check if num+1 exists; max pair length is answer.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);
        int ans = 0;
        for (int key : map.keySet()) {
            if (map.containsKey(key + 1)) {
                ans = Math.max(ans, map.get(key) + map.get(key+1));
            }
        }
        return ans;
    }
}