# What if the problem requires that the consecutive sequence must also keep original order in the array?

• I was asked this variation of this problem at one of the interviews:
What if the problem requires that the consecutive sequence must also keep original order in the array?

For example:
[100, 4, 200, 6, 5, 7, 9, 8] should return 3 instead of 6

The solution using unordered_set would not work, right?

Here is my solution using hashmap (unordered_map in C++). Since I cannot verify it on Leetcode, please correct me if it is wrong. Many Thanks!

``````int longestConsecutive(vector<int>& nums) {
unordered_map<int, unsigned> numMap;
int maxLen = 0;
for (int i = 0; i < nums.size(); ++i)
numMap[nums[i]] = i;

// check each number
for (int i = 0; i < nums.size(); ++i) {
int len = 0;
// if the number has not been checked. grow window around it
if (numMap.find(nums[i]) != numMap.end()) {
len++;
int right = nums[i]+1;
int k = i;
// find the rightmost boundary
while (numMap.find(right) != numMap.end() && numMap[right] > k) {
len++;
k = numMap[right];
numMap.erase(right);
right++;
}

int left = nums[i]-1;
k = i;
// find the leftmost boundary
while (numMap.find(left) != numMap.end() && numMap[left] < k) {
len++;
k = numMap[left];
numMap.erase(left);
left--;
}
if (len > maxLen)
maxLen = len;
}
}
return maxLen;
}``````

• I don't see why [100, 4, 200, 6, 5, 7, 9, 8] should return 3...

• I was asking a variation of this problem: what if the consecutive sequence must keep the original order. The solution to original problem [4,5,6,7,8,9] is invalid because the order is changed. The solution to the new problem should be [6,7,8]. Thanks!

• Ah, [6, 7, 8]. Thanks, got it now.

• `````` public int longestConsecutive(int[] nums) {
Map<Integer, Integer> start=new HashMap<>();
Map<Integer, Integer> end=new HashMap<>();
int max=Integer.MIN_VALUE;
Set<Integer> set=new HashSet<>();
for(int n:nums){
int res;
//int a=start.containsKey(n+1)?start.get(n+1):n;
int a=n;
int b=end.containsKey(n-1)?end.get(n-1):n;
res=a-b+1;
//start.put(b,a);
end.put(a,b);
max=Math.max(res,max);
}
return max;
}
``````

would this work?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.