Another accepted Java O(n) solution


  • 41
    public int longestConsecutive(int[] num) {
      int max = 0;
      
      Set<Integer> set = new HashSet<Integer>();
      for (int i = 0; i < nums.length; i++) {
        set.add(nums[i]);
      }
      
      for (int i = 0; i < nums.length; i++) {
        int count = 1;
        
        // look left
        int num = nums[i];
        while (set.contains(--num)) {
          count++;
          set.remove(num);
        }
        
        // look right
        num = nums[i];
        while (set.contains(++num)) {
          count++;
          set.remove(num);
        }
        
        max = Math.max(max, count);
      }
      
      return max;
    }

  • 0
    L

    Cool! Amortized O(n) solution.


  • 0
    F

    It seems to me that in the worst case, this solution is far more than O(n).
    Consider the in put are integers from 1 to n.

    But, this is still a good solution.

    =========================================================

    It's my mistake. I didn't notice the remove option.
    Yes, this is an amortized O(n) solution.


  • 0
    H

    66666666666666666666666666


  • 0
    F

    This is definitely an O(n) solution.


  • 0

    I love your solution!


  • 0
    R

    really is to understand !! Thanks


Log in to reply
 

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