Start learning free

LESSON 222 OF 410 · SORTING

Longest Consecutive Sequence in O(n log n) Time Using Java

Practice O(n log n) Read the full explanation

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

Example 1:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: Longest consecutive sequence is [1, 2, 3, 4].
             Therefore its length is 4.

Example 2:

Input: [0, 2, 0, 1, 2, 3, 1]
Output: 4
Explanation: Longest consecutive sequence is [0, 1, 2, 3].
             Therefore its length is 4.
	     Note that we count each value once, even though values 0, 1 and 2 appear 2 times each in nums

Note:

For this lesson, your algorithm should run in O(n log n) time and use O(1) extra space.
(There are faster solutions which we will discuss in future lessons)


Hints:

Let's sort the array in non-decreasing order. In this way each consecutive elements sequence is a subarray of the sorted array. Even more, these consecutive elements subarrays will come one after another.

Let's start by finding the first subarray. Its left endpoint is i = 0. We will use another index variable j to find the right endpoint. j is initially equal to i + 1 and should be incremented for as long as nums[i...j] is a consecutive subarray. But how can we check this?

j is initially equal to i + 1 and will be incremented as long as nums[j] <= nums[j - 1] + 1. When the condition is not satisfied anymore, we have found the first subarray: nums[i...j-1]. How can we find the second one?

The left endpoint of the second subarray is j. So we can set the index i to j. Then we can continuously increment j as long as our condition is satisfied just like we did for the first subarray. When the condition is not satisfied anymore, we have found the second subarray: nums[i...j-1]. Can we use the same strategy for finding the rest of the subarrays?

Yes, we can. We should design an algorithm that repeats this strategy until we are left with no more subarrays (e.g. i >= n, where n is nums.length).
  • 1. Initialize i with 0.
  • 2. While i < n:
    • 1. Initialize j with i + 1.
    • 2. While nums[j] <= nums[j - 1] + 1, increment j
    • 3. Set i to j and return to step 1.

STEP 1 OF 11
    Ctrl + Enter to check

    JAVA · SORTING

    Longest Consecutive Sequence in Java, explained

    Problem Definition

    The problem requires finding the length of the longest consecutive elements sequence in an unsorted array of integers.

    Input:

    • An unsorted array of integers.

    Output:

    • An integer representing the length of the longest consecutive elements sequence.

    Constraints and Assumptions:

    • The array can contain duplicates.
    • The array can have both positive and negative integers.

    Example:

    Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: Longest consecutive sequence is [1, 2, 3, 4]. Therefore its length is 4.

    Understanding the Problem

    The core challenge is to identify the longest sequence of consecutive integers in an unsorted array. This problem is significant in various applications such as data analysis, where identifying trends or patterns in data is crucial.

    Potential pitfalls include handling duplicates and ensuring that the solution is efficient in terms of time complexity.

    Approach

    To solve this problem, we can start with a naive approach and then move to more optimized solutions.

    Naive Solution:

    The naive solution involves sorting the array and then finding the longest consecutive sequence. However, this approach has a time complexity of O(n log n) due to the sorting step.

    Optimized Solution:

    We can optimize the solution by using a set to store the elements and then iterate through the array to find the longest consecutive sequence. This approach can achieve O(n) time complexity, but for this lesson, we will focus on the O(n log n) solution.

    Algorithm

    Here is a step-by-step breakdown of the O(n log n) algorithm:

    1. Sort the array.
    2. Initialize variables to keep track of the longest sequence length and the current sequence length.
    3. Iterate through the sorted array and update the sequence lengths based on consecutive elements.
    4. Return the longest sequence length.

    Code Implementation

    import java.util.Arrays;

public class LongestConsecutiveSequence {
    public static int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // Sort the array
        Arrays.sort(nums);

        int longestStreak = 1;
        int currentStreak = 1;

        for (int i = 1; i < nums.length; i++) {
            // Skip duplicates
            if (nums[i] != nums[i - 1]) {
                // Check if the current number is consecutive
                if (nums[i] == nums[i - 1] + 1) {
                    currentStreak += 1;
                } else {
                    // Update the longest streak
                    longestStreak = Math.max(longestStreak, currentStreak);
                    currentStreak = 1;
                }
            }
        }

        // Return the maximum of the longest streak and the current streak
        return Math.max(longestStreak, currentStreak);
    }

    public static void main(String[] args) {
        int[] nums1 = {100, 4, 200, 1, 3, 2};
        int[] nums2 = {0, 2, 0, 1, 2, 3, 1};

        System.out.println("Longest consecutive sequence length (Example 1): " + longestConsecutive(nums1)); // Output: 4
        System.out.println("Longest consecutive sequence length (Example 2): " + longestConsecutive(nums2)); // Output: 4
    }
}

    Complexity Analysis

    The time complexity of the above solution is O(n log n) due to the sorting step. The space complexity is O(1) as we are not using any extra space that scales with the input size.

    Edge Cases

    Potential edge cases include:

    • Empty array: The output should be 0.
    • Array with one element: The output should be 1.
    • Array with all duplicates: The output should be 1.

    Testing

    To test the solution comprehensively, consider the following test cases:

    • Simple cases with small arrays.
    • Arrays with negative and positive integers.
    • Arrays with duplicates.
    • Large arrays to test performance.

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Understand the problem requirements and constraints thoroughly.
    • Start with a brute-force solution and then optimize.
    • Use sorting and data structures like sets or maps to simplify the problem.
    • Practice similar problems to improve problem-solving skills.

    Conclusion

    In this blog post, we discussed how to find the longest consecutive sequence in an unsorted array of integers using an O(n log n) approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for coding interviews.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free