Why is this Solution Slow even though it is O(N)
Avinash Doddi
193
Union-FindPythonHash FunctionHash TableInterview

Why is this Solution Slow even though it is O(N) ?

view Problem Statement

image

from collections import defaultdict as maps
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums); nums = list(nums); n = len(nums);
        if n == 0: return 0;
        if n == 1: return 1;
        present = maps(int); visited = maps(int)
        for i in range(n):
            present[nums[i]] = 1;
            visited[i] = 0;
        i = 0; curr = 0; cnt, maxx = 0, 0; visset = {nums[i] for i in range(n)}
        while n > 0:
            cnt = 1;
            for ind in visset:
                curr = ind; n -= 1; visset.remove(ind); break;
            # less than curr::
            curr, temp = curr, curr;
            while n > 0:
                if present[curr - 1]:
                    curr -= 1; n -= 1; visset.remove(curr); cnt += 1;
                else:
                    break;
            # greater than curr::
            while n > 0:
                if present[temp + 1]:
                    temp += 1; n -= 1; visset.remove(temp); cnt += 1;
                else:
                    break;
            maxx = max(cnt, maxx);
        maxx = max(cnt, maxx);
        return maxx

Complexity Analysis:

-> O(N) for len function
-> O(N) for the for loop
-> the while loop runs till n > 0 and remove in set is O(1), so the overall complexity comes down to O(N)
the overall complexity of this program is O(N) which is the optimal one.
can anybody explain why this code is taking more time than it is intended?

Comments (2)