9LOC Java O(n) solution


  • 13
    K
    <pre>
    public class Solution { <br/>
        public int longestConsecutive(int[] nums) {<br/>
          Set<Integer> set = new HashSet<>();
          int max = 0;
          for(int num : nums) set.add(num);
          for(int num : nums) if (!set.contains(num-1)) {
            int val = num;
            while(set.remove(val++));
            max = Math.max(max, val-num-1);
          }
          return max;
        }
    }
    </pre>

  • 0
    X

    Is this really o(N)? It seems to contain a 'while' inner loop.

    Sorry, it is. The worst case is [N, N-1, N-2, ... 3,2,1] which need to do two-pass enumeration of the entire list in the second loop . So the worst case is O(3N), which, by omitting the constant factor, is also O(N).


  • 0
    J
    This post is deleted!

  • 0
    J
    This post is deleted!

Log in to reply
 

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