Longest Harmonious Subsequence

We can solve this problem using a HashMap (or a dictionary in Python) to count the frequency of each number in the array. Then, for each number in the array, we check if this number + 1 is in our map. If it is, then we have a possible harmonious subsequence with a length equal to the count of the current number + the count of the next number. We keep updating our result with the maximum length of harmonious subsequences we find. If there is no such number that its count + count of the next number is larger than our result, we return our result.

Here is the Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from collections import Counter

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        count = Counter(nums)
        res = 0
        for num in count:
            if num + 1 in count:
                res = max(res, count[num] + count[num + 1])
        return res

In this code, Counter(nums) will count the frequency of each number in nums. Then for each number in our counter, we check if this number + 1 is also in our counter. If it is, it means we have a harmonious subsequence and we update our result with the max length found so far. Finally, we return our result.

Identifying Problem Isomorphism

“Longest Harmonious Subsequence” can be approximately mapped to “Find the Difference”.

In “Longest Harmonious Subsequence”, you are asked to find the longest harmonious subsequence in an array. A harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

In “Find the Difference”, you are given two strings and asked to find the letter that was added to t, which makes it different from s.

While both problems aren’t exactly alike, they share a fundamental trait: they both involve comparing elements in a sequence and finding some difference or relationship among them. In “Longest Harmonious Subsequence”, the relationship is the difference between numbers, while in “Find the Difference”, it’s the extra letter that makes two strings different.

“Find the Difference” is simpler because it requires you to simply find the extra letter in the string, which can be done by comparing the frequency of characters in both strings. “Longest Harmonious Subsequence” requires you to find the longest subsequence that fulfills a certain condition, which is a more complex task.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
	def findLHS(self, nums: List[int]) -> int:
		tmp = Counter(nums)
		keys = tmp.keys()
		max = 0
		for num in keys:
			if num - 1 in keys:
				if tmp[num - 1] + tmp[num] > max:
					max = tmp[num - 1] + tmp[num]
		return max

Let’s break down the explanation:

  1. “Let count be the number of x’s in our array.”

    • This means that we’re keeping track of how many times each number (represented here as ‘x’) appears in the array.

  2. “Suppose our longest subsequence B has min(B) = x and max(B) = x+1.”

    • Here we’re assuming that we have a subsequence (a sequence that is part of our array) where the smallest number is ‘x’ and the largest number is ‘x+1’. This means the numbers in our subsequence are either ‘x’ or ‘x+1’, and their difference is exactly 1, which fits the definition of a harmonious subsequence.

  3. “Evidently, it should use all occurrences of x and x+1 to maximize it’s length, so len(B) = count + count[x+1].”

    • Here, it’s saying that to make the subsequence as long as possible, we should include all instances of ‘x’ and ‘x+1’ in the array. So, the length of this subsequence would be the number of times ‘x’ appears in the array plus the number of times ‘x+1’ appears in the array.

  4. “Additionally, it must use x and x+1 at least once, so count and count[x+1] should both be positive.”

    • Lastly, it’s saying that ‘x’ and ‘x+1’ must each appear at least once in the subsequence. This is because if ‘x’ or ‘x+1’ doesn’t appear in the subsequence, then it’s not possible to have a harmonious subsequence where the minimum is ‘x’ and the maximum is ‘x+1’. So, the count of ‘x’ and ‘x+1’ in the array should both be more than 0.

So, in simpler terms, we are looking at every pair of numbers in the array where one number is exactly 1 more than the other. For each pair, we’re adding up how many times both numbers appear in the array. The largest total we find will be the length of the longest harmonious subsequence.

Problem Classification

This problem is dealing with the concept of Array Manipulation and Subsequence Extraction.

  1. Input: An integer array nums.

  2. Output: The length of its longest harmonious subsequence. A harmonious array is one where the difference between its maximum value and its minimum value is exactly 1.

  3. Subsequence: A subsequence of an 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.

