128. Longest Consecutive Sequence - cocoder39/coco39_LC GitHub Wiki
128. Longest Consecutive Sequence
- (1) optimal:
mp[i] = j where j is the length of the consecutive sequence that containing i.
tip:
mp[num] = len. (1) insert num into map (2) why notmp[num] = a random numbersince we would only check the length of boundary element. for elements within a consecutive sequence and are not boundaries, we only check if it appeared before? Answer: make mp[num] consistent with mp[num - len] or mp[num+len] when num is exactly the boundary. we can also switch the position.
mp[num] = 0;
mp[num - left_len] = len;
mp[num + right_len] = len;
int longestConsecutive(vector<int>& nums) {
int res = 0;
unordered_map<int, int> mp; //seq[i] is length of a consecutive sequence containing i
for (auto num : nums) {
if (mp.find(num) == mp.end()) { //ignore repeat num
int left_len = mp.find(num - 1) != mp.end() ? mp[num - 1] : 0;
int right_len = mp.find(num + 1) != mp.end() ? mp[num + 1] : 0;
int len = left_len + right_len + 1;
mp[num - left_len] = len;
mp[num + right_len] = len;
mp[num] = len;
res = max(res, len);
}
}
return res;
}
- (2) O(n * log n) sort
- (3) bucket sort, O(n) time. But we need check the max_size() that a vector can handle. if the input includes INT_MIN and INT_MAX, then high - low + 1 = 2^31 - 1 - (-2^31) + 1 = 2^32 > 2^32 - 1 = max of
unsigned int. (size_type is unsigned int). So ask if there is bound for input numbers
int longestConsecutive(vector<int>& nums) {
int low = INT_MAX;
int high = INT_MIN;
for (auto num : nums) {
low = min(low, num);
high = max(high, num);
}
vector<bool> visited(high - low + 1);
for (auto num : nums) {
visited[num - low] = true;
}
int res = 0;
int cur = 0;
for (long long i = 0; i < visited.size(); i++) {
if (! visited[i]) {
cur = 0;
} else {
cur++;
res = max(res, cur);
}
}
return res;
}
- (4) union find. ametrized O(n)
class UnionFind {
public:
UnionFind(int N) {
for (int i = 0; i < N; i++) {
parent.push_back(i);
}
sz = vector<int>(N, 1);
}
void unite(int i, int j) {
int p = root(i);
int q = root(j);
if (p == q) return;
if (sz[p] < sz[q]) {
parent[p] = q;
sz[q] += sz[p];
} else {
parent[q] = p;
sz[p] += sz[q];
}
}
bool isConnected(int i, int j) {
return root(i) == root(j);
}
int getMaxSz() {
int res = 0;
for (auto i : sz) {
res = max(res, i);
}
return res;
}
private:
vector<int> parent;
vector<int> sz;
int root(int i) {
while (i != parent[i]) {
parent[i] = parent[parent[i]];
i = parent[i];
}
return i;
}
};
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int sz = nums.size();
UnionFind uf(sz);
unordered_map<int, int> mp;
for (int i = 0; i < sz; i++) {
if (mp.find(nums[i]) != mp.end()) continue;
mp[nums[i]] = i;
if (mp.find(nums[i] - 1) != mp.end()) uf.unite(i, mp[nums[i] - 1]);
if (mp.find(nums[i] + 1) != mp.end()) uf.unite(i, mp[nums[i] + 1]);
}
return uf.getMaxSz();
}
};
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aug. 17, 2020
Option 1: looks like O(N^2) time complexity but it is actually O(N). Executing while loop only for the left most item in a range if num - 1 not in st
def longestConsecutive(self, nums: List[int]) -> int:
st = set(nums)
max_len = 0
for num in st:
if num - 1 not in st:
cur_len = 1
while num + 1 in st:
cur_len += 1
num += 1
max_len = max(max_len, cur_len)
return max_len
Option 2: merge resulted range while introducing new num
def longestConsecutive(self, nums: List[int]) -> int:
# mp[left] = right, mp[right] = left
left = {}
right = {}
seen = set(nums)
for num in seen:
merged = False
while num - 1 in left or num + 1 in right:
merged = True
if num - 1 in left: # num may contribute
l = left[num-1]
r = right[num] if num in right else num
del left[num-1]
if num in right:
del right[num]
left[r] = l
right[l] = r
elif num + 1 in right:
r = right[num+1]
l = left[num] if num in left else num
del right[num+1]
if num in left:
del left[num]
left[r] = l
right[l] = r
if not merged:
left[num] = num
right[num] = num
length = 0
for k, v in left.items():
length = max(length, k-v+1)
return length
Option 3: Union find
def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
st = set(nums)
parent = {}
size = {}
for num in st:
parent[num] = num
size[num] = 1
def root(i):
while i != parent[i]:
i = parent[parent[i]]
return parent[i]
def union(i, j):
p, q = root(i), root(j)
if p == q:
return
if size[p] < size[q]:
parent[p] = q
size[q] += size[p]
else:
parent[q] = p
size[p] += size[q]
for num in st:
if num - 1 in st:
union(num-1, num)
if num + 1 in st:
union(num, num+1)
return max(size.values())