Longest Consecutive Sequence in Linear time

Posted in

Longest Consecutive Sequence in Linear time
vinaykhatri

Vinay Khatri
Last updated on March 29, 2024

    Problem

    Given an array of integers. Find the length of the longest possible sequence from the array such that the integers of the sequence are consecutive integers. Recall that a “sequence” does not need to contain array of elements adjacent to each other.

    Sample Input

    [1, 3, 4, 7, 2, 9]

    Sample Output

    4

    Explanation

    Below are the consecutive integers that we picked up from the array [1, 3, 4, 7, 2, 9] [1, 3, 4, 2]. As you can see, these integers are consecutive

    Approach

    We can use hash sets to solve this problem. For each element that is the starting point of the sequence, we will traverse the sequence until we find the consecutive integers. Below are the steps of the algorithm involved in this solution.

    1. We first traverse the given array and insert each element into an unordered set.
    2. We again traverse the array, and for each element, check if this is the starting element. For this, we just check if arr[i]-1 is present in the set. If arr[i]-1 is not present, it means this is the starting element of the array.
    3. From this starting element, we keep incrementing the value until the value is not present in the set. If we find that the current value is not present, we update the answer.

    Complexity Analysis

    The time complexity is O(N), and the space complexity is also O(N) due to the set.

    C++ Programming

    #include <bits/stdc++.h>
    using namespace std;
    
    int solve(int arr[], int n)
    {
        unordered_set<int> s;
        int ans = 0;
    
        // insert the elements
        for (int i = 0; i < n; i++)
            s.insert(arr[i]);
    
        // traverse the array
        for (int i = 0; i < n; i++)
        {
            // if current element is the starting
            // element of a sequence
            if (s.find(arr[i] - 1) == s.end())
            {
                // Then check for next elements
                // in the sequence
                int j = arr[i];
    
                while (s.find(j) != s.end())
                    j++;
    
                // update the answer
                ans = max(ans, j - arr[i]);
            }
        }
        return ans;
    }
    
    int main()
    
    {
        int arr[] = {1, 3, 4, 7, 2, 9};
        int n = sizeof arr / sizeof arr[0];
        cout << solve(arr, n);
    
        return 0;
    }

    Output

    4

    Java Programming

    import java.io.*;
    import java.util.*;
    
    class Solution {
        static int solve(int arr[], int n)
        {
            HashSet<Integer> s = new HashSet<Integer>();
            int ans = 0;
    
            // insert all the elements
            for (int i = 0; i < n; ++i)
                s.add(arr[i]);
    
            // traverse the array
            for (int i = 0; i < n; ++i)
            {
                // if current element is the starting
                // element of a sequence
                if (!s.contains(arr[i] - 1))
                {
                    // check for next elements
                    // in the sequence
                    int j = arr[i];
                    while (s.contains(j))
                        j++;
    
                    // update the answer
                    if (ans < j - arr[i])
                        ans = j - arr[i];
                }
            }
    
            return ans;
        }
    
        public static void main(String args[])
        {
            int arr[] = {1, 3, 4, 7, 2, 9};
            int n = arr.length;
    
            System.out.println(solve(arr, n));
        }
    }

    Output

    4

    Python Programming

    def solve(arr, n):
        s = set()
        ans = 0
    
        # insert the elements
        for e in arr:
            s.add(e)
    
        # traverse the array
        for i in range(n):
            # if current element is the starting
            # element of a sequence
            if (arr[i]-1) not in s:
                # check for next elements in the sequence
                j = arr[i]
                while(j in s):
                    j += 1
    
                # update the answer
                ans = max(ans, j-arr[i])
        return ans
    
    
    n = 6
    arr = [1, 3, 4, 7, 2, 9]
    print(solve(arr, n))

    Output

    4

    People are also reading:

    Leave a Comment on this Post

    0 Comments