Split Array into Consecutive Subsequences

Leetcode Problem 659: Split Array into Consecutive Subsequences

Problem Summary

Given a sorted integer array nums, determine whether it can be split into one or more consecutive subsequences of length at least 3. Each element must be used in exactly one subsequence.

Constraints:

• The array has between 1 and 10,000 elements.
• Element values are integers in the range [1, 1,000].

Techniques

• Array
• Hash Table
• Greedy
• Heap (Priority Queue)

Solution

function isPossible(nums: number[]): boolean {
    const freq = new Map<number, number>(); 
    const need = new Map<number, number>();

    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }

    for (const num of nums) {
        if (freq.get(num) === 0) 
            continue; 

        if ((need.get(num) ?? 0) > 0) {
            need.set(num, need.get(num)! - 1);
            need.set(num + 1, (need.get(num + 1) || 0) + 1);
        } 
        else if ((freq.get(num + 1) ?? 0) > 0 && (freq.get(num + 2) ?? 0) > 0) {
            freq.set(num + 1, freq.get(num + 1)! - 1);
            freq.set(num + 2, freq.get(num + 2)! - 1);
            need.set(num + 3, (need.get(num + 3) || 0) + 1);
        } 
        else {
            return false;
        }

        freq.set(num, freq.get(num)! - 1);
    }

    return true;
}

console.log(isPossible([1,2,3,3,4,5])); // true
console.log(isPossible([1,2,3,3,4,4,5,5])); // true
console.log(isPossible([1,2,3,4,4,5])); // false