aboutsummaryrefslogtreecommitdiff
path: root/longest_consecutive_sequence.cpp
blob: 2fda5e65cb9a248addd450ddacb7232184a7cb92 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include "leetcode.h"

class Solution {
public:
  int longestConsecutive(vector<int> &nums) {
    unordered_set<int> us;
    int ans = 0;
    for (int i = 0; i < nums.size(); i++)
      us.insert(nums[i]);
    while (us.size() > 0) {
      int num = *us.begin();
      int count = 1;
      us.erase(num);
      int smaller = num - 1;
      int bigger = num + 1;
      while (us.count(smaller) > 0) {
        us.erase(smaller);
        smaller--;
        count++;
      }
      while (us.count(bigger) > 0) {
        us.erase(bigger);
        bigger++;
        count++;
      }
      ans = max(ans, count);
    }
    return ans;
  }
};

int main() {
  Solution obj;
  vector<int> nums = {100, 4, 200, 1, 3, 2};
  cout << obj.longestConsecutive(nums);
}