Simple JAVA Solution Using HashMap


  • 0

    ...

    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        boolean[] visited = new boolean[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i]))
                map.put(nums[i], i);
            else
                visited[i] = true;
        }
        
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                
                int localCnt = 1;
                for (int j = nums[i]-1; map.containsKey(j); localCnt++, visited[map.get(j--)]=true);
                for (int j = nums[i]+1; map.containsKey(j); localCnt++, visited[map.get(j++)]=true);
                
                cnt = localCnt > cnt ? localCnt : cnt;
            }
        }
        
        return cnt;
    }
    

    ...


  • 0
    C

    Can you explain a little about the algorithm? And how this algorithm achieve the O(n) time complexity?


  • 0

    @chenw2000
    The time complexity is O(n).

    The basic idea is using a HashMap map to store all numbers that occurred in the nums array. The array visited is used to mark if a number is already be found in a sequence, so that we never try to find the consecutive sequence for it again.

    To find the consecutive sequence contains number i we need to look at numbers on the left hand side of it, i.e. i-1, i-2... and numbers on the right hand side of it, i.e. i+1,i+2... we can use the map to check if these numbers are in the array, and if they are in, we mark their indices as visited, to indicate that the consecutive sequence of them are already found.


Log in to reply
 

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