# Split Array into Consecutive Subsequences
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/split-array-into-consecutive-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/split-array-into-consecutive-subsequences
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
You are given an integer array `nums` that is **sorted in non-decreasing order**.

Determine if it is possible to split `nums` into **one or more subsequences** such that **both** of the following conditions are true:

* Each subsequence is a **consecutive increasing sequence** (i.e. each integer is **exactly one** more than the previous integer).
* All subsequences have a length of `3` **or more**.

Return `true` _if you can split_ `nums` _according to the above conditions, or_ `false` _otherwise_.

A **subsequence** of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., `[1,3,5]` is a subsequence of `[1,2,3,4,5]` while `[1,3,2]` is not).

**Example 1:**

**Input:** nums = [1,2,3,3,4,5]
**Output:** true
**Explanation:** nums can be split into the following subsequences:
[**1**,**2**,**3**,3,4,5] --> 1, 2, 3
[1,2,3,**3**,**4**,**5**] --> 3, 4, 5

**Example 2:**

**Input:** nums = [1,2,3,3,4,4,5,5]
**Output:** true
**Explanation:** nums can be split into the following subsequences:
[**1**,**2**,**3**,3,**4**,4,**5**,5] --> 1, 2, 3, 4, 5
[1,2,3,**3**,4,**4**,5,**5**] --> 3, 4, 5

**Example 3:**

**Input:** nums = [1,2,3,4,4,5]
**Output:** false
**Explanation:** It is impossible to split nums into consecutive increasing subsequences of length 3 or more.

**Constraints:**

* `1 <= nums.length <= 104`
* `-1000 <= nums[i] <= 1000`
* `nums` is sorted in **non-decreasing** order.

