🧑‍💻 LeetCode 0594 — Longest Harmonious Subsequence🔥

The Longest Harmonious Subsequence problem on LeetCode asks us to find the length of the longest subsequence where the difference between the maximum and minimum values is exactly 1. This blog will cover all solutions in Java, with detailed explanations of time and space complexity.

Generated by ChatGPT

🤔 Problem Statement

Level 🔥 Easy

You are given an integer array nums. A harmonious subsequence is a subsequence where the difference between its maximum and minimum value is exactly 1. Return the length of its longest harmonious subsequence among all possible subsequences.

Input: nums = [1, 3, 2, 2, 5, 2, 3, 7]
Output: 5
Explanation: The longest harmonious subsequence is [3, 2, 2, 2, 3].

💡 Solution

✍ Approach 1: Using HashMap

Idea

• Use a HashMap to count the frequency of each number in the array.
• For each number key in the map, check if key + 1 exists. If it does, compute the total length of the subsequence formed key and key + 1.

Algorithm

• Traverse the array and store the frequency of each number in a HashMap.
• Iterate through the HashMap. For each key, if key + 1 exists, calculate the subsequence length as: freq(key)+freq(key + 1)
• Track the maximum subsequence length and return it.

import java.util.HashMap;

public class Solution {
    public int findLHS(int[] nums) {
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        int maxLength = 0;
        for (int key : freqMap.keySet()) {
            if (freqMap.containsKey(key + 1)) {
                maxLength = Math.max(maxLength, freqMap.get(key) + freqMap.get(key + 1));
            }
        }
        return maxLength;
    }
}

Time Complexity: O(n)

• Building the HashMap takes O(n), and iterating over the keys takes O(n).

Space Complexity: O(n)

• The HashMap stores up to n unique keys in the worst case.

✍ Approach 2: Sorting and Two pointers

Idea

• Sort the array to bring elements with similar values close together.
• Use two pointers (start and end) to find the longest harmonious subsequence. Keep start fixed while end moves forward.
• If the difference between nums[end] and nums[start] exceeds 1, increment start.

Algorithm: Sort the array and use two pointers to traverse the array:

• If nums[end] - nums[start] == 1, calculate the length of the harmonious subsequence.
• If nums[end] - nums[start] > 1, increment start.

import java.util.Arrays;

public class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);

        int start = 0;
        int maxLength = 0;

        for (int end = 0; end < nums.length; end++) {
            while (nums[end] - nums[start] > 1) {
                start++;
            }
            if (nums[end] - nums[start] == 1) {
                maxLength = Math.max(maxLength, end - start + 1);
            }
        }
        return maxLength;
    }
}

Time Complexity: O(n log n): Sorting the array takes O(n log n). The two-pointer traversal is O(n).

Space Complexity: O(1) No additional space is used, apart from sorting in place.

✍ Approach 3: Optimized HashMap

Idea: While traversing the array, update the frequency map and calculate the harmonious subsequence length dynamically. This avoids a second pass over the HashMap.

Algorithm

• Traverse the array and update the frequency map in real time.
• For each number, check if num - 1 and num + 1 exist in the map. If they do, calculate the harmonious subsequence length.

import java.util.HashMap;

public class Solution {
    public int findLHS(int[] nums) {
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        int maxLength = 0;

        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);

            if (freqMap.containsKey(num + 1)) {
                maxLength = Math.max(maxLength, freqMap.get(num) + freqMap.get(num + 1));
            }
            if (freqMap.containsKey(num - 1)) {
                maxLength = Math.max(maxLength, freqMap.get(num) + freqMap.get(num - 1));
            }
        }

        return maxLength;
    }
}

Time Complexity: O(n) A single traversal of the array updates the map and calculates the length.

Space Complexity: O(n) The HashMap stores the frequency of each number.

🙏 Conclusion

The Longest Harmonious Subsequence problem offers multiple approaches, each with its own trade-offs. The HashMap solutions are faster but use more space, while the Sorting + Two Pointers approach is space-efficient but slower due to sorting. Choose the solution that best fits your requirements!

Have any questions or want to dive deeper into one of the solutions? Let me know in the comments below! 😊

https://leetcode.com/problems/longest-harmonious-subsequence/submissions/1456153184

[embed]GitHub - nphausg/leetcode.solution: 💎 💎 💎 LeetCode is the best platform to help you enhance your… 💎 💎 💎 LeetCode is the best platform to help you enhance your skills, expand your knowledge and prepare for technical…github.com