Jobs

Interviews

Discussions

Longest Harmonious Subsequence

Easy

Asked by:

More companies

44 views

Topics:

ArraysDynamic Programming

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 * 10⁴
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Longest Harmonious Subsequence

Easy

Asked by:

44 views

Topics:

ArraysDynamic Programming

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 * 10⁴
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the `nums` array? Can I expect negative numbers, zeros, or very large positive numbers?
Can the input array `nums` be empty or null?
If no harmonious subsequence exists, what value should I return?
Are duplicate values in the `nums` array significant, and should they be considered when determining the length of the longest harmonious subsequence?
Could you define more formally what constitutes a subsequence in this context? Specifically, does order matter and must elements be contiguous?

Brute Force Solution

Approach

The brute force method for finding the longest harmonious subsequence is all about trying every possible combination. We'll examine each possible group of numbers within the input and see if it meets the harmonious criteria. Then, we'll keep track of the longest one we find that fits the rules.

Here's how the algorithm would work step-by-step:

Consider every possible subsequence. A subsequence is formed by picking some numbers from the original group, in their original order.
For each subsequence you pick, check if it's 'harmonious'. This means checking if the biggest and smallest numbers in that subsequence are exactly one apart.
If the subsequence is harmonious, find how many numbers are in it.
Keep track of the biggest size you have found so far.
After checking every possible subsequence, the biggest size you tracked is your answer.

Code Implementation

def longest_harmonious_subsequence_brute_force(numbers):
    max_length_harmonious_subsequence = 0

    # Iterate through all possible subsequences
    for i in range(1 << len(numbers)):
        subsequence = []
        for j in range(len(numbers)):
            # Construct the subsequence
            if (i >> j) & 1:
                subsequence.append(numbers[j])

        # Skip empty subsequences
        if not subsequence:
            continue

        # Check if subsequence is harmonious
        min_value_subsequence = min(subsequence)
        max_value_subsequence = max(subsequence)

        # Harmonious if difference between max and min is 1
        if max_value_subsequence - min_value_subsequence == 1:
            current_subsequence_length = len(subsequence)

            # Keep track of the maximum length
            if current_subsequence_length > max_length_harmonious_subsequence:
                max_length_harmonious_subsequence = current_subsequence_length

    return max_length_harmonious_subsequence

Big(O) Analysis

Time Complexity

O(2^n * n) – The brute force approach iterates through all possible subsequences of the input array. Generating all subsequences of an array of size n takes O(2^n) time because each element can either be present or absent in a subsequence. For each subsequence, we iterate through its elements to find the maximum and minimum values, which takes O(n) time in the worst case. Therefore, the overall time complexity is O(2^n * n).

Space Complexity

O(1) – The brute force approach, as described, only involves iterating through subsequences and checking their properties. It does not use any auxiliary data structures like lists, hash maps, or recursion. Therefore, the space complexity is constant, independent of the input size N (the number of elements in the input sequence). Essentially, only a few variables are used to store the current subsequence's size and the maximum harmonious subsequence size found so far, contributing to O(1) auxiliary space.

Optimal Solution

Approach

The key to efficiently finding the longest harmonious subsequence is to focus on counting the frequency of each number, not comparing every pair. We can significantly reduce the work needed by cleverly organizing how we assess harmonious possibilities. By only counting numbers and their neighbors, we determine the longest sequence.

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the list.
Then, go through the numbers that you've counted and check if the number one greater than it also appears in the list.
If the number one greater exists, add the count of the number and the count of the number one greater.
Keep track of the largest sum you find. The largest sum is the length of the longest harmonious subsequence.
The basic idea is: if you have 5 occurrences of '3' and 3 occurrences of '4', the harmonious subsequence built from those two numbers is of length 8.

Code Implementation

def find_longest_harmonious_subsequence(number_list):
    number_counts = {}

    for number in number_list:
        number_counts[number] = number_counts.get(number, 0) + 1

    longest_harmonious_sequence = 0

    # Iterate through each unique number to find harmonious pairs.
    for number in number_counts:

        # Check if the number + 1 also exists in the list.
        if (number + 1) in number_counts:

            # Calculating the length of the harmonious subsequence.
            harmonious_length = number_counts[number] + number_counts[number + 1]

            # Keep track of the largest harmonious subsequence length.
            longest_harmonious_sequence = max(longest_harmonious_sequence, harmonious_length)

    return longest_harmonious_sequence

