Split Array into Consecutive Subsequences

leetcode 659. Split Array into Consecutive Subsequences

Intuition

Store how many time a num+1000 exist in nums. We know that to form a vaild subsequence it has to be three nums, so if there're possibly a new sequence, we add it to queue. If there should be one or multiple subsequence going to end, check if it contains three elements, otherwise return false.

Code

bool isPossible(vector<int>& nums) {
	vector<int> sub(3000, false);
	for(int i : nums) sub[i+1000]++;
	int count = 0, last = 0;
	queue<int> q;
	for(int i = 0; i < 2004; i++) {
		while (sub[i] > q.size()) q.push(i);

		while (sub[i] < q.size()) {
			if(q.front()+2 < i) q.pop();
			else return false;
		}

	}
	return true;
}

Complexity Analysis

Time: O(n)

Space: O(n)