Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

What is the Big o notation of the longest consecutive sequence algorithm below

I google the solution for the longest consecutive sequence algorithm here is the link to the question in leetcode leetcodeQuestion and below is the algorithm solution. I was confused by some of the comments on the website where i got the solution some where saying that the solution is not O(n) time complexity since there is a for loop nested inside of another for loop, that make sense to me but when i run the question on leetcode it works without any issues even though one of the constrains is that the solution must be O(n) time complexity, which makes me assume it in fact is O(n). so is this algorithm O(n) or not?. If my question is missing information let me know and i will update it quickly

var longestConsecutive = function(nums) {
  if (nums == null || nums.length === 0) return 0;
  const set = new Set(nums);
  let longest = 0;
  for (let num of nums) {
    if (!set.has(num - 1)) {
      let count = 0;
      while (set.has(count+num)) {
        count++;
      }
      longest = Math.max(longest,count);
    }
  }
  return longest;
};

>Solution :

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

The algorithm is O(n). Pasting the explaination from the same site below :

Complexity Analysis

Time complexity : O(n).

Although the time complexity appears to be quadratic due to the while
loop nested within the for loop, closer inspection reveals it to be
linear. Because the while loop is reached only when currentNum marks
the beginning of a sequence (i.e. currentNum-1 is not present in
nums), the while loop can only run for nnn iterations throughout the
entire runtime of the algorithm. This means that despite looking like
O(n⋅n) complexity, the nested loops actually run in
O(n+n)=O(n) time. All other computations
occur in constant time, so the overall runtime is linear.

Space complexity : O(n).

In order to set up O(1) containment lookups, we allocate
linear space for a hash table to store the O(n) numbers in
nums. Other than that, the space complexity is identical to that of
the brute force solution.

Also, sometimes in Leetcode you can submit a solution with higher complexity than the asked complexity but it does not mean that the accepted solution is efficient. Generally for the non efficient solution the site says ‘Your solution beats x % of solution’ where x is a pretty low number .

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading