Scale Engineer

Longest Harmonious Subsequence

Easy
#0566Time: O(U * N), where N is the number of elements in `nums` and U is the number of unique elements. In the worst-case scenario where all elements are unique, U = N, leading to a time complexity of O(N^2).Space: O(U), where U is the number of unique elements in `nums`. In the worst case, all elements are unique, so the space complexity is O(N).2 companies
Patterns
Sliding WindowCounting
Algorithms
Sorting
Data structures
ArrayHash Table
Companies
LiveRampZS Associates

Prompt

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 * 104
  • -109 <= nums[i] <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through each unique number in the array. For each number x, it checks if x+1 also exists. If it does, it then re-iterates through the entire original array to count the occurrences of x and x+1 to find the length of the harmonious subsequence they form. This process is repeated for every unique number, and the maximum length found is the result.

Algorithm

  • Create a Set of unique numbers from the input array nums to avoid redundant checks.
  • Initialize a variable maxLength to 0.
  • Iterate through each unique number num in the set.
  • For each num, check if num + 1 also exists in the set.
  • If it does, this pair can form a harmonious subsequence. We then need to find its length.
  • To find the length, iterate through the original nums array and count all elements that are equal to num or num + 1.
  • Update maxLength with the maximum length found so far.
  • After checking all unique numbers, return maxLength.

Walkthrough

The brute-force method systematically checks every possible base number for a harmonious subsequence. First, we identify all unique numbers present in the input array nums by storing them in a HashSet. Then, for each unique number currentNum, we verify if its counterpart, currentNum + 1, is also present in the set. If both exist, they form a potential harmonious subsequence. To calculate its length, we perform a full scan of the original nums array, counting every occurrence of currentNum and currentNum + 1. This sum gives the length of the subsequence formed by this pair. We maintain a variable, maxLength, to keep track of the largest length found across all such pairs. While straightforward, this method is computationally expensive because of the repeated scans of the input array.

class Solution {    public int findLHS(int[] nums) {        int maxLength = 0;        java.util.Set<Integer> uniqueNums = new java.util.HashSet<>();        for (int num : nums) {            uniqueNums.add(num);        }         for (int num : uniqueNums) {            if (uniqueNums.contains(num + 1)) {                int currentLength = 0;                for (int val : nums) {                    if (val == num || val == num + 1) {                        currentLength++;                    }                }                maxLength = Math.max(maxLength, currentLength);            }        }        return maxLength;    }}

Complexity

Time

O(U * N), where N is the number of elements in `nums` and U is the number of unique elements. In the worst-case scenario where all elements are unique, U = N, leading to a time complexity of O(N^2).

Space

O(U), where U is the number of unique elements in `nums`. In the worst case, all elements are unique, so the space complexity is O(N).

Trade-offs

Pros

  • Simple to understand and implement.

  • Does not require complex data structures other than a set.

Cons

  • Highly inefficient due to nested iteration. The time complexity is quadratic in the worst case.

  • Redundant counting work. For a pair (x, x+1), the counts are recalculated by iterating over the entire array.

Solutions

class Solution {public  int findLHS(int[] nums) {    Map<Integer, Integer> counter = new HashMap<>();    for (int num : nums) {      counter.put(num, counter.getOrDefault(num, 0) + 1);    }    int ans = 0;    for (int num : nums) {      if (counter.containsKey(num + 1)) {        ans = Math.max(ans, counter.get(num) + counter.get(num + 1));      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem