Longest Consecutive Sequence

• Initialize a variable maxLength to 0.\n- For each number num in the input array nums:\n - Initialize currentNum = num and currentLength = 1.\n - Start a loop:\n - Check if currentNum + 1 exists in the nums array by performing a linear scan.\n - If it exists, increment currentLength, update currentNum to currentNum + 1, and continue the loop.\n - If it does not exist, break the loop.\n - Update maxLength = max(maxLength, currentLength).\n- After iterating through all numbers, return maxLength.

The brute-force algorithm iterates through every number in the input array nums. For each number num, it assumes it could be the start of a consecutive sequence. It then enters a while loop, checking for the existence of num + 1, num + 2, and so on. The check for existence is performed by another linear scan through the entire array. The length of the current sequence is tracked, and the maximum length found across all possible starting numbers is returned. This method is straightforward to conceptualize but is highly inefficient due to the nested loops and repeated scans.\n\n

1java\nclass Solution {\n    private boolean arrayContains(int[] arr, int num) {\n        for (int i = 0; i < arr.length; i++) {\n            if (arr[i] == num) {\n                return true;\n            }\n        }\n        return false;\n    }\n\n    public int longestConsecutive(int[] nums) {\n        if (nums.length == 0) {\n            return 0;\n        }\n\n        int longestStreak = 0;\n\n        for (int num : nums) {\n            int currentNum = num;\n            int currentStreak = 1;\n\n            while (arrayContains(nums, currentNum + 1)) {\n                currentNum += 1;\n                currentStreak += 1;\n            }\n\n            longestStreak = Math.max(longestStreak, currentStreak);\n        }\n\n        return longestStreak;\n    }\n}\n

• Handle the edge case of an empty array by returning 0.\n- Sort the input array nums.\n- Initialize maxLength = 1 and currentLength = 1.\n- Iterate through the sorted array from the second element (i = 1).\n- If nums[i] is not equal to nums[i-1] (i.e., not a duplicate):\n - Check if nums[i] is equal to nums[i-1] + 1.\n - If it is, increment currentLength.\n - If it's not, the sequence is broken. Update maxLength = max(maxLength, currentLength) and reset currentLength = 1.\n- After the loop finishes, update maxLength one last time: maxLength = max(maxLength, currentLength).\n- Return maxLength.

The core idea is that if the numbers are sorted, we can easily find consecutive sequences by just iterating through the array once. The first step is to sort the input array nums. After sorting, we iterate through the array, keeping track of the current consecutive sequence length (currentLength) and the maximum length found so far (maxLength). We must handle duplicate numbers; if the current number is the same as the previous one, we simply ignore it. If the current number is one greater than the previous number, it extends the sequence, so we increment currentLength. If the sequence is broken (the current number is not one greater than the previous), we update maxLength with the currentLength and reset currentLength to 1 for the new sequence. A final check is needed after the loop to account for the longest sequence being at the end of the array.\n\n

1java\nimport java.util.Arrays;\n\nclass Solution {\n    public int longestConsecutive(int[] nums) {\n        if (nums.length == 0) {\n            return 0;\n        }\n\n        Arrays.sort(nums);\n\n        int longestStreak = 1;\n        int currentStreak = 1;\n\n        for (int i = 1; i < nums.length; i++) {\n            if (nums[i] != nums[i-1]) {\n                if (nums[i] == nums[i-1] + 1) {\n                    currentStreak += 1;\n                } else {\n                    longestStreak = Math.max(longestStreak, currentStreak);\n                    currentStreak = 1;\n                }\n            }\n        }\n\n        return Math.max(longestStreak, currentStreak);\n    }\n}\n

• If the input array is empty, return 0.\n- Create a HashSet and add all elements of nums to it.\n- Initialize maxLength = 0.\n- Iterate through each num in the set.\n- Check if set.contains(num - 1). If it does, num is not the start of a sequence, so continue to the next number.\n- If num - 1 is not in the set, we have found the start of a sequence.\n- Initialize currentNum = num and currentLength = 1.\n- While set.contains(currentNum + 1):\n - Increment currentLength and update currentNum to currentNum + 1.\n- After the while loop, update maxLength = max(maxLength, currentLength).\n- After iterating through all numbers, return maxLength.

This method provides an optimal solution with O(n) time complexity as required by the problem. First, all numbers from the input array are inserted into a HashSet. This allows for checking the presence of a number in average O(1) time. Then, the algorithm iterates through the numbers. For each number num, it performs a crucial check: if num - 1 also exists in the set. If it does, it means num is part of a sequence we have already counted or will count starting from a smaller number, so we skip it. This check is the key to achieving O(n) time complexity, as it ensures we only start building a sequence from its absolute smallest element. If num - 1 is not in the set, we start counting a new sequence. We use a while loop to check for num + 1, num + 2, etc., in the set, incrementing a counter. The maximum length is updated after each full sequence is counted. Although there is a nested loop, each number is visited at most twice, leading to a linear time complexity overall.\n\n

1java\nimport java.util.HashSet;\nimport java.util.Set;\n\nclass Solution {\n    public int longestConsecutive(int[] nums) {\n        if (nums == null || nums.length == 0) {\n            return 0;\n        }\n\n        Set<Integer> numSet = new HashSet<>();\n        for (int num : nums) {\n            numSet.add(num);\n        }\n\n        int longestStreak = 0;\n\n        for (int num : numSet) {\n            // Only start counting if 'num' is the beginning of a sequence\n            if (!numSet.contains(num - 1)) {\n                int currentNum = num;\n                int currentStreak = 1;\n\n                while (numSet.contains(currentNum + 1)) {\n                    currentNum += 1;\n                    currentStreak += 1;\n                }\n\n                longestStreak = Math.max(longestStreak, currentStreak);\n            }\n        }\n\n        return longestStreak;\n    }\n}\n