My java solution use hashmap O(N)


  • 4
    M

    I use a hashmap to save the array's element. And iterative the array from 0 index to the length. When i visit a element of array, i will search the (element + 1) or (element - 1) in the hashmap. If there exits, then plus 1 or miner 1 and continue search in the hashmap. When i find a target, the max consecutive sequence length plus 1. And when the search end, remove the element from hashmap.

    Building the hashMap takes O(N) and the loop also takes O(N). The search in hashmap, commonly think that takes O(1). So the result of this solution is O(N + N + 1). The result is O(N). It is a linear complexity solution.

    Upon is my own thought. Anything wrong please tell me ! I appreciate that.

    public class Solution {
        public int longestConsecutive(int[] num) {
            int length = num.length;
            if (length == 0 || length == 1) {
                return length;
            }
            
            Map<Integer, Integer> numMap = new HashMap<Integer, Integer>();
            
            for (int i=0; i<length; i++) {
                numMap.put(num[i], 1);
            }
            
            int maxLen = 0;
            for (int i=0; i<length; i++) {
                if (!numMap.containsKey(num[i])) {
                    continue;
                }
                int max = 1;
                int temp1 = num[i];
                int temp2 = num[i];
                while (numMap.containsKey(++temp1)) {
                    max+=1;
                    numMap.remove(temp1);
                }
                while(numMap.containsKey(--temp2)) {
                    max+=1;
                    numMap.remove(temp2);
                }
                numMap.remove(num[i]);
                if (max>maxLen) {
                    maxLen = max;
                }
            }
            return maxLen;
        }
    }

  • 0
    H
    This post is deleted!

  • 0
    M

    you mean the for loop to building base hashmap? or the next for loop behind first ?


  • 3
    L

    yours is not O(n), it is O(n^2), how about this case [1,1,1,1,1,1];


  • 0
    L

    this is the O(n) solution:

        int len = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                continue;
            }
            map.put(nums[i], 1);
    
            int end = nums[i];
            int begin = nums[i];
            if (map.containsKey(nums[i] + 1)) {
                end = nums[i] + map.get(nums[i] + 1);
            }
            if (map.containsKey(nums[i] - 1)) {
                begin = nums[i] - map.get(nums[i] - 1);
            }
            map.put(end, end - begin + 1);
            map.put(begin, end - begin + 1);
            len = Math.max(len, end - begin + 1);
        }
        return len;
    

Log in to reply
 

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