Longest Harmonious Subsequence - Practice Coding Problems

Longest Harmonious Subsequence - Problem

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.

Note: A subsequence is derived from an array by deleting some or no elements without changing the order of the remaining elements.

Input & Output

Example 1 — Basic Harmonious Array

$ Input: nums = [1,3,2,2,5,2,3,7]

› Output: 5

💡 Note: The longest harmonious subsequence is [3,2,2,2,3] with length 5. It contains numbers 2 and 3, and 3-2=1.

Example 2 — No Harmonious Subsequence

$ Input: nums = [1,2,3,4]

› Output: 2

💡 Note: Multiple harmonious subsequences exist: [1,2], [2,3], [3,4], each with length 2. Return the maximum length which is 2.

Example 3 — All Same Numbers

$ Input: nums = [1,1,1,1]

› Output: 0

💡 Note: All numbers are the same, so max-min=0, not 1. No harmonious subsequence exists.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with various numbers

Find Harmonious

Look for subsequences where max - min = 1

Return Length

Length of longest valid subsequence

Key Takeaway

🎯 Key Insight: Only consecutive integers can form harmonious subsequences, so count frequencies and pair adjacent numbers

Asked in

a Amazon 15 f Facebook 8

The key insight is that only consecutive numbers (x and x+1) can form a harmonious subsequence. The optimal approach uses a frequency count hash map to count each number's occurrences, then checks each number x with x+1 to find the maximum combined frequency. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Sort First Approach	O(n log n)	O(1)	Sort array then use sliding window to find harmonious segments
Frequency Count with Hash Map	O(n)	O(n)	Count frequencies and check adjacent number pairs
Brute Force	O(2ⁿ)	O(n)	Check all possible subsequences to find harmonious ones

Sort First Approach — Algorithm Steps

Sort the input array
Use sliding window with two pointers
Expand window while difference ≤ 1
Update maximum length when difference equals 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort to group similar numbers together

Sliding Window

Use two pointers to maintain valid window

Check Harmonious

Window is harmonious when max - min = 1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int numsSize) {
    if (numsSize < 2) return 0;
    
    qsort(nums, numsSize, sizeof(int), compare);
    
    int maxLength = 0;
    int left = 0;
    
    for (int right = 0; right < numsSize; right++) {
        // Shrink window if difference > 1
        while (nums[right] - nums[left] > 1) {
            left++;
        }
        
        // Check if current window is harmonious
        if (nums[right] - nums[left] == 1) {
            int length = right - left + 1;
            if (length > maxLength) {
                maxLength = length;
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ']') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), sliding window takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for pointers

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort First Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler