Hashing: Longest consecutive sequence

Problem Statement:

You are given an array, you need to find the length of the longest sub sequence

Example:

Input: [2, 1, 3, 4, 9, 5, 6]
Output: 6

The longest sub sequence is [2, 1, 3, 4, 5, 6]

Solution 1:Bruteforce approach

Sort the array and then check if the numbers are incremented sequentially.

Time Complexity: O(n logn)
Space Complexity: O(1)

Solution 2: Efficient approach

We will use hashing approach.

Insert all the elements into hash set.

Then iterate through the set and for each number num, check if num-1 present in the set.

if not, then the num will start of the sequence.

Then Initialize current_num = num, then increment the sequence.

Then return the max sequence

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_set>
using namespace std;


int solution_1 (vector<int> arr) {

    if (arr.empty()) 
    	return 0;

    sort(arr.begin(), arr.end());
  
    int result = 1;
    int count = 1;
  
    for (int i = 1; i < arr.size(); i++) {
      	
      	//case 1: if the element is duplicate of previous element,
      	//        skip it
        if (arr[i] == arr[i-1]) 
            continue;

        //case 2: if current element is the next element
        //        increment the count
        if (arr[i] == arr[i - 1] + 1) {
            count++;
        } 
        else {
        //case 3: if the current element is greater than the previous element, reset the count
            count = 1;
        }

        result = max(result, count);
    }
    return result;
}

int solution_2(vector<int> nums)
{
    unordered_set<int> st(nums.begin(), nums.end());
    
    int max_size = 0;

    for (int num : st) {
        if (st.find(num - 1) == st.end()) {
            int current_num = num;
            int current_size = 1;

            while (st.find(current_num + 1) != st.end()) {
                current_num++;
                current_size++;
            }

            max_size = max(max_size, current_size);
        }
    }

    return max_size;

}

int main() {
    vector<int> arr = {2, 1, 3, 4, 9, 5, 6};
    cout << solution_1(arr)<<endl;
    cout << solution_2(arr);
    return 0;
}

Output

6
6