Geeksforgeeks: Longest Consecutive Subsequence

 Longest Consecutive Subsequence

Difficulty: Medium

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.

Examples:

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.

Input: arr[] = [15, 13, 12, 14, 11, 10, 9]
Output: 7
Explanation: The longest consecutive subsequence is 9, 10, 11, 12, 13, 14, 15, which has a length of 7.

Constraints:
1 <= arr.size() <= 105
0 <= arr[i] <= 105

To solve the problem of finding the length of the longest subsequence of consecutive integers, we can approach it using hashing for efficient lookup.

Approach:

1. Use a Set for Efficient Lookup:

   • First, we can store all elements in a set (or hash table) to allow for O(1) time complexity for checking the presence of elements.

2. Iterate Over the Array:

   • For each element in the array, we check if it is the start of a possible subsequence. If it is, we continue to check for consecutive elements (i.e., element + 1, element + 2, etc.).

3. Track the Maximum Length:

   • For each potential subsequence, we track the length and update the maximum length found.

4. Optimization:

   • Once an element has been part of a subsequence, we can skip further checks for that element by removing it from the set or marking it as visited.

Algorithm:

1. Convert the array into a set to ensure O(1) lookups.
2. For each element, if it is the start of a subsequence (i.e., element - 1 is not in the set), we count the length of the subsequence by checking for element + 1, element + 2, etc.
3. Track the maximum subsequence length during this process.

Code Implementation (C#):

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestConsecutiveSubsequence(int[] arr) {
        HashSet<int> set = new HashSet<int>();
        
        // Add all elements to the set
        foreach (int num in arr) {
            set.Add(num);
        }
        
        int maxLength = 0;
        
        foreach (int num in arr) {
            // Check if it's the start of a subsequence
            if (!set.Contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;
                
                // Count the length of the consecutive subsequence
                while (set.Contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }
                
                // Update the maximum length
                maxLength = Math.Max(maxLength, currentLength);
            }
        }
        
        return maxLength;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();
        
        // Test Case 1
        int[] arr1 = { 2, 6, 1, 9, 4, 5, 3 };
        Console.WriteLine(solution.LongestConsecutiveSubsequence(arr1));  // Output: 6
        
        // Test Case 2
        int[] arr2 = { 1, 9, 3, 10, 4, 20, 2 };
        Console.WriteLine(solution.LongestConsecutiveSubsequence(arr2));  // Output: 4
        
        // Test Case 3
        int[] arr3 = { 15, 13, 12, 14, 11, 10, 9 };
        Console.WriteLine(solution.LongestConsecutiveSubsequence(arr3));  // Output: 7
    }
}

Explanation:

1. Set Creation:

   • We first create a HashSet to store all elements from the input array, ensuring that we can check the presence of elements in O(1) time.

2. Main Loop:

   • For each element num in the array:
     • We check if num - 1 exists in the set. If it doesn't, this means that num is the starting element of a possible subsequence.
     • We then continue to check for consecutive elements (num + 1, num + 2, etc.), counting the length of this subsequence.

3. Tracking Maximum Length:

   • The length of each consecutive subsequence is compared to the current maximum length, and we update the maximum length if a longer subsequence is found.

4. Returning the Result:

   • After all elements are processed, the maximum length of any consecutive subsequence is returned.

Time and Space Complexity:

• Time Complexity:
  • Constructing the set takes $O(n)$, where $n$ is the size of the array.
  • For each element, we may need to check the consecutive numbers. However, each element is processed at most once, making the total time complexity $O(n)$.
• Space Complexity:
  • The space complexity is $O(n)$ due to the set storing all the elements.

Edge Cases:

1. Empty Array:

   • If the array is empty, the result should be 0 because there are no subsequences.

2. All Elements Are Same:

   • If all elements are the same, the longest subsequence is the element itself, with a length of 1.

3. Array with No Consecutive Numbers:

   • If the array contains no consecutive numbers, the longest subsequence will have a length of 1.

Examples:

1. Input: arr = [2, 6, 1, 9, 4, 5, 3]

   • Output: 6 (The longest consecutive subsequence is [1, 2, 3, 4, 5, 6])

2. Input: arr = [1, 9, 3, 10, 4, 20, 2]

   • Output: 4 (The longest consecutive subsequence is [1, 2, 3, 4])

3. Input: arr = [15, 13, 12, 14, 11, 10, 9]

   • Output: 7 (The longest consecutive subsequence is [9, 10, 11, 12, 13, 14, 15])

This solution efficiently finds the longest consecutive subsequence using hashing with a time complexity of $O(n)$, which is well-suited for large input sizes.