I used a greedy alorithme.
leftis a hashmap,
left[i] counts the number of
i that I haven't placed yet.
endis a hashmap,
end[i] counts the number of consecutive subsequences that ends at number
Then I tried to split the nums one by one.
If I could neigther add a number to the end of a existing consecutive subsequence nor find two following number in the left, I returned
def isPossible(self, nums): left = collections.Counter(nums) end = collections.Counter() for i in nums: if not left[i]: continue left[i] -= 1 if end[i - 1] > 0: end[i - 1] -= 1 end[i] += 1 elif left[i + 1] and left[i + 2]: left[i + 1] -= 1 left[i + 2] -= 1 end[i + 2] += 1 else: return False return True
@jedihy I got a similar idea and implement that on C++ by my own, you can check it out here:https://discuss.leetcode.com/topic/100988/c-o-n-solution-two-pass
Thanks for your explanation. I upvoted yours.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.