algoadvance

Problem Statement

The problem requires us to find the length of the longest harmonious subsequence in an array of integers. A harmonious subsequence is defined as subsequence where the difference between its maximum and minimum values is exactly 1.

Clarifying Questions

1. Can the input array contain negative numbers?
   • Yes, it can contain any integer values.
2. Can the input array be empty?
   • Yes, the input array can be empty. In this case, the output should be 0.
3. Is the order of the subsequence elements important?
   • No, the order of the subsequence elements is not important; it is only necessary for the elements to be a part of the original array.

Strategy

To solve the problem, we can use the following approach:

1. Use a dictionary to count the occurrences of each element in the array.
2. Iterate through the dictionary and for each key, check if the dictionary contains key + 1.
3. If key + 1 exists, compute the sum of the counts of key and key + 1.
4. Track the maximum sum found across all pairs of key and key + 1.

Code

Here is the Python code that implements this strategy:

def findLHS(nums):
    if not nums:
        return 0
    
    count = {}
    for num in nums:
        count[num] = count.get(num, 0) + 1
        
    max_length = 0
    for num in count:
        if num + 1 in count:
            max_length = max(max_length, count[num] + count[num + 1])
    
    return max_length

Time Complexity

• Time Complexity: O(N), where N is the number of elements in the input array. This is because we traverse the list once to build the frequency dictionary and again to check the harmonious subsequences.
• Space Complexity: O(N), where N is the number of unique elements in the input array. This is because we store the frequency of each unique element in a dictionary.

Example

Let’s consider an example to understand the code:

nums = [1, 3, 2, 2, 5, 2, 3, 7]
print(findLHS(nums)) # Output: 5

Here’s the walkthrough:

1. Count dictionary: {1: 1, 3: 2, 2: 3, 5: 1, 7: 1}
2. Check pairs:
   • (1, 2): Length = 1 + 3 = 4
   • (2, 3): Length = 3 + 2 = 5
   • (3, 4): Not applicable, 4 is not in the dictionary
   • (5, 6): Not applicable, 6 is not in the dictionary
3. Maximum length found is 5. Hence, the output is 5.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?