Big(O) Analysis

Time Complexity

O(n) – The dominant operation is counting the frequency of each number in the input list of size n. This involves iterating through the list once. Subsequently, we iterate through the unique numbers (at most n) in the frequency map to check for the existence of their neighbors and calculate subsequence lengths. This second loop also has a cost proportional to n in the worst case. Therefore, the overall time complexity is O(n) for counting frequencies plus O(n) for checking neighbors, which simplifies to O(n).

Space Complexity

O(N) – The algorithm uses a hash map (or dictionary) to count the frequency of each number in the input list. In the worst case, all N numbers in the input list are unique, requiring the hash map to store N key-value pairs. Therefore, the auxiliary space used by the hash map scales linearly with the size of the input list. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 since there is no subsequence in an empty array.
Input array with a single element	Return 0 because a harmonious subsequence needs at least two elements with a difference of 1.
Input array contains only identical numbers	Return 0 since the difference between the maximum and minimum of such a subsequence is 0, not 1.
Input array with extremely large positive or negative numbers	The solution should correctly handle large numbers if implemented properly with integer types that have sufficient range (e.g., long in Java, int64 in Go, etc.) and avoid overflow.
Input array contains duplicates of numbers which are 1 apart.	The frequency map will accurately reflect the counts of each number, ensuring the correct length is calculated when checking for harmonious subsequences.
No harmonious subsequence exists in the input array	The solution should correctly identify that no harmonious subsequence is present and return 0.
Array with a large number of elements, potentially causing memory issues if not handled efficiently.	Using a hash map to store element counts ensures that the solution has a time complexity of O(n) and a space complexity of O(n), avoiding memory issues for reasonable input sizes.
Input array contains both positive and negative integers, as well as zero	The difference calculations and comparison will still operate correctly, as long as no integer overflow happens.

Empty input array

How to Handle:

Return 0 since there is no subsequence in an empty array.

Input array with a single element

How to Handle:

Return 0 because a harmonious subsequence needs at least two elements with a difference of 1.

Input array contains only identical numbers

How to Handle:

Return 0 since the difference between the maximum and minimum of such a subsequence is 0, not 1.

Input array with extremely large positive or negative numbers

How to Handle:

The solution should correctly handle large numbers if implemented properly with integer types that have sufficient range (e.g., long in Java, int64 in Go, etc.) and avoid overflow.

Input array contains duplicates of numbers which are 1 apart.

How to Handle:

The frequency map will accurately reflect the counts of each number, ensuring the correct length is calculated when checking for harmonious subsequences.

No harmonious subsequence exists in the input array

How to Handle:

The solution should correctly identify that no harmonious subsequence is present and return 0.

Array with a large number of elements, potentially causing memory issues if not handled efficiently.

How to Handle:

Using a hash map to store element counts ensures that the solution has a time complexity of O(n) and a space complexity of O(n), avoiding memory issues for reasonable input sizes.

Input array contains both positive and negative integers, as well as zero

How to Handle:

The difference calculations and comparison will still operate correctly, as long as no integer overflow happens.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the `nums` array? Can I expect negative numbers, zeros, or very large positive numbers?
Can the input array `nums` be empty or null?
If no harmonious subsequence exists, what value should I return?
Are duplicate values in the `nums` array significant, and should they be considered when determining the length of the longest harmonious subsequence?
Could you define more formally what constitutes a subsequence in this context? Specifically, does order matter and must elements be contiguous?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every possible subsequence. A subsequence is formed by picking some numbers from the original group, in their original order.
For each subsequence you pick, check if it's 'harmonious'. This means checking if the biggest and smallest numbers in that subsequence are exactly one apart.
If the subsequence is harmonious, find how many numbers are in it.
Keep track of the biggest size you have found so far.
After checking every possible subsequence, the biggest size you tracked is your answer.

Code Implementation

