Problem Description

Given a sorted array of integers called nums, you are to determine if it is possible to split nums into one or more subsequences, where each subsequence consists of consecutive integers and has a length of at least 3.

• Each element in nums must be used exactly once in exactly one subsequence.
• Subsequences must be made up of consecutive integers, for example, [1,2,3], [3,4,5,6].
• You must not reuse elements in multiple subsequences.
• The function should return True if such a split is possible, otherwise False.

Example:
Input: nums = [1,2,3,3,4,5]
Output: True
Explanation: You can split it as [1,2,3] and [3,4,5].

Thought Process

The brute-force way to approach this problem would be to try all possible ways of splitting the array into subsequences and check if all of them are valid. However, this quickly becomes infeasible as the array grows, because the number of ways to split increases exponentially.

Instead, we need to look for a pattern or greedy way to build valid subsequences as we iterate through the array. The key insight is that we should always try to extend existing subsequences if possible, because starting a new subsequence is only valid if we can guarantee it will reach a length of at least 3.

Think of the problem as trying to "fit" each number into a subsequence: either by extending an existing one, or by starting a new one (only if there are enough future numbers to make it at least length 3).

Solution Approach

We can solve this problem efficiently using two hash maps:

• Frequency Map (freq): Counts how many times each number appears in nums. This helps us track which numbers are still available to be used.
• Need Map (need): Counts how many subsequences are currently "waiting for" a certain number to continue. For example, if need[4] = 2, it means two subsequences end at 3 and are waiting for 4 to be appended.

1. Iterate through each number x in nums:
   • If freq[x] == 0, skip it (already used).
   • If need[x] > 0, it means there is a subsequence ending at x-1 that can be extended with x.
     • Decrement freq[x] and need[x].
     • Increment need[x+1] (the subsequence now wants x+1).
   • Else, try to create a new subsequence starting at x:
     • Check if freq[x+1] > 0 and freq[x+2] > 0 (need at least 3 consecutive numbers).
     • If yes, decrement freq[x], freq[x+1], freq[x+2].
     • Increment need[x+3] (the new subsequence now wants x+3).
     • If not, return False (cannot form a valid subsequence).
2. If we finish the loop without returning False, return True.

This approach ensures that we never leave a subsequence "dangling" at length less than 3, and always tries to extend existing subsequences first, which is optimal.

Example Walkthrough

Let's walk through the example nums = [1,2,3,3,4,5] step by step:

1. freq: {1:1, 2:1, 3:2, 4:1, 5:1}
   need: {}
2. x = 1:
   - need[1] is 0.
   - freq[2] > 0 and freq[3] > 0, so start new subsequence [1,2,3].
   - Update: freq[1]=0, freq[2]=0, freq[3]=1, need[4]=1
3. x = 2:
   - freq[2]=0, skip.
4. x = 3:
   - need[3]=0.
   - freq[4]=1 and freq[5]=1, so start new subsequence [3,4,5].
   - Update: freq[3]=0, freq[4]=0, freq[5]=0, need[6]=1
5. x = 3 (second time):
   - freq[3]=0, skip.
6. x = 4:
   - freq[4]=0, skip.
7. x = 5:
   - freq[5]=0, skip.

All numbers are used, and all subsequences are of length at least 3. So the answer is True.

Time and Space Complexity

• Brute-force: The brute-force approach would try all possible ways to split the array, which is exponential time in the worst case, i.e. O(2^n). This is not feasible for large inputs.
• Optimized (Hash Map) Approach:
  • Time Complexity: O(n), where n is the length of nums. Each number is processed at most once, and all hash map operations are O(1) on average.
  • Space Complexity: O(n), since both freq and need can, in the worst case, store counts for every unique number in nums.

Summary

The key to solving the "Split Array into Consecutive Subsequences" problem efficiently is to always try to extend existing subsequences before starting new ones, and to only start a new subsequence if you can guarantee it will reach length 3. Using hash maps to track frequencies and needs allows us to do this in linear time, making the solution both efficient and elegant. This greedy approach ensures that all constraints are satisfied and no number is left unused or misused.

Code Implementation

from collections import Counter, defaultdict

class Solution:
    def isPossible(self, nums):
        freq = Counter(nums)
        need = defaultdict(int)
        for x in nums:
            if freq[x] == 0:
                continue
            if need[x] > 0:
                freq[x] -= 1
                need[x] -= 1
                need[x + 1] += 1
            elif freq[x + 1] > 0 and freq[x + 2] > 0:
                freq[x] -= 1
                freq[x + 1] -= 1
                freq[x + 2] -= 1
                need[x + 3] += 1
            else:
                return False
        return True
      

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> freq, need;
        for (int x : nums) freq[x]++;
        for (int x : nums) {
            if (freq[x] == 0) continue;
            if (need[x] > 0) {
                freq[x]--;
                need[x]--;
                need[x + 1]++;
            }
            else if (freq[x + 1] > 0 && freq[x + 2] > 0) {
                freq[x]--;
                freq[x + 1]--;
                freq[x + 2]--;
                need[x + 3]++;
            }
            else {
                return false;
            }
        }
        return true;
    }
};
      

import java.util.*;

class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        Map<Integer, Integer> need = new HashMap<>();
        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
        for (int x : nums) {
            if (freq.get(x) == 0) continue;
            if (need.getOrDefault(x, 0) > 0) {
                freq.put(x, freq.get(x) - 1);
                need.put(x, need.get(x) - 1);
                need.put(x + 1, need.getOrDefault(x + 1, 0) + 1);
            } else if (freq.getOrDefault(x + 1, 0) > 0 && freq.getOrDefault(x + 2, 0) > 0) {
                freq.put(x, freq.get(x) - 1);
                freq.put(x + 1, freq.get(x + 1) - 1);
                freq.put(x + 2, freq.get(x + 2) - 1);
                need.put(x + 3, need.getOrDefault(x + 3, 0) + 1);
            } else {
                return false;
            }
        }
        return true;
    }
}
      

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isPossible = function(nums) {
    let freq = new Map();
    let need = new Map();
    for (let x of nums) {
        freq.set(x, (freq.get(x) || 0) + 1);
    }
    for (let x of nums) {
        if (freq.get(x) === 0) continue;
        if ((need.get(x) || 0) > 0) {
            freq.set(x, freq.get(x) - 1);
            need.set(x, need.get(x) - 1);
            need.set(x + 1, (need.get(x + 1) || 0) + 1);
        } else if ((freq.get(x + 1) || 0) > 0 && (freq.get(x + 2) || 0) > 0) {
            freq.set(x, freq.get(x) - 1);
            freq.set(x + 1, freq.get(x + 1) - 1);
            freq.set(x + 2, freq.get(x + 2) - 1);
            need.set(x + 3, (need.get(x + 3) || 0) + 1);
        } else {
            return false;
        }
    }
    return true;
};