# Simple Java HashMap Solution

• The idea is to keep a count of all the numbers, and eventually for each of the numbers, check if there's any adjacent number. If it's present, then add the count of both - since these two numbers form subsequence in the array.

Update : from @harkness comment, we don't need to check both +1 and -1;

``````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;
}``````

• You don't need to check both `key+1` and `key-1`. Checking one of them is enough.

• Any reason to use long instead of int?

• @yl
to handle this :

``````findLHS(new int[]{-2147483648 , 2147483647});
//2147483647 + 1 = -2147483648 , and we don't want that.``````

• @jaqenhgar Yes you are right, they should add this to test case.

• @yl Oh I wasn't aware that it's not there!
@1337c0d3r We're missing a test case. My answer is 0, and OJ is 2.

• @jaqenhgar Great catch :)

• @harkness So clever u are.

• Great solution! Here is the C++ version

``````class Solution {
public:
int findLHS(vector<int>& nums) {
unordered_map<int, int> map;
for(auto num : nums) {
if(map.find(num) == map.end())
map[num] = 1;
else
map[num] += 1;
}
int result = 0;
for (auto iter = map.begin(); iter != map.end(); ++iter)
if (map.find(iter->first + 1) != map.end())
result = max(result, iter->second + map[iter->first + 1]);
return result;
}
};
``````

• @jtimberlakers you don't have to check whether num is in the map when counting the frequency. If num doesn't exist, default constructor will generate one. So "map[num]++;" will be sufficient.

• @jaqenhgar If we use TreeMap will it optimize the solution, because we are searching for nearby keys always (key+1) ?

• @harkness Can you specify the reason not to check key-1? Thanks

• @arthursunbao if `key` and `key-1` form a valid answer, then we should be able to find it when checking `key-1` as the key.

• @jaqenhgar yes,we are just same,but I sort the `nums` firstly,then use `HashMap` to count it.

``````public class Solution {
public int findLHS(int[] nums) {
Arrays.sort(nums);
Map<Integer,Integer> map=new HashMap<>();
int max=0;
for(Integer i:nums){
map.put(i,map.getOrDefault(i,0)+1);
}
for(int i=1;i<nums.length;i++){
if(nums[i]-nums[i-1]==1)max=Math.max(max,map.get(nums[i])+map.get(nums[i-1]));
}
return max;
}
}
``````

• In this solution, it has duplicate calculation, how to improve it?

• same idea:(but as discussed above, no need to check e+1 and e -1 simultaneously, one is enoug.)

``````public int findLHS(int[] nums) {
int ret = 0, sum;
HashMap<Integer, Integer> hm = new HashMap<>();
for (int e : nums)
hm.put(e, hm.getOrDefault(e, 0) + 1);
for (int e : hm.keySet()) {
sum = Math.max(hm.getOrDefault(e + 1, 0), hm.getOrDefault(e - 1, 0)) + hm.get(e);
if (sum > ret && Math.max(hm.getOrDefault(e + 1, 0), hm.getOrDefault(e - 1, 0)) != 0) {
ret = sum;
}
}
return ret;
}``````

• My code without using HashMap. Beats 91% of submissions

`````` Arrays.sort(nums);
int min =0; int count = 0;
for(int i=1;i<nums.length;)
{
if(nums[i]-nums[min]==0)
i++;
else if( nums[i]-nums[min] ==1){
count = Math.max(count, i-min+1);
i++;
}
else
min++;
}
return count;
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.