हिन्दी flagहिन्दी  
MENU

Suggested:

🛠️ Settings

Problem Statement

Given an array nums of n integers, return the length of the longest sequence of consecutive integers. The integers in this sequence can appear in any order.

Examples

Example 1:

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

Explanation: The longest sequence of consecutive elements in the array is [1, 2, 3, 4], which has a length of 4.
Example 2:

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9

Explanation: The longest sequence of consecutive elements in the array is [0, 1, 2, 3, 4, 5, 6, 7, 8], which has a length of 9.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Make use of linear search, for each number x in the array, we will check if the next numbers like x + 1, x + 2, x + 3, and so on, are also in the array and maintain a counter.

Approach:

  1. As you iterate through each number in the array, begin by checking if consecutive numbers like ( x+1, x+2, x+3 ), and so on, exist in the array. The occurrence of the next consecutive number can be checked by using linear search.
  2. When you find consecutive numbers, start counting them using a counter. Increment this counter each time you find the next consecutive number in the sequence.
  3. This counter effectively keeps track of how long the current consecutive sequence is as you move through the array and find more consecutive numbers.

Code:


#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Helper function to perform linear search
    bool linearSearch(vector<int>& a, int num) {
        int n = a.size(); 
        // Traverse through the array 
        for (int i = 0; i < n; i++) {
            if (a[i] == num)
                return true;
        }
        return false;
    }

public:
    // Function to find the longest consecutive sequence
    int longestConsecutive(vector<int>& nums) {
        // If the array is empty
        if (nums.size() == 0) {
            return 0;
        }
        int n = nums.size();
        // Initialize the longest sequence length
        int longest = 1; 

        // Iterate through each element in the array
        for (int i = 0; i < n; i++) {
            // Current element
            int x = nums[i]; 
            // Count of the current sequence
            int cnt = 1; 

            // Search for consecutive numbers
            while (linearSearch(nums, x + 1) == true) {
                // Move to the next number in the sequence
                x += 1; 
                // Increment the count of the sequence
                cnt += 1; 
            }

            // Update the longest sequence length found so far
            longest = max(longest, cnt);
        }
        return longest;
    }
};

int main() {
    vector<int> a = {100, 4, 200, 1, 3, 2};

    // Create an instance of the Solution class
    Solution solution;

    // Function call for longest consecutive sequence
    int ans = solution.longestConsecutive(a);
    cout << "The longest consecutive sequence is " << ans << "\n"; 
    return 0;
}

Complexity Analysis:

  • Time Complexity: O(n^2), where n is the size of given array.
    • Since we are using nested loops each running for approximately n times. The outer loop traverses for finding the consecutive sequence of every element and the inner loop works for checking if the next value exists in the array or not.
  • Space Complexity: O(1)

2️⃣  Better Approach (Sorting)

Approach:

  1. Sort the Array: By sorting the array, consecutive numbers will be placed next to each other. This will help in easily detecting the longest sequence of consecutive numbers.
  2. Iterate Through the Array: After sorting, iterate through the array and compare each element with the next one. If two consecutive elements are the same or differ by more than 1, reset the current streak of consecutive numbers. If they differ by 1, continue counting the streak.
  3. Track the Maximum Length: During the iteration, maintain the current length of the consecutive sequence and the maximum length found.

Code:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;

        // Sort the array
        sort(nums.begin(), nums.end());

        // Variables to track the longest streak
        int maxLength = 1, currentLength = 1;

        // Iterate through the sorted array to find the longest consecutive sequence
        for (int i = 1; i < nums.size(); i++) {
            // If current number is the same as the previous number, skip it
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            // If the current number is consecutive to the previous number
            if (nums[i] == nums[i - 1] + 1) {
                currentLength++;
            } else {
                // Reset the streak
                maxLength = max(maxLength, currentLength);
                currentLength = 1; // Reset for new sequence
            }
        }

        // After the loop, check the last streak
        maxLength = max(maxLength, currentLength);
        
        return maxLength;
    }
};

