Would this code be considered as O(n) time complexity?


  • 0
    A

    I use a visited array to indicate whether a element is visited. the code guarantee that each node in the array is only visited once, which means if the program find an element is visited before it just continues to the next element. My question, is this still O(n), since the program may check whether one node is visited many times?

    public class Solution {
    public int longestConsecutive(int[] num) {
        boolean[] visited = new boolean[num.length];
        HashMap<Integer, Integer> numPos = new HashMap<Integer, Integer>();
        for(int i = 0; i < num.length; i++){
            if(!numPos.containsKey(num[i])){
                numPos.put(num[i], i);
            }
        }
        int maxlen = 0;
        for(int i = 0; i < num.length; i++){
            if(visited[i])
                continue;
            int len = 1;
            visited[i] = true;
            int val = num[i];
            int curVal = val;
            while(numPos.containsKey(curVal+1) && !visited[numPos.get(curVal+1)]){
                visited[numPos.get(val+1)] = true;
                curVal = curVal + 1;
                len ++;
            }
            curVal = val;
            while(numPos.containsKey(curVal-1) && !visited[numPos.get(curVal -1)]){
                visited[numPos.get(curVal -1)] = true;
                curVal = curVal -1;
                len ++;
            }
            if(len > maxlen){
                maxlen = len;
            }
        }
        return maxlen;
    }
    

    }


  • 0
    M

    I think it's guaranteed to be O(n) because each element in array is visited only once.


Log in to reply
 

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