Java

  • import java.util.Arrays;
    import java.util.HashMap;
    import java.util.Map;
    
    import junit.framework.Assert;
    
    
    /*
    
    We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.
    
    Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.
    
    Example 1:
    Input: [1,3,2,2,5,2,3,7]
    Output: 5
    Explanation: The longest harmonious subsequence is [3,2,2,2,3].
    Note: The length of the input array will not exceed 20,000.
    
     */
    
    public class Longest_Harmonious_Subsequence {
    
    	@SuppressWarnings("deprecation")
    	public static void main(String[] args) {
    		Longest_Harmonious_Subsequence out = new Longest_Harmonious_Subsequence();
    		Solution3 s = out.new Solution3();
    
    		int[] input1 = new int[]{1,1,1,1}; // corner case, should return 0, must be exactly 1
    		int[] input2 = new int[]{1,1,1,2};
    		int[] input3 = new int[]{1,2,2,2};
    		int[] input4 = new int[]{1,1,1,3};
    		int[] input5 = new int[]{1}; // [1] single element should return 0
    		int[] input6 = new int[]{1,2,3,4};
    		int[] input7 = new int[]{1,3,2,2,5,2,3,7};
    
    		Assert.assertEquals(0, s.findLHS(input1));
    		Assert.assertEquals(4, s.findLHS(input2));
    		Assert.assertEquals(4, s.findLHS(input3));
    		Assert.assertEquals(0, s.findLHS(input4));
    		Assert.assertEquals(0, s.findLHS(input5));
    		Assert.assertEquals(2, s.findLHS(input6));
    		Assert.assertEquals(5, s.findLHS(input7));
    
    		System.out.println("all passed");
    	}
    
    	public class Solution {
    	    public int findLHS(int[] nums) {
    	        Map<Long, Integer> map = new HashMap<>();
    	        for (long num : nums) {
    	            map.put(num, map.getOrDefault(num, 0) + 1);
    	        }
    	        int result = 0;
    	        for (long key : map.keySet()) {
    	            if (map.containsKey(key + 1)) {
    	                result = Math.max(result, map.get(key + 1) + map.get(key));
    	            }
    	        }
    	        return result;
    	    }
    	}
    
    
    	// wrong solution, getting too complicated, too many branches
    	public class Solution2 {
    	    public int findLHS(int[] nums) {
    
    	    	if(nums == null || nums.length <= 1) {
    	    		return 0;
    	    	}
    
    	    	// o(NlogN)
    	    	Arrays.sort(nums);
    
    	    	// o(N)
    	    	int longest = 0; // assume nums[] has at least 1 element
    	    	// 2 index-pointers, to track segement with diff<=1
    	    	int i = 0;
    	    	int j = 0;
    	    	int count = 1;
    	    	boolean diffOne = false;
    	    	while(j < nums.length) {
    	    		if (nums[j] - nums[i] <= 1) { // EXACTLY 1
    	    			diffOne = (nums[j] - nums[i] == 1);
    	    			if (diffOne) {
    	    				longest = Math.max(longest, count); // only check here, to avoid [1,1,1,1] case
    	    			}
    
    	    			j++;
    	    			count++;
    
    	    		} else { // check longest and reset
    
    	    			// last check
    	    			if (diffOne) {
    	    				longest = Math.max(longest, count);
    	    			}
    
    	    			i = j;
    	    			count = 1;
    	    			diffOne = false;
    	    		}
    	    	}
    
    	    	return longest;
    	    }
    	}
    
    	// bucket idea, sort, then probe right for current segment length, and +1 segment length
    	public class Solution3 {
    
    
    	    public int findLHS(int[] nums) {
    	    	if(nums == null || nums.length <= 1) {
    	    		return 0;
    	    	}
    
    	    	// o(NlogN)
    	    	Arrays.sort(nums);
    
    	    	// o(N)
    	    	int longest = 0;
    	    	int i = 0;
    	    	int j = 0;
    
    	    	while(i < nums.length) {
    		    	int currentBucketLength = getBucketLength(nums, i); // current digit dulicate count
    
    		    	// if next bucket digit is +1, then get length
    		    	if (tmpEndIndex + 1 < nums.length && nums[tmpEndIndex + 1] - nums[i] == 1) {
    		    		int nextBucketLength = getBucketLength(nums, tmpEndIndex + 1);
    		    		longest = Math.max(longest, currentBucketLength + nextBucketLength);
    //		    	} else {
    
    		    	}
    
    		    	i = tmpEndIndex + 1;
    	    	}
    
    	    	return longest;
    	    }
    	}
    	private int tmpEndIndex = 0;
    
    	private int getBucketLength(int[]nums, int startIndex) {
    
    		if(startIndex >= nums.length) {
    			tmpEndIndex = startIndex;
    			return 0;
    		}
    
    		int length = 1;
    		while(startIndex + 1 < nums.length && nums[startIndex] == nums[startIndex + 1]) {
    			startIndex++;
    			tmpEndIndex = startIndex;
    
    			length++;
    		}
    		return length;
    	}
    }
    
  • // OJ: https://leetcode.com/problems/longest-harmonious-subsequence/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        int findLHS(vector<int>& nums) {
            unordered_map<int, int> cnts;
            int ans = 0;
            for (int n : nums) cnts[n]++;
            for (auto &p : cnts) {
                if (cnts.find(p.first + 1) == cnts.end()) continue;
                ans = max(ans, p.second + cnts[p.first + 1]);
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        d = collections.Counter(nums)
        for num in nums:
          if num + 1 in d:
            ans = max(ans, d[num] + d[num + 1])
        return ans
    
    

Java

  • class Solution {
        public int findLHS(int[] nums) {
            Map<Integer, Integer> numCountMap = new HashMap<Integer, Integer>();
            for (int num : nums) {
                int count = numCountMap.getOrDefault(num, 0);
                count++;
                numCountMap.put(num, count);
            }
            int longest = 0;
            Set<Integer> numsSet = numCountMap.keySet();
            for (int num : numsSet) {
                int prevNum = num - 1, nextNum = num + 1;
                if (!numsSet.contains(prevNum) && !numsSet.contains(nextNum))
                    continue;
                int curLength = numCountMap.get(num);
                if (numsSet.contains(prevNum)) {
                    int length = curLength + numCountMap.get(prevNum);
                    longest = Math.max(longest, length);
                }
                if (numsSet.contains(nextNum)) {
                    int length = curLength + numCountMap.get(nextNum);
                    longest = Math.max(longest, length);
                }
            }
            return longest;
        }
    }
    
  • // OJ: https://leetcode.com/problems/longest-harmonious-subsequence/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        int findLHS(vector<int>& nums) {
            unordered_map<int, int> cnts;
            int ans = 0;
            for (int n : nums) cnts[n]++;
            for (auto &p : cnts) {
                if (cnts.find(p.first + 1) == cnts.end()) continue;
                ans = max(ans, p.second + cnts[p.first + 1]);
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        d = collections.Counter(nums)
        for num in nums:
          if num + 1 in d:
            ans = max(ans, d[num] + d[num + 1])
        return ans
    
    

All Problems

All Solutions