Explanation:

  1. Sorting: We first sort the array in ascending order. This allows consecutive numbers to be adjacent in the sorted array.
  2. Iterating Through the Sorted Array:
    • We iterate through the sorted array from the second element to the last.
    • For each element, check if it is the same as the previous element (to avoid duplicates) or if it is one more than the previous element. If it's one more, it means we are still in a consecutive sequence, so we increment the current sequence length.
    • If the current element is not consecutive to the previous one, we compare the current sequence length with the maximum length found so far, update maxLength if necessary, and reset the current sequence length.
  3. Final Update: After the loop, we need to check if the last sequence we were counting was the longest one. Therefore, we do a final comparison to update maxLength.

Complexity Analysis:

  • Time Complexity: O(n log n) + O(n)
    • Sorting the array takes O(n log n) time
    • Iterating through the array takes O(n) time.
  • Space Complexity: O(1)

3️⃣ HashSet

Intuition:

  1. Insert all elements into a HashSet: This allows us to check for the presence of any element in constant time, O(1).
  2. Iterate through each number in the array:
    • For each number, check if it is the start of a sequence. This is true if the number-1 is not in the set.
    • If it’s the start of a sequence, count the length of the consecutive sequence starting from this number by checking if num + 1, num + 2, etc., exist in the set.
  3. Update the maximum sequence length as you go.

Algorithm:

  1. Insert all elements in the array into a HashSet.
  2. For each element, check if it's the start of a sequence.
  3. Count the length of the consecutive sequence starting from that element.
  4. Track the maximum length encountered.

Dry Run:

       +-----+-----+-----+-----+-----+-----+
nums = | 100 |  4  | 200 |  1  |  3  |  2  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
Step 1: Insert elements into the unordered_set:
       +-----+-----+-----+-----+-----+-----+
nums = | 100 |  4  | 200 |  1  |  3  |  2  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5

longestCount = 0

unordered_set
 +-----+
 | 100 |
 +-----+
 |  4  |
 +-----+
 | 200 |
 +-----+
 |  1  |
 +-----+
 |  3  |
 +-----+
 |  2  |
 +-----+
Iterate through the nums:
       +-----+-----+-----+-----+-----+-----+
nums = | 100 |  4  | 200 |  1  |  3  |  2  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^
          |
          i

unordered_set
 +-----+
 | 100 |
 +-----+
 |  4  |
 +-----+
 | 200 |
 +-----+
 |  1  |
 +-----+
 |  3  |
 +-----+
 |  2  |
 +-----+
 
longestCount = 0
 
Iteration 1: i = 0
    Check if it is the starting point by finding
    the nums[i] - 1 exist in the set or not.
    nums[0] - 1
    100 - 1
    99, does not exist in the set.
    
         Set currentStreak = 1
         Look for the next item in the set
         Does nums[i] + 1, exist
         nums[0] + 1
         100 + 1
         101, does not exist,
         means streak is broken
         
         Update longestCount with the max of
         longestCount and currentStreak.
         longestCount = max(longestCount, currentStreak)
                      = max(0, 1)
                      = 1
Iteration 2: i = 1

       +-----+-----+-----+-----+-----+-----+
nums = | 100 |  4  | 200 |  1  |  3  |  2  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                ^
                |
                i
longestCount = 1

unordered_set
 +-----+
 | 100 |
 +-----+
 |  4  |
 +-----+
 | 200 |
 +-----+
 |  1  |
 +-----+
 |  3  |
 +-----+
 |  2  |
 +-----+
 
    Check nums[i] if it is the starting point by
    finding the nums[i] - 1 exist in the set or not.
    nums[1] - 1
    4 - 1
    3, does exist in the set.
Iteration 3: i = 2

       +-----+-----+-----+-----+-----+-----+
nums = | 100 |  4  | 200 |  1  |  3  |  2  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                      ^
                      |
                      i
longestCount = 1