# Approaches
## Greedy Approach with Min-Heap
This approach uses a greedy strategy combined with a min-heap (PriorityQueue in Java) to keep track of the lengths of all active subsequences. The core idea is that for any number `x`, it's always optimal to append it to an existing subsequence ending in `x-1` rather than starting a new one. If there are multiple such subsequences, we extend the one that is currently the shortest. This is because shorter subsequences are 'in more danger' of not reaching the required length of 3, so we prioritize helping them grow.
**Time:** O(N log N), where N is the length of `nums`. We iterate through each of the N numbers. For each number, we perform map lookups (which are O(1) on average) and at most one heap poll and one heap add operation. Heap operations take O(log K) time, where K is the size of the heap. In the worst case, K can be on the order of N (e.g., for an array like `[1,1,1,2,2,2,3,3,3]`), leading to an overall complexity of O(N log N). · **Space:** O(N), where N is the length of `nums`. In the worst-case scenario (e.g., an array with all unique, non-consecutive numbers), the map will store N entries, and each priority queue will have one element.
**Pros:** The greedy logic is relatively straightforward to conceptualize.; It correctly solves the problem by prioritizing the extension of shorter subsequences.
**Cons:** The time complexity is O(N log N), which is not optimal.; The space complexity is O(N), which can be improved.
### Explanation
We use a `HashMap` where keys are the ending numbers of subsequences and values are `PriorityQueue`s storing the lengths of these subsequences. The `PriorityQueue` acts as a min-heap, allowing us to efficiently access the shortest subsequence ending at a particular number.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public boolean isPossible(int[] nums) {
        // Map from a number to a priority queue of lengths of subsequences ending with that number.
        Map<Integer, PriorityQueue<Integer>> tails = new HashMap<>();

        for (int num : nums) {
            if (tails.containsKey(num - 1) && !tails.get(num - 1).isEmpty()) {
                // Extend the shortest subsequence ending at num - 1
                int length = tails.get(num - 1).poll();
                
                // Add the new extended subsequence
                tails.computeIfAbsent(num, k -> new PriorityQueue<>()).add(length + 1);
            } else {
                // Start a new subsequence of length 1
                tails.computeIfAbsent(num, k -> new PriorityQueue<>()).add(1);
            }
        }

        // Check if all subsequences have length 3 or more
        for (PriorityQueue<Integer> pq : tails.values()) {
            if (!pq.isEmpty() && pq.peek() < 3) {
                return false;
            }
        }

        return true;
    }
}
```

After processing all numbers, we iterate through the map. If any priority queue contains a length less than 3, it means we have a subsequence that is too short, and we return `false`. If all subsequences meet the length requirement, we return `true`.
### Algorithm
*   Initialize a `HashMap` named `tails` where the key is an integer `x` and the value is a `PriorityQueue` of lengths of consecutive subsequences ending at `x`.
*   Iterate through each number `num` in the input array `nums`.
*   Check if there is a priority queue for `num - 1` in the `tails` map and if it's not empty. This signifies that there's at least one subsequence ending at `num - 1` that we can extend.
*   If such a subsequence exists, we greedily extend the shortest one. We do this by polling the smallest length `len` from the priority queue `tails.get(num - 1)`.
*   We then add a new entry to the priority queue for `num`, with the new length `len + 1`. We use `map.computeIfAbsent` to create a new priority queue if one doesn't exist for `num`.
*   If no subsequence ending at `num - 1` exists, we must start a new subsequence. We add a new entry of length `1` to the priority queue for `num`.
*   After iterating through all numbers, we examine the `tails` map. We iterate through all the priority queues in the map.
*   For each priority queue, we check if its smallest element (the length of the shortest subsequence ending at that number) is less than 3.
*   If we find any subsequence with a length less than 3, it's impossible to satisfy the conditions, so we return `false`.
*   If all subsequences have a length of 3 or more, we return `true`.

## Greedy Approach with Two Hash Maps
This is a more efficient greedy approach that achieves linear time complexity. The strategy is based on a simple, powerful observation: for any number `x`, it is always better to append it to an existing subsequence ending at `x-1` than to use it to start a new subsequence. Starting a new subsequence `[x, x+1, x+2]` immediately consumes future numbers that might be crucial for extending other, already existing subsequences.

To implement this, we use two hash maps. The first, `freq`, keeps track of the availability of each number. The second, `append`, keeps track of how many subsequences are 'needing' a particular number to be appended.
**Time:** O(N), where N is the length of `nums`. The first loop to build the frequency map takes O(N). The second loop also iterates N times, and each step involves hash map operations which are O(1) on average. Thus, the total time complexity is linear. · **Space:** O(N), where N is the length of `nums`. In the worst case, if all numbers are distinct, the `freq` and `append` maps could store up to N entries.
**Pros:** Achieves optimal O(N) time complexity.; The logic is a very clear and direct implementation of the greedy choice.; Generally easier to implement correctly than the O(1) space solution.
**Cons:** Requires O(N) extra space for the two hash maps, which is not optimal.
### Explanation
The algorithm makes two passes. The first pass populates the frequency map. The second pass iterates through the numbers and makes a greedy decision for each one.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        Map<Integer, Integer> append = new HashMap<>();

        for (int num : nums) {
            if (freq.get(num) == 0) {
                continue; // This number has been used
            }

            // Case 1: Append to an existing subsequence
            if (append.getOrDefault(num, 0) > 0) {
                append.put(num, append.get(num) - 1);
                append.put(num + 1, append.getOrDefault(num + 1, 0) + 1);
            }
            // Case 2: Start a new subsequence
            else if (freq.getOrDefault(num + 1, 0) > 0 && freq.getOrDefault(num + 2, 0) > 0) {
                freq.put(num + 1, freq.get(num + 1) - 1);
                freq.put(num + 2, freq.get(num + 2) - 1);
                append.put(num + 3, append.getOrDefault(num + 3, 0) + 1);
            }
            // Case 3: Impossible to place the number
            else {
                return false;
            }

            freq.put(num, freq.get(num) - 1);
        }

        return true;
    }
}
```
### Algorithm
*   First, create a frequency map, `freq`, to store the counts of each number in `nums`.
*   Second, create another map, `append`, where `append[x]` will store the number of subsequences that have ended at `x-1` and are now looking for `x` to be appended.
*   Iterate through each number `num` in the `nums` array.
*   If `freq.get(num) == 0`, this number has already been used up by a preceding subsequence, so we can continue to the next number.
*   **Greedy Choice 1: Extend an existing subsequence.** Check if `append.get(num) > 0`. If true, it means there is at least one subsequence waiting for `num`. We use the current `num` to extend it. We decrement `append.get(num)` and increment `append.get(num + 1)` because the subsequence now ends at `num` and is waiting for `num + 1`.
*   **Greedy Choice 2: Start a new subsequence.** If `append.get(num) == 0`, we have no choice but to start a new subsequence with `num`. For this to be valid, it must have a length of at least 3. So, we check if `num + 1` and `num + 2` are available (i.e., their counts in `freq` are greater than 0).
*   If they are available, we form a new subsequence `[num, num + 1, num + 2]`. We decrement the frequencies of `num + 1` and `num + 2` in the `freq` map. We then increment `append.get(num + 3)` because this new subsequence is now waiting for `num + 3`.
*   If `num + 1` and `num + 2` are not available, we cannot place the current `num`, so it's impossible to form a valid split. Return `false`.
*   After processing a `num` (either by extending or starting a new sequence), we must decrement its count in `freq`.
*   If the loop completes without returning `false`, it means all numbers were successfully placed into valid subsequences. Return `true`.

