POTD #11 - Longest Consecutive Subsequence | Geeks For Geeks

{% raw %}

Problem Statement

Geeks For Geeks – https://www.geeksforgeeks.org/problems/longest-consecutive-subsequence2449/1

Given an array arr[] 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.

Input: arr[] = [2, 6, 1, 9, 4, 5, 3]Output: 6Explanation: The consecutive numbers here are 1, 2, 3, 4, 5, 6. These 6 numbers form the longest consecutive subsquence.

Input: arr[] = [1, 9, 3, 10, 4, 20, 2]Output: 4Explanation: 1, 2, 3, 4 is the longest consecutive subsequence.

My Approach

1. Sort the array.Initialize two variables:

• max_sequence to 1 (to store the length of the longest consecutive subsequence).
• cont_sub_sequence to 1 (to track the current consecutive subsequence length).

2. Loop through the array starting from the second element:

• If the current element is equal to the previous one, skip it (handle duplicates).
• Else, if the difference between the current and previous element is 1:
  • Increment cont_sub_sequence by 1.
• Otherwise:
  • Update max_sequence as the maximum of max_sequence and cont_sub_sequence.
  • Reset cont_sub_sequence to 1.

3. After the loop, update max_sequence one final time as the maximum of max_sequence and cont_sub_sequence.

4. Return max_sequence.

class Solution:        # arr[] : the input array        #Function to return length of longest subsequence of consecutive integers.    def longestConsecutive(self,arr):        #code here        arr.sort()        max_sequence = 1        cont_sub_sequence = 1        for itr in range(1, len(arr)):            if arr[itr] == arr[itr-1]:                continue            elif arr[itr] - arr[itr-1] == 1:                cont_sub_sequence += 1            else:                if cont_sub_sequence > max_sequence:                    max_sequence = cont_sub_sequence                cont_sub_sequence = 1                if cont_sub_sequence > max_sequence:            max_sequence = cont_sub_sequence        return max_sequence

{% endraw %}