unordered_set
 +-----+
 | 100 |
 +-----+
 |  4  |
 +-----+
 | 200 |
 +-----+
 |  1  |
 +-----+
 |  3  |
 +-----+
 |  2  |
 +-----+
 
    Check nums[i] if it is the starting point by
    finding the nums[i] - 1 exist in the set or not.
    nums[2] - 1
    200 - 1
    199, does not exist in the set.
    means it is the starting of new streak.
         Set currentStreak = 1
         Look for the next item in the set
         Does nums[i] + 1, exist
         nums[2] + 1
         200 + 1
         201, does not exist,
         means streak is broken
         
         Update longestCount with the max of
         longestCount and currentStreak.
         longestCount = max(longestCount, currentStreak)
                      = max(1, 1)
                      = 1
Iteration 4: i = 3

       +-----+-----+-----+-----+-----+-----+
nums = | 100 |  4  | 200 |  1  |  3  |  2  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                            ^
                            |
                            i
longestCount = 1

unordered_set
 +-----+
 | 100 |
 +-----+
 |  4  |
 +-----+
 | 200 |
 +-----+
 |  1  |
 +-----+
 |  3  |
 +-----+
 |  2  |
 +-----+
 
    Check nums[i] if it is the starting point by
    finding the nums[i] - 1 exist in the set or not.
    nums[3] - 1
    1 - 1
    0, does not exist in the set.
    means it is the starting of new streak.
         Set currentStreak = 1
         Look for the next item in the set
         Does nums[i] + 1, exist
         nums[3] + 1
         1 + 1
         2, does exist,
              increment currentStreak and look 
              for next number in set.
              currentStreak = 2
              nextNumber = 3
         3, does exist,
              increment currentStreak and look
              for next number in set.
              currentStreak = 3
              nextNumber = 4
         4, does exist,
              increment currentStreak and look
              for next number in set
              currentStreak = 4
              nextNumber = 5
         5, does not exist
         means the streak is broken.
         Update longestCount with the max of
         longestCount and currentStreak.
         longestCount = max(longestCount, currentStreak)
                      = max(1, 4)
                      = 4
Iteration 5: i = 4

       +-----+-----+-----+-----+-----+-----+
nums = | 100 |  4  | 200 |  1  |  3  |  2  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                                  ^
                                  |
                                  i
longestCount = 4

unordered_set
 +-----+
 | 100 |
 +-----+
 |  4  |
 +-----+
 | 200 |
 +-----+
 |  1  |
 +-----+
 |  3  |
 +-----+
 |  2  |
 +-----+
 
    Check nums[i] if it is the starting point by
    finding the nums[i] - 1 exist in the set or not.
    nums[4] - 1
    3 - 1
    2, does exist in the set.
Iteration 6: i = 5

       +-----+-----+-----+-----+-----+-----+
nums = | 100 |  4  | 200 |  1  |  3  |  2  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                                        ^
                                        |
                                        i
longestCount = 4

unordered_set
 +-----+
 | 100 |
 +-----+
 |  4  |
 +-----+
 | 200 |
 +-----+
 |  1  |
 +-----+
 |  3  |
 +-----+
 |  2  |
 +-----+
 
    Check nums[i] if it is the starting point by
    finding the nums[i] - 1 exist in the set or not.
    nums[5] - 1
    2 - 1
    1, does exist in the set.
Return the longestCount, which would contain the longest sequence.

Code:

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

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        unordered_set<int> numSet(nums.begin(), nums.end());
        int longestSeq = 0;
        
        for (int num : nums) {
            // If it's the start of a sequence
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;
                int currentStreak = 1;
                
                // Count the consecutive sequence starting from `num`
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum++;
                    currentStreak++;
                }
                
                // Update longest sequence length
                longestSeq = max(longestSeq, currentStreak);
            }
        }
        
        return longestSeq;
    }
};

// Example usage
int main() {
    Solution solution;
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    cout << "Longest Consecutive Sequence Length: " << solution.longestConsecutive(nums) << endl;
    return 0;
}

Complexity Analysis:

  • Time Complexity: O(n)+(2*n) = O(3*n), where n is the size of the array.
    • The function takes O(N) to insert all elements into the set data structure. After that, for every starting element, we find the consecutive elements. Although nested loops are used, the set will be traversed at most twice in the worst case. Therefore, the time complexity is O(2xn) instead of O(n^2).
  • Space Complexity: O(n)
    • As we store array elements in the set data structure.

Your experience on this site will be improved by allowing cookies Cookie Policy