Simple Java HashMap Solution


  • 32
    • 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;
    }

  • 8
    H

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


  • 2
    Y

    Any reason to use long instead of int?


  • 7

    @yl
    to handle this :

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

  • 1
    Y

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


  • 0

    @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.


  • 1
    Y

    @jaqenhgar Great catch :)


  • 0
    K

    @harkness So clever u are.


  • 0
    J

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

  • 1
    Z

    @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.


  • 0

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


  • 0
    A

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


  • 1
    H

    @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.


  • 0
    G

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

  • 0
    A

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


  • 0
    T

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

  • 1
    A

    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;
    

Log in to reply
 

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