LeetCode: Longest Consecutive Sequence

Challenge description

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Naive Solution: Use set to check consecutive elements

We use a set to check whether one element exists in array. Iterate all the elements and try to find the longest sub-array in the loop.

But the overall time complexity is O(N^2), which will time-limited.

class Solution {
public:

  set<int> S;

  int longestConsecutive(vector<int>& nums) {
    for(auto i: nums)
      S.insert(i);

    int ans = 0;
    for(auto i: S){
      int n = i + 1;
      int cnt = 1;
      while(S.count(n)) {
        cnt++;
        n++;
      }
      ans = max(ans, cnt);
    }

    return ans;
  }
};

An Optimization on the previous solution: reduce duplicated checking

The duplicated checking happened at a long consecutive array, suppose we have 3, 4, 5, 6, 7.

First, we checked with 3, and then checked at 4, and 5 …

This could be avoided if we test whether i-1 has been checked.

class Solution {
public:
  set<int> S;

  int longestConsecutive(vector<int>& nums) {
    for(auto i: nums)
      S.insert(i);

    int ans = 0;
    for(auto i: S){
      if(!S.count(i-1)) {
        int n = i;
        int cnt = 1;
        while(S.count(n+1)) {
          cnt++;
          n++;
        }
        ans = max(ans, cnt);
      }
    }
    return ans;
  }
};

Use union-find to store relationships of elements

union-find is an elegant data structure to store and query consecutive relationships. U will store the next larger elements of one element.

Iterate with all the elements, try to find the largest element from one starting point, and the distance of two elements will be the number of consecutive elements.

class Solution {
public:
  map<int,int> U;

  int find(int x){
    return U.count(x) ? U[x] = find(U[x]) : x;
  }

  int longestConsecutive(vector<int>& nums) {
    for(auto i: nums)
      U[i] = i+1;

    int ans = 0;
    for(auto i: nums){
      int y = find(i+1);
      ans = max(ans, y-i);
    }
    return ans;
  }
};

The post LeetCode: Longest Consecutive Sequence appeared first on Coder's Cat.