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 :
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 .