Posts Longest consecutive subsequence (geeksforgeeks - SDE Sheet)
Post
Cancel

Longest consecutive subsequence (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given an array of non-negative integers. Find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.

geeksforgeeks

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
    class Solution
    {
    // arr[] : the input array
    // N : size of the array arr[]

    //Function to return length of longest subsequence of consecutive integers.
    static int findLongestConseqSubseq(int arr[], int n)
    {

        int maxLength = 0;

        Set<Integer> set = new HashSet<>();

        for(Integer x: arr){
            set.add(x);
        }

        for(int i=0; i<n; i++){

            // MAIN OPTIMIZATION:
            // x = arr[i]
            // if array contains x-1,
            // the longest sequence cannot start from x
            // we will start counting only if we get the starting position
            if(set.contains(arr[i]-1))
            continue;

            int len = 0;
            int current = arr[i];

            while(set.contains(current)){
                len++;
                current++;
            }

            maxLength = Math.max(maxLength, len);

        }

        return maxLength;

    }
    }
This post is licensed under CC BY 4.0 by the author.