Syed Jafer K

Its all about Trade-Offs

POTD #11 – Longest Consecutive Subsequence | Geeks For Geeks

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: 6
Explanation: 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: 4
Explanation: 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