100% Faster 🔥 Python3 | Java | JavaScript fast O(n) and easy O(nlogn) solutions with explanations
Please upvote if it helped \uD83D\uDE05, Thank You!\n---\n## Connect with me:\n\n LinkedIn : saivigneshgolla\n GitHub : GodsScion\n My Hot Project \uD83D\uDD25 
## Please upvote if it helped \uD83D\uDE05, Thank You!\n---\n## Connect with me:\n\n* LinkedIn : [saivigneshgolla](https://www.linkedin.com/in/saivigneshgolla/)\n* GitHub : [GodsScion](https://github.com/GodsScion)\n* My Hot Project \uD83D\uDD25 : [Auto job applier - Linkedin (Python Proj)](https://github.com/GodsScion/Auto_job_applier_linkedIn) \uD83D\uDC40\n\n---\n# 1. Python\n\n## Intuition\n* For every element we need to check if it has a sequence. If yes, what are it\'s sequential numbers and sequence\'s length? Also, when we visit a number, since we know it\'s sequential numbers, we can skip checking them.\n\n* Usually a search operation like `in` takes longer time on lists vs sets. Average search time on Set is usually O(1) and unlike lists we don\'t have to worry about iterating through duplicates as set values are unique.\n\n## Approach\n* Convert the list to set `numSet = set(nums)`.\n* For while loop we can safely assume that if the current maximum possible sequence length >= number of unvisited numbers, we have already calculated the longest possible sequence due to nested loops.\n* So we can keep searching for longest possible sequences until we hit this condition `while maxSeqLen < len(numSet):`.\n* As you visit a number keep deleting them from set, so you don\'t have to check twice `numSet.pop()`. Check consecutive sequence of the number in the set `while longest in numSet:`, delete them as you visit and save the highest number of that sequence `numSet.remove(longest)`.\n* Similarly now you check for the presence of it\'s preceding sequential numbers `while num in numSet:` and find the lowest number of that sequence `numSet.remove(num)`.\n* When you subtract the highest and lowest numbers of a sequence, you get sequence\'s length `longest-num-1`.\n* Update the max `maxSeqLen = max(maxSeqLen, longest-num-1)`, and repeat the steps until your max sequence length >= number of unvisited integers in set (length of set since you deleted visited numbers) `maxSeqLen < len(numSet)`.\n\n## Complexity\n- **Time complexity:**  $$O(n)$$\n  - Conversion of list to set `numSet = set(nums)\n` is linear time *O(n)*.\n  - In worst case scenario where each element in `nums` is unique and doesn\'t have any sequences, each number is only visited once, which is also linear time *O(n)*. \n  - Ignore the constants and you get ***O(n)** where, n = length of list*.\n\n- **Space complexity:** $$O(n)$$\n  - `numSet` requires space, which is ***O(n)** where, n = number of unique numbers in list*.\n\n---\n# 2. Java or JavaScript\n\n## Intuition\n\n* The key idea is to efficiently identify and track consecutive sequences within the given numbers.\n* While Python leverages a set for efficient membership checks, Java and JavaScript adopt a sorting-based approach to achieve similar efficiency.\n\n## Approach\n##### 1. Sort the Input:\n   * Arrange the numbers in ascending order using either `Arrays.sort(nums);` in Java or `nums.sort((a,b) => a-b)` in JavaScript.\n   * This arrangement brings consecutive numbers together, making them easier to detect.\n##### 2. Iterate and Track Sequences:\n   * Iterate through the sorted numbers `for (... ) `, keeping track of:\n     - The current number being examined `num`.\n     - The current sequence length `seq`.\n     - The maximum sequence length found so far `maxSeq`.\n   * During iteration:\n     - If the current number is one more than the previous number `if (prev + 1 == num) ` , increment the sequence length `seq++`.\n     - Otherwise, check if it\'s a duplicate and if it\'s not `else if (prev != num)`, reset the sequence length to 1 `seq = 1`.\n     - Update the maximum sequence length if the current sequence length exceeds it `maxSeq = Math.max(maxSeq, seq)`.\n\n## Complexity\n\n- **Time Complexity:** $$O(n log n)$$\n\n  - Sorting the input array takes *O(n log n)* time.\n  - The single traversal through the sorted array takes O(n) time.\n\n  - Overall, the time complexity is dominated by sorting, resulting in O(n log n).\n- **Space Complexity:** $$O(1)$$\n\n  - The algorithm only uses a constant amount of extra space to store variables, regardless of the input size.\n---\n\n# Code\n\n```python []\nclass Solution:\n    def longestConsecutive(self, nums: List[int]) -> int:\n        numSet = set(nums)\n        maxSeqLen = 0\n        while maxSeqLen < len(numSet):\n            num = numSet.pop()\n            longest = num+1\n            while longest in numSet:\n                numSet.remove(longest)\n                longest += 1\n            num = num-1\n            while num in numSet:\n                numSet.remove(num)\n                num -= 1\n            maxSeqLen = max(maxSeqLen, longest-num-1)\n        return maxSeqLen\n            \n```\n```javascript []\nvar longestConsecutive = function(nums) {\n    if (!nums.length) return 0\n    nums.sort((a,b) => a-b)\n    let prev = nums[0]\n    let seq = 1\n    let maxSeq = 1\n    for (let num of nums) {\n        if ( prev + 1 === num ) {\n            seq++\n            maxSeq = Math.max(maxSeq, seq)\n        } else if (prev !== num) {\n            seq = 1\n        }\n        prev = num\n    }\n    return maxSeq\n};\n```\n```java []\nclass Solution {\n    public int longestConsecutive(int[] nums) {\n        if (nums.length == 0) return 0;\n        Arrays.sort(nums);\n        int prev = nums[0];\n        int seq = 1;\n        int maxSeq = 1;\n        for (int num : nums) {\n            if (prev + 1 == num) {\n                seq++;\n                maxSeq = Math.max(maxSeq, seq);\n            }  else if (prev != num) {\n                seq = 1;\n            }\n            prev = num;\n        }\n        return maxSeq;\n    }\n}\n```\nThese codes are faster Python by *97%*, JavaScript by *99.5%*, Java by *95%* approx respectively but...\n\n### If you want to beat 100% with python...\n\n```python []\ndef longestConsecutive(nums):\n    nums = set(nums)\n    maxSeq = 0\n    while maxSeq < len(nums):\n        num = nums.pop()\n        maxn = num+1\n        while maxn in nums:\n            nums.remove(maxn)\n            maxn += 1\n        num = num-1\n        while num in nums:\n            nums.remove(num)\n            num-=1\n        maxSeq = max(maxSeq, maxn-num-1)\n    return maxSeq\n            \nwith open(\'user.out\', \'w\') as f:\n    for case in map(loads, stdin):\n        f.write(f"{longestConsecutive(case)}\\n")\nexit(0)\n```\n---\n\n# Proofs\n![Screenshot 2024-01-18 104555.png](https://assets.leetcode.com/users/images/2091f65c-bec2-4228-91f5-e598cf48587c_1705604388.0152986.png)\n\n![jsproof.png](https://assets.leetcode.com/users/images/61d3ca8c-e485-4cd6-b3e0-008ef314468c_1705691001.615249.png)\n\n![javaProof.png](https://assets.leetcode.com/users/images/6ec971f6-22db-497d-8550-6e3941517311_1705695478.554098.png)\n\n
['Array', 'Python', 'Java', 'Python3', 'JavaScript']