NeetCode 150: Longest Consecutive Sequence

Table of contents

The Problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

The Approach

The goal is to get the longest streak of consective elements. Firstly, we need to sort nums, ordering each element sequentially in terms of value. From here, we need to loop over all the elements in nums & keep track of the;

• Current streak.
• Longest streak recorded.

We also need to consider the case where the streak ends on the last element in nums, thus a final checker needs to be applied at the end of the loop.

My Solution

class Solution {
    public int longestConsecutive(int[] nums) {
        // Return 0 if nums is empty.
        if (nums.length == 0) {
            return 0;
        }
        // Sort the array.
        Arrays.sort(nums);

        int consecutiveCounter = 1;
        int longestConsecutiveValue = 0;
        // Iterate over nums in pairs & determine the difference.
        // There are 4 possible scenarios:
        // 1) Same value: continue
        // 2) Consecutive: increase consecutiveCounter by 1
        // 3) Not consecutive : Check if currentCounter > longestConsecutiveValue, and update it if 
        //    necessary. Reset currentCounter to 1.
        for (int i = 0; i < (nums.length - 1); i++) {
            int difference = (nums[i + 1]) - (nums[i]);

            if (difference == 0) {
                continue;
            } else if (difference == 1) {
                consecutiveCounter++;
            } else {
                longestConsecutiveValue = getGreaterValue(consecutiveCounter, longestConsecutiveValue);
                consecutiveCounter = 1;
            }
        }
        // Check for scenario of max streak ending with final pair.
        longestConsecutiveValue = getGreaterValue(consecutiveCounter, longestConsecutiveValue);
        
        return longestConsecutiveValue;
    }

    // Returns the greater value.
    private int getGreaterValue(int a, int b) {
        if (a > b) {
            return a;
        } else {
            return b;
        }
    }
}

Firstly, we sort nums.

We then initialize two variables;

• consecutiveCounter: Tracks the current streak.
• longestConsecutiveValue: Tracks the longest streak recorded.

We then loop over every element in nums, checking if the element succeeding it is consecutive. For each “pair” in this loop there are 4 scenarios;

• difference == 0: nums[i + 1] & nums[i] are the same number & no change is made to consecutiveCounter.
• difference == 0: nums[i + 1] & nums[i] are consecutive elements & consecutiveCounter is increased by 1.
• difference is not 0 or 1: Streak has ended, check if it is greater than the longest recorded streak, longestConsecutiveValue & reset consecutiveCounter to 1.

After the loop, we then add the final checker for the case if the streak ends on the final element.

longestConsecutiveValue is then returned.