Simple C++ Greedy O(nlogn) Solution (with explanation)


  • 13

    The Algorithm

    Maintain a set of consecutive sequences, call this set s. s begins as an empty set of consecutive sequences.

    Now, iterate through each num in nums. For each iteration, if there exists a consecutive sequence in s that ends with element num-1, then append num to the end of the shortest such sequence; otherwise, create a new sequence that begins with num.

    The problem has a solution (i.e. the array can be split into consecutive subsequences such that each subsequence consists of at least 3 consecutive integers) if and only if each sequence in s has size greater than or equal to 3.

    Proof of Algorithm

    Why does this algorithm work? It was intuitive to me, but I could not indisputably prove that it was correct. Hopefully, someone else can prove it.

    Implementation

    We don't need to actually store each sequence. Instead, we just need to know (1) the number of sequences that end at a particular element, and (2) the size of each of those sequences. To implement this, we can have an unordered map backs to represent the sequences: backs[key] returns a priority queue (smallest value at top) of the sizes of all sequences that end with element key. Now that we have (1) and (2), we can implement the algorithm above without knowing each particular sequence.

    For each num in nums, if there exists any sequence that ends with num-1 (i.e. if backs[num-1] is a non-empty priority queue), then find such a sequence with the smallest possible size (get the smallest value from the priority queue at backs[num-1]). Now, the sequence will be extended by 1 since we will add num to it. So pop the smallest value count from the priority queue at backs[num-1], and add a new value count+1 to the priority queue at backs[num].

    If no sequence was found that ends in num-1 (i.e. backs[num-1] is empty), then create a new sequence. In other words, add 1 to the priority queue at backs[num].

    The Code

    class Solution {
    public:
    	bool isPossible(vector<int>& nums)
    	{
    		unordered_map<int, priority_queue<int, vector<int>, std::greater<int>>> backs;
    
    		// Keep track of the number of sequences with size < 3
    		int need_more = 0;
    
    		for (int num : nums)
    		{
    			if (! backs[num - 1].empty())
    			{	// There exists a sequence that ends in num-1
    				// Append 'num' to this sequence
    				// Remove the existing sequence
    				// Add a new sequence ending in 'num' with size incremented by 1 
    				int count = backs[num - 1].top();
    				backs[num - 1].pop();
    				backs[num].push(++count);
    
    				if (count == 3)
    					need_more--;
    			}
    			else
    			{	// There is no sequence that ends in num-1
    				// Create a new sequence with size 1 that ends with 'num'
    				backs[num].push(1);
    				need_more++;
    			}
    		}
    		return need_more == 0;
    	}
    };
    

    Improvements

    I know that there are O(n) solutions out there that use different algorithms. Can my algorithm be implemented more efficiently to be O(n) instead of O(nlogn)?

    Thoughts?


  • 0
    Y

    Nice solution, appreciate it


  • 1
    C

    Hi, I think we almost have the same idea. The reason we have O(nlogn) instead of O(n) is because of the priority queue. In fact, append to the shortest subsequence is not necessary. Any subsequences with the length larger than 3 are equal.
    A way to solve that is to use another hashmap or vector as a counter to count how many times each number show up in the original sequence. Then, do another for loop to formulate subsequences. This time, when trying to form a new subseuqences, make sure you get 3 number ahead of time.


  • 1
    C

    Actually, you don't need the priority_queue, just an array contains the number of sequences of length 1, 2, 3+ is enough. Then the time is O(n).

    My python code:

    def isPossible(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        chains = {}
        for x in nums:
            #count of chains end with x and having length 0,1,2,3+
            pre = chains.setdefault(x-1, [0,0,0,0])
            cur = chains.setdefault(x, [0,0,0,0])
            #add x to the shortest chain
            if pre[1] > 0:
                pre[1] -= 1
                cur[2] += 1
            elif pre[2] > 0:
                pre[2] -= 1
                cur[3] += 1
            elif pre[3] > 0:
                pre[3] -= 1
                cur[3] += 1
            else:
                cur[1] += 1
        
        for x in chains:
            if chains[x][1] or chains[x][2]:
                return False
        return True
    

  • 0
    K

    @jay520 noob question here, how is your complexity nlogn ?


  • 0
    L

    I think this is also O(n), why not?
    Quote:
    class Solution {
    public:
    bool isPossible(vector<int>& nums)
    {
    unordered_map<int, priority_queue<int, vector<int>, std::greater<int>>> backs;

    	// Keep track of the number of sequences with size < 3
    	int need_more = 0;
    
    	for (int num : nums)
    	{
    		if (! backs[num - 1].empty())
    		{	// There exists a sequence that ends in num-1
    			// Append 'num' to this sequence
    			// Remove the existing sequence
    			// Add a new sequence ending in 'num' with size incremented by 1 
    			int count = backs[num - 1].top();
    			backs[num - 1].pop();
    			backs[num].push(++count);
    
    			if (count == 3)
    				need_more--;
    		}
    		else
    		{	// There is no sequence that ends in num-1
    			// Create a new sequence with size 1 that ends with 'num'
    			backs[num].push(1);
    			need_more++;
    		}
    	}
    	return need_more == 0;
    }
    

    };


  • 0
    T

    @csytracy Hey, could you please give your code for the same ??


  • 0
    J

    Hi, my idea is also go through the array but achieving O(n), you can check it out here:
    https://discuss.leetcode.com/topic/100988/c-o-n-solution-two-pass


Log in to reply
 

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