LeetCode 0594. Longest Harmonious Subsequence Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

Description

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

Solutions

Solution 1: Hash Table

We can use a hash table cnt to record the occurrence count of each element in the array nums. Then, we iterate through each key-value pair (x, c) in the hash table. If the key x + 1 exists in the hash table, then the sum of occurrences of elements x and x + 1, c + cnt[x + 1], forms a harmonious subsequence. We just need to find the maximum length among all harmonious subsequences.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.

PythonJavaC++GoTypeScriptRust

class Solution: def findLHS(self, nums: List[int]) -> int: cnt = Counter(nums) return max((c + cnt[x + 1] for x, c in cnt.items() if cnt[x + 1]), default=0)(code-box)

class Solution { public int findLHS(int[] nums) { Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) { cnt.merge(x, 1, Integer::sum); } int ans = 0; for (var e : cnt.entrySet()) { int x = e.getKey(), c = e.getValue(); if (cnt.containsKey(x + 1)) { ans = Math.max(ans, c + cnt.get(x + 1)); } } return ans; } }(code-box)

class Solution { public: int findLHS(vector<int>& nums) { unordered_map<int, int> cnt; for (int x : nums) { ++cnt[x]; } int ans = 0; for (auto& [x, c] : cnt) { if (cnt.contains(x + 1)) { ans = max(ans, c + cnt[x + 1]); } } return ans; } };(code-box)

func findLHS(nums []int) (ans int) { cnt := map[int]int{} for _, x := range nums { cnt[x]++ } for x, c := range cnt { if c1, ok := cnt[x+1]; ok { ans = max(ans, c+c1) } } return }(code-box)

function findLHS(nums: number[]): number { const cnt: Record<number, number> = {}; for (const x of nums) { cnt[x] = (cnt[x] || 0) + 1; } let ans = 0; for (const [x, c] of Object.entries(cnt)) { const y = +x + 1; if (cnt[y]) { ans = Math.max(ans, c + cnt[y]); } } return ans; }(code-box)

use std::collections::HashMap; impl Solution { pub fn find_lhs(nums: Vec<i32>) -> i32 { let mut cnt = HashMap::new(); for &x in &nums { *cnt.entry(x).or_insert(0) += 1; } let mut ans = 0; for (&x, &c) in &cnt { if let Some(&y) = cnt.get(&(x + 1)) { ans = ans.max(c + y); } } ans } }(code-box)