We can further classify this problem as an Optimization Problem. In this problem, we aim to find the maximum length subsequence that satisfies certain conditions (here being harmonious), which is a common theme in optimization problems. We are trying to optimize (maximize, in this case) a certain objective (length of the harmonious subsequence) under specific constraints (difference between max and min elements is exactly 1).

This problem involves exploring all possible subsequences of the given array, and hence could also be seen as involving Combinatorial Search strategies, often solved by techniques like dynamic programming, greedy algorithms, or exhaustive search, depending on the problem’s specific constraints and size.

Q&A

So basically you just have to find a number and then the successor(number +1 ) of that number in the given array and check their frequencies and that will be our answer.(Why?)

Reason: See if you include any smaller number in the array that will change min of array and hence to fulfill the condition, you again need to find the next number of that minimum number and similar applies to changing the maximum of the array , in that case you will need maxnumber-1 for that array .

Yes, exactly. Your understanding is correct.

In a harmonious array, the difference between the maximum and minimum values should be exactly 1. Thus, a harmonious array must consist of two types of elements: one is x (any number from the array), and the other is x+1. The maximum possible length of such array would be the sum of frequencies of x and x+1.

We iterate through each unique number (x) in the array, check if x+1 is present, and then sum the frequency of x and x+1. We keep updating our result with the maximum length found so far. At the end, we return the maximum length. This approach ensures we find the longest harmonious subsequence among all possible subsequences.

Let’s visualize it with an example: nums = [1,3,2,2,5,2,3,7]

  • Frequencies are {1:1, 3:2, 2:3, 5:1, 7:1}
  • We have possible harmonious pairs (1,2), (2,3), (5,6) and (7,8)
  • (1,2): Length is freq[1]+freq[2] = 1+3 = 4
  • (2,3): Length is freq[2]+freq[3] = 3+2 = 5
  • (5,6) and (7,8) pairs do not exist since 6 and 8 are not in the array.
  • Maximum length of harmonious subsequence is 5 which corresponds to the pair (2,3). So the output is 5.

actually you can reformulate the problem in: count the occurrences of every number in the array, then calculate the maximum sum between occs of n, n+1 and n, n-1 for every n in the array.

You’re correct. The problem can indeed be reformulated that way. To solve it, we could follow these steps:

  1. Iterate over the array and record the frequency of each number using a dictionary or a hash map.
  2. Then, for every unique number n in the dictionary, calculate the sum of the frequency of n and the frequency of n+1 as well as the frequency of n and n-1.
  3. Keep track of the maximum sum encountered. This will give us the length of the longest harmonious subsequence, as this sum represents the total count of numbers n and n+1 or n and n-1 that can be found in the array, forming a harmonious subsequence.

Here’s a Python solution that follows these steps:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        count = collections.Counter(nums)
        res = 0
        for n in count:
            if n + 1 in count:
                res = max(res, count[n] + count[n + 1])
            if n - 1 in count:
                res = max(res, count[n] + count[n - 1])
        return res

Note: In this code, we’re using Python’s built-in collections.Counter to create a dictionary that maps each unique number in nums to its frequency. For each unique number n in this dictionary, we then check if n+1 and n-1 are also in the dictionary. If they are, we calculate the sum of the frequencies of n and n+1 and n and n-1, and update our result res with the maximum of these sums.

Isn’t a subsequence supposed to preserve the order of the elements? Here we are just taking a random arrangement of integers

Yes, a subsequence typically does preserve the order of elements from the original sequence. However, this problem doesn’t require that order be maintained for the subsequence. This is because the harmonious property is based solely on the values of the elements, not their order.

A subsequence is just a sequence that can be derived from another sequence by deleting some (or no) elements, without changing the order of the remaining elements. But in this problem, we’re interested in the length of the longest harmonious subsequence, and the length would be the same regardless of the order in which the elements appear.

So, while we’re technically counting combinations of elements that could form such subsequences, it doesn’t affect the solution to this problem. This is because we’re ultimately only interested in the maximum length of such subsequences, not the subsequences themselves. So even though we are not explicitly forming these subsequences, our approach correctly calculates the maximum possible length for such a subsequence.

