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


  • 0
    A

    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;
    }

  • 0

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


  • 0
    A

    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!


  • 0

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


  • 0
    C
     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){
            if(!set.add(n)) continue;
            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?


Log in to reply
 

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