Leetcode 659 Solution

This article provides solution to leetcode question 659 (split-array-into-consecutive-subsequences)
Categories:
Tags:
Access this page by simply typing in "lcs 659" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/split-array-into-consecutive-subsequences

Solution

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> freq;
        unordered_map<int, int> tails;

        for (auto num: nums)
            freq[num] += 1;

        for (auto num: nums)
        {
            if (freq[num] == 0)
                continue;
            else if (tails[num] > 0)
            {
                tails[num] -= 1;
                tails[num + 1] += 1;

                freq[num] -= 1;
            }
            else if (freq[num + 1] > 0 && freq[num + 2] > 0)
            {
                freq[num + 1] -= 1;
                freq[num + 2] -= 1;
                tails[num + 3] += 1;

                freq[num] -= 1;
            }
            else
                return false;
        }

        return true;
    }
};