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;
}
}
############
class Solution {
public int findLHS(int[] nums) {
Map<Integer, Integer> counter = new HashMap<>();
for (int num : nums) {
counter.put(num, counter.getOrDefault(num, 0) + 1);
}
int ans = 0;
for (int num : nums) {
if (counter.containsKey(num + 1)) {
ans = Math.max(ans, counter.get(num) + counter.get(num + 1));
}
}
return ans;
}
}