Accepted simple and easy to understand Python O(nlgn) solution


  • 1

    Sort the array and count the longest consecutive subarray (without double counting duplicates). It's slower than the O(n) solutions here but it's simple to reason about (:

    class Solution(object):
        def longestConsecutive(self, arr):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(arr) <= 1:
                return len(arr)
    
            sorted_arr = sorted(arr)
            longest = 0
            curr = 1
    
            for i in range(len(sorted_arr)-1):
                diff = sorted_arr[i+1] - sorted_arr[i]
                if diff == 1:
                    curr += 1
                elif diff != 0:
                    curr = 1
                longest = max(longest, curr)
    
            return longest
    

Log in to reply
 

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