def longest_harmonious_subsequence_brute_force(numbers):
    max_length_harmonious_subsequence = 0

    # Iterate through all possible subsequences
    for i in range(1 << len(numbers)):
        subsequence = []
        for j in range(len(numbers)):
            # Construct the subsequence
            if (i >> j) & 1:
                subsequence.append(numbers[j])

        # Skip empty subsequences
        if not subsequence:
            continue

        # Check if subsequence is harmonious
        min_value_subsequence = min(subsequence)
        max_value_subsequence = max(subsequence)

        # Harmonious if difference between max and min is 1
        if max_value_subsequence - min_value_subsequence == 1:
            current_subsequence_length = len(subsequence)

            # Keep track of the maximum length
            if current_subsequence_length > max_length_harmonious_subsequence:
                max_length_harmonious_subsequence = current_subsequence_length

    return max_length_harmonious_subsequence

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the list.
Then, go through the numbers that you've counted and check if the number one greater than it also appears in the list.
If the number one greater exists, add the count of the number and the count of the number one greater.
Keep track of the largest sum you find. The largest sum is the length of the longest harmonious subsequence.
The basic idea is: if you have 5 occurrences of '3' and 3 occurrences of '4', the harmonious subsequence built from those two numbers is of length 8.

Code Implementation

def find_longest_harmonious_subsequence(number_list):
    number_counts = {}

    for number in number_list:
        number_counts[number] = number_counts.get(number, 0) + 1

    longest_harmonious_sequence = 0

    # Iterate through each unique number to find harmonious pairs.
    for number in number_counts:

        # Check if the number + 1 also exists in the list.
        if (number + 1) in number_counts:

            # Calculating the length of the harmonious subsequence.
            harmonious_length = number_counts[number] + number_counts[number + 1]

            # Keep track of the largest harmonious subsequence length.
            longest_harmonious_sequence = max(longest_harmonious_sequence, harmonious_length)

    return longest_harmonious_sequence

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 since there is no subsequence in an empty array.
Input array with a single element	Return 0 because a harmonious subsequence needs at least two elements with a difference of 1.
Input array contains only identical numbers	Return 0 since the difference between the maximum and minimum of such a subsequence is 0, not 1.
Input array with extremely large positive or negative numbers	The solution should correctly handle large numbers if implemented properly with integer types that have sufficient range (e.g., long in Java, int64 in Go, etc.) and avoid overflow.
Input array contains duplicates of numbers which are 1 apart.	The frequency map will accurately reflect the counts of each number, ensuring the correct length is calculated when checking for harmonious subsequences.
No harmonious subsequence exists in the input array	The solution should correctly identify that no harmonious subsequence is present and return 0.
Array with a large number of elements, potentially causing memory issues if not handled efficiently.	Using a hash map to store element counts ensures that the solution has a time complexity of O(n) and a space complexity of O(n), avoiding memory issues for reasonable input sizes.
Input array contains both positive and negative integers, as well as zero	The difference calculations and comparison will still operate correctly, as long as no integer overflow happens.

Empty input array

How to Handle:

Return 0 since there is no subsequence in an empty array.

Input array with a single element

How to Handle:

Return 0 because a harmonious subsequence needs at least two elements with a difference of 1.

Input array contains only identical numbers

How to Handle:

Return 0 since the difference between the maximum and minimum of such a subsequence is 0, not 1.

Input array with extremely large positive or negative numbers

How to Handle:

The solution should correctly handle large numbers if implemented properly with integer types that have sufficient range (e.g., long in Java, int64 in Go, etc.) and avoid overflow.

Input array contains duplicates of numbers which are 1 apart.

How to Handle:

The frequency map will accurately reflect the counts of each number, ensuring the correct length is calculated when checking for harmonious subsequences.

No harmonious subsequence exists in the input array

How to Handle:

The solution should correctly identify that no harmonious subsequence is present and return 0.

Array with a large number of elements, potentially causing memory issues if not handled efficiently.

How to Handle:

Using a hash map to store element counts ensures that the solution has a time complexity of O(n) and a space complexity of O(n), avoiding memory issues for reasonable input sizes.

Input array contains both positive and negative integers, as well as zero

How to Handle:

The difference calculations and comparison will still operate correctly, as long as no integer overflow happens.