Problem of The Day: Longest Harmonious Subsequence

Problem Statement

leetcode problem link

Brute Force [TLE]

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        N = len(nums)
        res = 0
        arr = sorted(list(set(nums)))
        for i in range(len(arr) - 1):
            if arr[i + 1] - arr[i] == 1:
                curr = 0
                for j in range(N):
                    if nums[j] in [arr[i], arr[i + 1]]:
                        curr += 1
                res = max(res, curr)

        return res

Improved Algorithm [Accepted]

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        N = len(nums)
        res = 0
        counter = Counter(nums)
        arr = sorted(list(set(nums)))
        pairs = []
        for i in range(len(arr) - 1):
            if arr[i + 1] - arr[i] == 1:
                res = max(res, counter[arr[i + 1]] + counter[arr[i]])
        return res

Editorial

Approach 1: Brute Force

public class Solution {
    public int findLHS(int[] nums) {
        int res = 0;
        for (int i = 0; i < (1 << nums.length); i++) {
            int count = 0, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            for (int j = 0; j < nums.length; j++) {
                if ((i & (1 << j)) != 0) {
                    min = Math.min(min, nums[j]);
                    max = Math.max(max, nums[j]);
                    count++;
                }
            }
            if (max - min == 1)
                res = Math.max(res, count);
        }
        return res;
    }
}

Approach 2: Better Brute Force

public class Solution {
    public int findLHS(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            boolean flag = false;
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == nums[i])
                    count++;
                else if (nums[j] + 1 == nums[i]) {
                    count++;
                    flag = true;
                }
            }
            if (flag)
                res = Math.max(count, res);
        }
        return res;
    }
}

Approach 3: Using Sorting

public class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int prev_count = 1, res = 0;
        for (int i = 0; i < nums.length; i++) {
            int count = 1;
            if (i > 0 && nums[i] - nums[i - 1] == 1) {
                while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                    count++;
                    i++;
                }
                res = Math.max(res, count + prev_count);
                prev_count = count;
            } else {
                while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                    count++;
                    i++;
                }
                prev_count = count;
            }
        }
        return res;
    }
}

Approach 4: Using HashMap

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

Approach 5: In Single Loop

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