Longest Harmonious Subsequence

An harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1. The goal is to find 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.

2 solutions

Solution 1:

1) Counts the number of appearances of each value using a Counter

2) Iterate over the Counter sorted by key, if two successive values have a difference of 1 they are hence a harmonious subsequence.

3) Return the harmonious subsequence with greater length (update the value directly in the loop)

# Solution 1
def findLHS(nums: List[int]) -> int:
    max_sequence, count = 0, Counter(nums)
    k_prec, v_prec = -float("inf"), 0
    for k, v in sorted(count.items()):
        if k - k_prec == 1:
            max_sequence = max(max_sequence, v + v_prec)
        k_prec, v_prec = k, v
    return(max_sequence)

Solution 2:

1) Sort the array

2) Create sequence of equal values (store the size of the sequence)

3) For new values not in the sequence, two cases are possible:

a) if the difference with last sequence values is less than 1: start a new sequence and store the length of the precedent one in another variable

b) if the difference with last sequence values is greater than 1: start a new sequence and set the variable "length of precedent sequence" to 0

4) If the variable "precedent sequence length" is greater than 0 that means that the 2 sequences have a difference of 1 and then we compare the length of this new sequence to the greatest sequence length so far

# Solution 2
def findLHS(self, nums: List[int]) -> int:
        nums.sort()
        longest_harmonic_sequence = 0
        
        current_sequence_equal_values = 1   # Length of current sequence of equal values
        previous_sequence_equal_values = 0  # Length of previous sequence of equal value with diff <= 1
        
        for i in range(1, len(nums)):
            # continue current sequence
            if nums[i] - nums[i-1] == 0:
                current_sequence_equal_values += 1
            
            # new sequence with diff of values = 1
            elif nums[i] - nums[i-1] == 1:
                previous_sequence_equal_values = current_sequence_equal_values # we store the length of precedent sequence
                current_sequence_equal_values = 1
            
            # new sequence with diff of values greater than 1
            else:
                previous_sequence_equal_values = 0 # reset precedent sequence length
                current_sequence_equal_values = 1
                
            # Update only if previous_sequence_equal_values > 0
            if previous_sequence_equal_values > 0: 
                longest_harmonic_sequence = max(longest_harmonic_sequence, previous_sequence_equal_values+current_sequence_equal_values)
                
        return longest_harmonic_sequence