algoadvance

Leetcode 594. Longest Harmonious Subsequence

Problem Statement

Given an integer array nums, return the length of the longest harmonious subsequence among all its possible subsequences.

A harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

Clarifying Questions

  1. What is the length limit of the array?
    • Typically, interview problems handle arrays up to a size of 10^4 to 10^5, but confirming the size can help optimize the solution.
  2. Can the array contain negative numbers?
    • This can affect sorting or hashmap-based solutions.
  3. Are there any constraints on the values that the array can contain?
    • Knowing the range (e.g., all numbers are within the range of [-10^9, 10^9]) can help in choosing the appropriate data structures.

Strategy

  1. Use a HashMap to count occurrences of each number: We will first traverse the array to build a frequency map where the keys are the elements of the array and the values are their counts.
  2. Determine harmonious subsequences: We’ll then iterate through the keys of the hashmap and check for each key if the key + 1 exists. If it does, we sum their counts to determine the length of the harmonious subsequence.
  3. Track the maximum subsequence length: We continuously update the maximum length found using the approach described above.

This algorithm ensures that we only need to traverse the array a couple of times, making it efficient.

Time Complexity

Code

import java.util.HashMap;
import java.util.Map;

public class LongestHarmoniousSubsequence {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        
        // Populate the frequency map
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        int maxLength = 0;
        
        // Iterate through the map to find the longest harmonious subsequence length
        for (int key : frequencyMap.keySet()) {
            if (frequencyMap.containsKey(key + 1)) {
                int currentLength = frequencyMap.get(key) + frequencyMap.get(key + 1);
                maxLength = Math.max(maxLength, currentLength);
            }
        }
        
        return maxLength;
    }

    public static void main(String[] args) {
        LongestHarmoniousSubsequence solution = new LongestHarmoniousSubsequence();
        int[] nums = {1, 3, 2, 2, 5, 2, 3, 7};
        System.out.println(solution.findLHS(nums)); // Output: 5
    }
}

This code should solve the problem of finding the longest harmonious subsequence in a given array of integers by leveraging a hashmap to store frequencies and then checking adjacent keys to compute possible subsequences’ lengths.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI