Longest Consecutive Sequence


  • 0

    Click here to see the full article post


  • 0
    C

    For the approach #3, personally, maybe we can reduce a little bit time complexity.
    when jump out from while loop and before the next for loop, we might check whether now the longest_streak has been longer than nums.length/2+1. If it is, I thought there might not exist another longer subsequence...


  • 0

    @CodingFisher Yep! That would be a good constant optimization to include (that didn't occur to me). However, it is important to note that such an optimization would never improve the asymptotic time complexity beyond linear -- there are still cases where you need to examine every element.


  • 0
    C

    yelp, thank you.


  • 0
    R

    I guess the c++ equivalent of using HashSet is an unordered_set and hence, it cannot accomodate for duplicate elements. If we want to allow duplicates, how do we modify the approach 3


  • 0

    @RK21 This problem doesn't care about duplicates, so unordered_set should do what you want it to. All we need to know is whether a particular number appears or not, which we can accomplish without tracking duplicate numbers. If we had to deal with duplicates, I would suggest using a hash table that maps list elements to counts.


  • 0
    L

    The above solution actually missed a case of. The expect answer would be 1, but it gives 2.

    [2147483647,-2147483648]


  • 0

    @li.xiong.391 It appears that the expected answer (according to the judge's solution) is 2, but I agree that it should be 1. The constraints are not specified very clearly for this problem, so I guess this might fall under the umbrella of "ill-defined behavior".


  • 1

    In Java you can just use a TreeSet and call it done :)


  • 0

    @littlefinzer Duplicates don't actually affect this problem, so using a TreeSet would just unnecessarily increase our time complexity to O(nlgn).


  • 0

    @emptyset You're right, I was a little careless there to overlook the O(n) requirement; Will redo it


  • 0
    A

    class Solution {
    public int longestConsecutive(int[] nums) {
    final HashSet<Integer> mySet = new HashSet<Integer>();
    for (int i : nums) mySet.add(i);

        int longest = 0;
        for (int i : nums) {
            int length = 1;
            for (int j = i - 1; mySet.contains(j); --j) {
                mySet.remove(j);
                ++length;
            }
            for (int j = i + 1; mySet.contains(j); ++j) {
                mySet.remove(j);
                ++length;
            }
            longest = Math.max(longest, length);
        }
        return longest;
    }
    

    }

    This shit worked and i still confuse.


  • 0

    @anmingyu11 This is a creative solution. How it works is: because all numbers were pre-put into the mySet set, imagine if they're all sorted, you can see all the range present from left to right. Example:

    nums = [1, 3, 11, 8, 2, 7]
    mySet = [1,2,3, 11, 7,8] (anyway to look at mySet since it's a set, order does not matter)

    the "for (int i : nums)" picks any number, expand left and right from that number. This eventually scan 1 complete range and count length at the same time. Order of ranges being scanned is: (1,2,3), (7,8), then (11)


  • 0
    A

    @littlefinzer i know how it works, but, which i confused is Can anyone give a mathmatic prove that element in Hashset can be removed ? i'm not so good at english, don't know my discription is accurate enough.


  • 0
    C

    I got the point "Because the while loop is reached only when currentNum marks the beginning of a sequence (i.e. currentNum-1 is not present in nums),", but still can not understand why "the while loop can only run for n iterations throughout the entire runtime of the algorithm". Could you please explain a little bit more detail?


  • 0

    @cdt This is because current_num is never assigned to the same number twice during the entire execution of the algorithm (lemma). By the pigeonhole principle, the lemma implies that current_num can be assigned no more than n times. Additionally, because the (overall) number of while loop iterations is linearly proportional to the (overall) number of current_num assignments, the algorithm runs in linear time.

    A proof of lemma 1 by contradiction:

    Assume that current_num is assigned to some number p multiple times during the algorithm's execution. During a single iteration of the for loop, it is obvious that this is impossible, as current_num is assigned to num and incremented some number of times. Therefore, current_num must be assigned to p during multiple different for loop iterations. This is impossible via current_num = num, as the numbers are drawn from a Set (which does not allow for duplicates). This means that that, current_num is assigned to p during one iteration of the for loop, and during another iteration it is assigned to a number q (such that q < p and all integers on the interval [q .. p] are in nums). Given that all integers between q and p are in nums, the while loop will bring current_num from q to p. This is where the contradiction appears, as current_num would never have been assigned to p in the first place if p-1 was in nums. QED.


  • 0
    A

    I think, using a HashSet is a bit confusing in terms of the time complexity. For many people (and to myself in particular) it wasn't obvious that we spend O(n).
    I prefer using a HashMap here in the following way:

    1. Firstly, put every element in a HashMap and mark it as unexplored.

    2. Then iterate through the array of numbers and "explore" every number up and down, remembering the longest subsequence length.

    3. If item has already been explored - it'll be skipped.
      Thus, every item will be processed only once - so we get O(n) time complexity, what satisfies the requirements.
      public int longestConsecutive(int[] nums) {
      Map<Integer, Boolean> mapExplored = new HashMap<>();
      for (int i = 0; i < nums.length; i++) {
      mapExplored.put(nums[i], false);
      }
      int maxCounter = 0;
      for (int i = 0; i < nums.length; i++) {
      if (mapExplored.get(nums[i])) {
      continue;
      }

           int counter = 1;
           int startPos = nums[i] - 1;
           while (mapExplored.containsKey(startPos) && !mapExplored.get(startPos)) {
               counter += 1;
               mapExplored.put(startPos, true);
               startPos--;
           }
           
           startPos = nums[i] + 1;
           while (mapExplored.containsKey(startPos) && !mapExplored.get(startPos)) {
               counter += 1;
               mapExplored.put(startPos, true);
               startPos++;
           }
           
           if (maxCounter < counter) {
               maxCounter = counter;
           }
           mapExplored.put(nums[i], true);
       }
       return maxCounter;    
      

      }


  • 0
    S

    @emptyset
    I think the complexity is O(nn) because the 'in' operator in python is of complexity O(n)
    'in' operator inside of for loop would give complexity to be O(n
    n)

    ref: https://wiki.python.org/moin/TimeComplexity


  • 0

    @shlok.gandhi, the in operator is overloaded, so it functions different depending on what container is used. For a list, the complexity is O(n), but we are using a set here (which has O(1) complexity).


  • 0
    W

    wouldn't [100,99, 98, ..., 1] (i.e. an array in reverse order) make this run in $$O(n^2)$$ because for every num, it have to go through the entire set so far?


Log in to reply
 

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