Longest Successive Elements

public static int longestSuccessiveElements(int []a) {

        // Write your code here.

        int n=a.length;

        Arrays.sort(a);

        int ans=a[0];

        int cnt=1;

        int res=1;

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

            if (a[i]==ans) {

                continue;

            }

            else if (a[i]==ans+1) {

                ans=a[i];

                cnt++;

                res=Math.max(res, cnt);

            }

            else if (a[i]!=ans+1){

               ans=a[i];

               cnt=1;

               res=Math.max(res, cnt);

            }

        }

        return res;

    }

int longestSuccessiveElements(vector<int>&a) {

   int cnt = 1;

   int n = a.size();

   int prev = -1;

   sort(a.begin(),a.end());

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

       //skip the duplicate

       if(a[i]==a[i+1])

       continue;

       else{

       int diff = a[i+1] - a[i];

        if(diff == 1){

            cnt++;

            if(cnt>prev)

            prev=cnt;

        }

        if(diff!=1){

            cnt=1;

        }

   }

   }

   return prev;

}

int longestSuccessiveElements(vector<int>&a) {
    // Write your code here.
    sort(a.begin(),a.end());
    int n=a.size(),longest =1, count=0, lastSmaller=INT_MIN ;
    for (int i=0;i<n;i++){
        if(a[i]-1 == lastSmaller){
            count++;
            lastSmaller=a[i];
        }
        else if(lastSmaller != a[i]){
            count=1; //reset
            lastSmaller=a[i];
        }
        longest = max(longest,count);
    }
    return longest;

}

Initialize Variables:

• longest: This variable stores the length of the longest consecutive sequence found. It starts at 1 since the shortest sequence possible has at least one element.

Create a HashSet:

• A HashSet named s is used to store all elements of the array a.
• We loop through each element i in a and add it to the set s. This will allow us to perform quick look-ups to check for the presence of elements.

Find the Start of Consecutive Sequences:

• We loop through each element j in the array a again:
  • Check if j is the start of a sequence:
    • If j - 1 is not in the set s (!s.contains(j - 1)), then j is the smallest element of a potential consecutive sequence.
  • Count the Length of the Consecutive Sequence:
    • Start a counter count at 1 to represent the current sequence length.
    • Use a variable x initialized to j to find the next consecutive numbers.
    • While x + 1 exists in the set s, increment count and x. This means you have found consecutive numbers following j.
  • Update the Longest Length:
    • After counting the current consecutive sequence, update longest to the maximum of its current value or count.

Return the Result:

• After completing the loop, longest will contain the length of the longest consecutive sequence found.

The problem requires finding the length of the longest consecutive elements sequence in an unsorted array. The first thought might be to sort the array since consecutive numbers will appear next to each other in a sorted array. This makes it easier to identify and count the length of consecutive sequences.

Sort the Array:

• Sorting the array ensures that any consecutive sequence of numbers appears in a contiguous segment.

Initialize Variables:

• Use longest to keep track of the maximum length of consecutive sequences found.
• Use count to count the length of the current consecutive sequence.
• Use prev_min to remember the last number in the current consecutive sequence.

Iterate Through the Sorted Array:

• Traverse the array from the start:
  • If the current number nums[i] is exactly one more than prev_min (i.e., nums[i] - 1 == prev_min), it continues the current sequence:
    • Increment count.
    • Update prev_min to the current number.
  • Else if the current number is not equal to prev_min (to avoid duplicates) and does not continue the sequence:
    • Reset count to 1 (starting a new sequence).
    • Update prev_min to the current number.
• Update longest to be the maximum of its current value or the value of count after each iteration.

Return the Result:

• The value of longest will be the length of the longest consecutive sequence.

Example: Input: nums = [100, 4, 200, 1, 3, 2]

Step-by-Step:

Sort the Array:

• nums becomes [1, 2, 3, 4, 100, 200]

Initialize Variables:

• longest = 0
• count = 0
• prev_min = Integer.MIN_VALUE

Iterate Through the Sorted Array:

i = 0:

• nums[i] = 1, and prev_min = Integer.MIN_VALUE
• Since nums[i] != prev_min, start a new sequence:
  • count = 1, prev_min = 1
• Update longest = 1.