Language Agnostic Coding Drills

  1. Dissection of the code: The given Python code utilizes various coding concepts, each providing a unique functionality towards achieving the desired solution:

    a) Using a Counter: A Counter is a dict subclass for counting hashable objects. It is a collection where elements are stored as dictionary keys and their counts are stored as dictionary values. Here, it is used to count the occurrence of each integer in the given list.

    b) Accessing dictionary keys: This concept involves accessing the keys of a dictionary. Here, it is used to iterate over all unique integers in the list.

    c) If-else conditional checks: Here, it is used to check if a particular condition holds (if num - 1 exists in the keys).

    d) Updating variables: Updating the values of variables based on certain conditions. Here, the maximum length of a harmonious subsequence found so far is updated.

  2. Difficulty-level categorization of coding concepts:

    a) Using a Counter: Easy. Using a counter is quite straightforward in Python. However, understanding its utility might require a basic understanding of dictionaries in Python.

    b) Accessing dictionary keys: Easy. This is a fundamental concept and involves accessing the keys of a dictionary, which is a basic operation in Python.

    c) If-else conditional checks: Easy. It is a basic programming construct used to control the flow of the program based on certain conditions.

    d) Updating variables: Easy. Updating variables based on conditions is a very common operation in programming and is quite simple to grasp.

  3. Problem-solving approach:

    The problem is solved by counting the occurrence of each number in the given list and then iterating over these unique numbers. For each number, we check if the number minus one exists in our unique numbers list. If it does, then we consider the subsequence made by this number and the number minus one as a potential harmonious subsequence. We then compare its length to the length of the longest harmonious subsequence found so far. This comparison is done by adding the count of the current number and the count of the number minus one (i.e., the length of the potential harmonious subsequence), and comparing it with the maximum length found so far.

    This solution relies on the concept of hash maps or dictionaries (implemented using the Counter class in Python) to efficiently count the occurrence of each number, and then it checks for each number if it can form a harmonious subsequence with the number minus one. The use of a dictionary ensures that both the counting and checking operations are efficient, leading to an overall time complexity of O(n).

Targeted Drills in Python

  1. Python Coding Drills:

a) Using a Counter

1
2
3
4
5

from collections import Counter

numbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
counter = Counter(numbers)
print(counter)

b) Accessing dictionary keys

1
2
3

dictionary = {"apple": 1, "banana": 2, "cherry": 3}
keys = dictionary.keys()
print(keys)

c) If-else conditional checks

1
2
3
4
5
6

number = 10

if number > 5:
    print("Number is greater than 5")
else:
    print("Number is less than or equal to 5")

d) Updating variables

1
2
3
4
5
6
7
8

max_number = -1
numbers = [1, 2, 3, 4, 5]

for number in numbers:
    if number > max_number:
        max_number = number

print(max_number)
  1. Problem-specific coding drills:

This problem does not require any problem-specific coding drills. The concepts listed above and the methods to implement them are enough to solve the problem.

  1. Assembly of drills to solve the problem:

a) Begin by counting the occurrence of each integer in the given list using the Counter class from the collections module.

b) Then, iterate over these unique integers (which are the keys in our counter dictionary).

c) For each integer, check if the integer minus one exists in our unique integers (keys of counter dictionary). If it does, this means we can form a harmonious subsequence with the current number and the number minus one.

d) Calculate the length of the potential harmonious subsequence by adding the count of the current number and the count of the number minus one (which can be accessed from the counter dictionary).

e) Compare this length to the length of the longest harmonious subsequence found so far. If it’s longer, then update the length of the longest harmonious subsequence.

f) Repeat this process for each unique integer in the list. Once all integers have been processed, return the length of the longest harmonious subsequence.

In this way, we use the Counter, dictionary key access, if-else conditional check, and variable updating concepts to solve the problem.