Longest Harmonious Subsequence - Hash Map vs Sorting Solutions

Every time you bump into a coding exercise with an obvious brute force solution, the first question you should ask is, “Can I use a hash map to optimise the solution?”. If so, that solution typically results in linear time complexity. If the answer is no, the second question should be, “Can I use sorting to optimise the solution?”. In this case, the limiting factor tends to be the sorting algorithm; the best algorithms such as Quick Sort or Merge Sort result in a O(NlogN) time complexity.

For the Longest Harmonious Subsequence coding exercise, the answer is yes for both questions, so I’ll leave you both solutions in Java.

In the first solution, I first sort the array. Then, I’ll go through the sorted array once, keeping track of the harmonious sequence current count. The only advantage of this solution over the hash map implementation is that the space complexity is O(1) instead of O(N).

public static int findLHS(int[] arr) {
    Arrays.sort(arr);

    int result = 0;
    int countPreviousStreak = 0;
    int currentCount = 0;
    for (int i = 0; i < arr.length; i++) {
        if (noTransition(i, arr)) {
            currentCount++;
        } else if (isUnitTransition(i, arr)) {
            countPreviousStreak = currentCount - countPreviousStreak;
            currentCount = countPreviousStreak + 1;
        } else {
            // transition of more than one
            countPreviousStreak = 0;
            currentCount = 1;
        }
        result = Math.max(result, currentCount);
    }
    return result;
}

private static boolean noTransition(int i, int[] arr) {
    if (i == 0) return false;
    return arr[i] - arr[i - 1] == 0;
}

private static boolean isUnitTransition(int i, int[] arr) {
    if (i == 0) return true;
    return arr[i] - arr[i - 1] == 1;
}

For the hashmap the algorithm is the following: Iterate the array once and increment the count of that element in the hash map. Calculate two harmonious sequences, current + 1 and current - 1. Keep track of the global maximum result.

public static int findLHS(int[] arr) {
    Map<Integer, Integer> counts = new HashMap<>();
    int result = 0;
    for (int elem: arr) {
        int count = counts.getOrDefault(elem, 0) + 1;
        counts.put(elem, count);

        int resultSeqMinusOne = count + counts.getOrDefault(elem - 1, 0);
        int resultSeqPlusOne = count + counts.getOrDefault(elem + 1, 0);

        result = Math.max(result, Math.max(resultSeqPlusOne, resultSeqMinusOne));
    }
    return result;
}

This solution has O(N) time complexity and O(N) space complexity.