## Greedy Approach with O(1) Space
This is the most optimal approach, achieving linear time and constant space. It leverages the fact that the input array `nums` is sorted. Instead of using maps to track all subsequences, we can process the numbers sequentially and only maintain counts of how many subsequences of certain lengths end at the *immediately preceding* value. This is sufficient because to extend a subsequence with `x`, we only care about subsequences that end in `x-1`.
**Time:** O(N), where N is the length of `nums`. Although there is a nested `while` loop, the outer loop pointer `i` is advanced by the inner loop. This means each element of the array is visited only a constant number of times, resulting in a single pass and linear time complexity. · **Space:** O(1). We only use a handful of variables (`ones`, `twos`, `longs`, `prev`, `i`, `count`, etc.) to maintain state, which does not depend on the size of the input array.
**Pros:** Optimal O(N) time complexity.; Optimal O(1) space complexity.; Intelligently utilizes the sorted property of the input array to avoid extra data structures.
**Cons:** The logic is more intricate and less intuitive than the hash map approach, making it potentially harder to implement correctly.
### Explanation
We iterate through the array, but instead of one element at a time, we process groups of identical elements. We only need three variables, `ones`, `twos`, and `longs`, to store the number of subsequences ending at the previous value (`prev`) with lengths 1, 2, and >=3, respectively. This constant-size state is updated as we move from one number to the next consecutive one.

```java
class Solution {
    public boolean isPossible(int[] nums) {
        // Counts of subsequences ending at prev with length 1, 2, and >=3
        int ones = 0, twos = 0, longs = 0;
        int prev = Integer.MIN_VALUE;

        int i = 0;
        while (i < nums.length) {
            int start = i;
            int curr = nums[i];
            while (i < nums.length && nums[i] == curr) {
                i++;
            }
            int count = i - start;

            if (prev != Integer.MIN_VALUE && curr != prev + 1) {
                // Gap in the sequence
                if (ones != 0 || twos != 0) {
                    return false; // Short sequences cannot be extended
                }
                // Start new sequences
                ones = count;
                twos = 0;
                longs = 0;
            } else {
                // Consecutive sequence
                if (count < ones + twos) {
                    return false; // Not enough numbers to extend short sequences
                }
                
                int remaining = count - ones - twos;
                int newLongs = twos + Math.min(longs, remaining);
                int newOnes = Math.max(0, remaining - longs);
                
                longs = newLongs;
                twos = ones;
                ones = newOnes;
            }
            prev = curr;
        }

        // After the loop, check if there are any uncompleted short sequences
        return ones == 0 && twos == 0;
    }
}
```
### Algorithm
*   Initialize three counters: `ones`, `twos`, and `longs` to 0. These will track the number of subsequences ending at the *previous* number (`prev`) that have lengths of 1, 2, and >=3, respectively.
*   Iterate through the `nums` array with an index `i`. Since the array is sorted, we can process identical numbers in a single batch.
*   In each iteration, count the occurrences of the current number `nums[i]`, let's call it `count`.
*   **Handle Gaps:** If the current number `nums[i]` is not `prev + 1` (and it's not the first number), it means there is a gap in the sequence. If at this point `ones > 0` or `twos > 0`, it means we have subsequences of length 1 or 2 that cannot be extended. This is an invalid state, so return `false`. If there are no short subsequences, we can safely 'forget' the old `longs` sequences and start fresh. We set `ones = count`, `twos = 0`, and `longs = 0` for the current number.
*   **Handle Consecutive Numbers:** If `nums[i] == prev + 1`, we must extend the subsequences ending at `prev`. The number of available `nums[i]` (`count`) must be sufficient to extend all the short subsequences, i.e., `count >= ones + twos`. If not, return `false`.
*   We update the counts for the current number `nums[i]`. The `ones` from `prev` become `twos`. The `twos` from `prev` become `longs`. The remaining `count - ones - twos` of `nums[i]` are used first to extend the `longs` sequences, and any leftovers must start new `ones` sequences.
*   Specifically, the new `twos` count is the old `ones` count. The new `longs` count is the old `twos` count plus `min(old_longs, remaining_count)`. The new `ones` count is `max(0, remaining_count - old_longs)`.
*   Update `prev` to `nums[i]` and advance `i` past the current group of identical numbers.
*   After the loop finishes, we must check the state of the very last number processed. If `ones > 0` or `twos > 0`, it means we ended with subsequences that are too short. Return `false`.
*   If all checks pass, return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean isPossible(int[] nums) {
    Map<Integer, PriorityQueue<Integer>> d = new HashMap<>();
    for (int v : nums) {
      if (d.containsKey(v - 1)) {
        var q = d.get(v - 1);
        d.computeIfAbsent(v, k->new PriorityQueue<>()).offer(q.poll() + 1);
        if (q.isEmpty()) {
          d.remove(v - 1);
        }
      } else {
        d.computeIfAbsent(v, k->new PriorityQueue<>()).offer(1);
      }
    }
    for (var v : d.values()) {
      if (v.peek() < 3) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isPossible(vector<int> &nums) {
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> d;
    for (int v : nums) {
      if (d.count(v - 1)) {
        auto &q = d[v - 1];
        d[v].push(q.top() + 1);
        q.pop();
        if (q.empty()) {
          d.erase(v - 1);
        }
      } else {
        d[v].push(1);
      }
    }
    for (auto &[_, v] : d) {
      if (v.top() < 3) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def isPossible(self, nums: List[int]) -> bool: d = defaultdict(list) for v in nums: if h: = d[v - 1]: heappush(d[v], heappop(h) + 1) else: heappush(d[v], 1) return all(not v or v and v[0] > 2 for v in d . values())

```