i = 1:

• nums[i] = 2, and prev_min = 1
• nums[i] - 1 == prev_min → Continues the sequence:
  • count = 2, prev_min = 2
• Update longest = 2.

i = 2:

• nums[i] = 3, and prev_min = 2
• nums[i] - 1 == prev_min → Continues the sequence:
  • count = 3, prev_min = 3
• Update longest = 3.

i = 3:

• nums[i] = 4, and prev_min = 3
• nums[i] - 1 == prev_min → Continues the sequence:
  • count = 4, prev_min = 4
• Update longest = 4.

i = 4:

• nums[i] = 100, and prev_min = 4
• nums[i] != prev_min + 1 → Sequence breaks:
  • count = 1, prev_min = 100
• No update to longest since it is greater than count.

i = 5:

• nums[i] = 200, and prev_min = 100
• nums[i] != prev_min + 1 → Sequence breaks:
  • count = 1, prev_min = 200
• No update to longest since it is greater than count.

import java.util.*;

public class Solution {

    public static int longestSuccessiveElements(int []a) {

        // Write your code here.

         int n = a.length;

        if (n == 0)

            return 0;

        int longest = 1;

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

        // put all the array elements into set

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

            set.add(a[i]);

        }

        // Find the longest sequence

        for (int it : set) {

            // if 'it' is a starting number

            if (!set.contains(it - 1)) {

                // find consecutive numbers

                int cnt = 1;

                int x = it;

                while (set.contains(x + 1)) {

                    x = x + 1;

                    cnt = cnt + 1;

                }

                longest = Math.max(longest, cnt);

            }

        }

        return longest;

    }

     public static void main(String[] args) {

        int[] a = {100, 200, 1, 2, 3, 4};

        int ans = longestSuccessiveElements(a);

        System.out.println("The longest consecutive sequence is " + ans);

    }

}

int longestSuccessiveElements(vector<int>&a) {

    // Write your code here.

    sort(a.begin(),a.end());

    int count=1;

    int maxi=0;

    for(int i=1;i<a.size();i++){

        if(a[i]-a[i-1] == 0)continue;

        if(a[i]-a[i-1] == 1) {

            count++;

            maxi = max(maxi,count);

        }

        else {

            count = 1;

        }

    }

    return maxi;

}

def longestSuccessiveElements(a : List[int]) -> int:

    n=len(a)

    cnt=1

    maxcnt=0

    a.sort()

    for i in range(n-1):

        if a[i]+1==a[i+1]:

            cnt+=1

            maxcnt=max(maxcnt,cnt)

        else:

            if a[i]==a[i+1]:

                continue

            else:

                cnt=1

    return maxcnt

Approach: What it does:

• Sorts the array.
• Uses a single loop to iterate through the sorted array and keep track of the length of consecutive sequences.

Complexity:

• Time Complexity: O(n log n) due to sorting, followed by O(n) for the single pass through the array.
• Space Complexity: O(1) additional space.

Code:

 int longestSuccessiveElements(vector<int>&a) {

    // Write your code here.

    if (a.empty()) return 0; 

    sort(a.begin(), a.end());

    int ans = 1; 

    int curr = 1;

    for (int i = 1; i < a.size(); ++i) {

        if (a[i] == a[i - 1]) {

            continue;

        } else if (a[i] == a[i - 1] + 1) {

            curr++;

        } else {

            curr = 1;

        }

        ans = max(ans, curr);

    }

    return ans;

}

int longestSuccessiveElements(vector<int>&a) {

    // Write your code here.

    int ans=1, curr=1;

    sort(a.begin(), a.end());

    for(int i=0; i<a.size()-1; i++){

        // bool flag = true;

        // if(a[i+1]-a[i] != 1){

        //     flag = false;

        // }

        // curr += 1;

        // int temp=curr;

        // if(flag == false){

        //     curr = 1;

        // }

        // ans = max(curr, ans);

        // bool flag = true;

        if(a[i+1]-a[i] == 1){

            curr += 1;

        }

        else if (a[i+1]-a[i] == 0){

            curr = curr;

        }

        else{

            // flag = false;

            curr = 1;

        }

        ans = max(curr, ans);

    }

    return ans;

}