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.
A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.
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
Example 3:
Input: nums = [1,1,1,1]
Output: 0Solution in Python:
Python
from typing import List
from collections import Counter
class Solution:
def findLHS(self, nums: List[int]) -> int:
# Step 1: Count the frequency of each number in the array
count = Counter(nums)
# Step 2: Initialize the maximum length of harmonious subsequence
max_length = 0
# Step 3: Iterate through the unique numbers in the array
for num in count:
# Step 4: Check if the current number and the number + 1 both exist in the array
if num + 1 in count:
# Step 5: Calculate the length of the harmonious subsequence containing num and num + 1
current_length = count[num] + count[num + 1]
# Step 6: Update the maximum length if the current length is greater
max_length = max(max_length, current_length)
# Step 7: Return the maximum length of harmonious subsequence found
return max_lengthExplanation:
- Step 1: Counting the Frequency of Each Number
- We use the
Counterclass from thecollectionsmodule to count the frequency of each number in thenumsarray. This gives us a dictionary-like object where keys are the numbers and values are their counts.
- We use the
- Step 2: Initialize the Maximum Length
- We initialize a variable
max_lengthto store the maximum length of any harmonious subsequence found.
- We initialize a variable
- Step 3: Iterate Through Unique Numbers
- We iterate through each unique number in the
countdictionary.
- We iterate through each unique number in the
- Step 4: Check for Harmonious Subsequence
- For each number, we check if the number plus one (
num + 1) also exists in thecountdictionary. This ensures that the subsequence will have a minimum difference of exactly 1 between its maximum and minimum values.
- For each number, we check if the number plus one (
- Step 5: Calculate Length of Harmonious Subsequence
- If
num + 1exists, we calculate the length of the harmonious subsequence containing bothnumandnum + 1by summing their counts.
- If
- Step 6: Update the Maximum Length
- We update
max_lengthif the current harmonious subsequence length is greater than the previously found maximum length.
- We update
- Step 7: Return the Maximum Length
- Finally, we return the
max_lengthwhich holds the length of the longest harmonious subsequence found.
- Finally, we return the
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var findLHS = function(nums) {
// Step 1: Create a map to count the frequency of each number in the array
let count = new Map();
// Step 2: Populate the frequency map
for (let num of nums) {
count.set(num, (count.get(num) || 0) + 1);
}
// Step 3: Initialize the maximum length of harmonious subsequence
let maxLength = 0;
// Step 4: Iterate through the unique numbers in the array
for (let [num, freq] of count) {
// Step 5: Check if the current number and the number + 1 both exist in the array
if (count.has(num + 1)) {
// Step 6: Calculate the length of the harmonious subsequence containing num and num + 1
let currentLength = freq + count.get(num + 1);
// Step 7: Update the maximum length if the current length is greater
maxLength = Math.max(maxLength, currentLength);
}
}
// Step 8: Return the maximum length of harmonious subsequence found
return maxLength;
};Solution in Java:
Java
import java.util.HashMap;
import java.util.Map;
class Solution {
public int findLHS(int[] nums) {
// Step 1: Create a map to count the frequency of each number in the array
Map<Integer, Integer> count = new HashMap<>();
// Step 2: Populate the frequency map
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
// Step 3: Initialize the maximum length of harmonious subsequence
int maxLength = 0;
// Step 4: Iterate through the unique numbers in the array
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
int num = entry.getKey();
int freq = entry.getValue();
// Step 5: Check if the current number and the number + 1 both exist in the array
if (count.containsKey(num + 1)) {
// Step 6: Calculate the length of the harmonious subsequence containing num and num + 1
int currentLength = freq + count.get(num + 1);
// Step 7: Update the maximum length if the current length is greater
maxLength = Math.max(maxLength, currentLength);
}
}
// Step 8: Return the maximum length of harmonious subsequence found
return maxLength;
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public int FindLHS(int[] nums) {
// Step 1: Create a dictionary to count the frequency of each number in the array
Dictionary<int, int> count = new Dictionary<int, int>();
// Step 2: Populate the frequency dictionary
foreach (int num in nums) {
if (count.ContainsKey(num)) {
count[num]++;
} else {
count[num] = 1;
}
}
// Step 3: Initialize the maximum length of harmonious subsequence
int maxLength = 0;
// Step 4: Iterate through the unique numbers in the dictionary
foreach (var entry in count) {
int num = entry.Key;
int freq = entry.Value;
// Step 5: Check if the current number and the number + 1 both exist in the array
if (count.ContainsKey(num + 1)) {
// Step 6: Calculate the length of the harmonious subsequence containing num and num + 1
int currentLength = freq + count[num + 1];
// Step 7: Update the maximum length if the current length is greater
maxLength = Math.Max(maxLength, currentLength);
}
}
// Step 8: Return the maximum length of harmonious subsequence found
return maxLength;
}
}