Split Array into Consecutive Subsequences

Med

#0613Time: 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.1 company

Patterns

Greedy

Data structures

Array Hash Table Heap (Priority Queue)

Companies

PhonePe

Prompt

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 <= 10⁴
-1000 <= nums[i] <= 1000
nums is sorted in non-decreasing order.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

We use a HashMap where keys are the ending numbers of subsequences and values are PriorityQueues 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.

1import java.util.HashMap;2import java.util.Map;3import java.util.PriorityQueue;4 5class Solution {6    public boolean isPossible(int[] nums) {7        // Map from a number to a priority queue of lengths of subsequences ending with that number.8        Map<Integer, PriorityQueue<Integer>> tails = new HashMap<>();9 10        for (int num : nums) {11            if (tails.containsKey(num - 1) && !tails.get(num - 1).isEmpty()) {12                // Extend the shortest subsequence ending at num - 113                int length = tails.get(num - 1).poll();14                15                // Add the new extended subsequence16                tails.computeIfAbsent(num, k -> new PriorityQueue<>()).add(length + 1);17            } else {18                // Start a new subsequence of length 119                tails.computeIfAbsent(num, k -> new PriorityQueue<>()).add(1);20            }21        }22 23        // Check if all subsequences have length 3 or more24        for (PriorityQueue<Integer> pq : tails.values()) {25            if (!pq.isEmpty() && pq.peek() < 3) {26                return false;27            }28        }29 30        return true;31    }32}

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.

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public boolean isPossible(int[] nums) {6        Map<Integer, Integer> freq = new HashMap<>();7        for (int num : nums) {8            freq.put(num, freq.getOrDefault(num, 0) + 1);9        }10 11        Map<Integer, Integer> append = new HashMap<>();12 13        for (int num : nums) {14            if (freq.get(num) == 0) {15                continue; // This number has been used16            }17 18            // Case 1: Append to an existing subsequence19            if (append.getOrDefault(num, 0) > 0) {20                append.put(num, append.get(num) - 1);21                append.put(num + 1, append.getOrDefault(num + 1, 0) + 1);22            }23            // Case 2: Start a new subsequence24            else if (freq.getOrDefault(num + 1, 0) > 0 && freq.getOrDefault(num + 2, 0) > 0) {25                freq.put(num + 1, freq.get(num + 1) - 1);26                freq.put(num + 2, freq.get(num + 2) - 1);27                append.put(num + 3, append.getOrDefault(num + 3, 0) + 1);28            }29            // Case 3: Impossible to place the number30            else {31                return false;32            }33 34            freq.put(num, freq.get(num) - 1);35        }36 37        return true;38    }39}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public boolean isPossible(int[] nums) {3        // Counts of subsequences ending at prev with length 1, 2, and >=34        int ones = 0, twos = 0, longs = 0;5        int prev = Integer.MIN_VALUE;6 7        int i = 0;8        while (i < nums.length) {9            int start = i;10            int curr = nums[i];11            while (i < nums.length && nums[i] == curr) {12                i++;13            }14            int count = i - start;15 16            if (prev != Integer.MIN_VALUE && curr != prev + 1) {17                // Gap in the sequence18                if (ones != 0 || twos != 0) {19                    return false; // Short sequences cannot be extended20                }21                // Start new sequences22                ones = count;23                twos = 0;24                longs = 0;25            } else {26                // Consecutive sequence27                if (count < ones + twos) {28                    return false; // Not enough numbers to extend short sequences29                }30                31                int remaining = count - ones - twos;32                int newLongs = twos + Math.min(longs, remaining);33                int newOnes = Math.max(0, remaining - longs);34                35                longs = newLongs;36                twos = ones;37                ones = newOnes;38            }39            prev = curr;40        }41 42        // After the loop, check if there are any uncompleted short sequences43        return ones == 0 && twos == 0;44    }45}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  boolean isPossible(int[] nums) {4    Map<Integer, PriorityQueue<Integer>> d = new HashMap<>();5    for (int v : nums) {6      if (d.containsKey(v - 1)) {7        var q = d.get(v - 1);8        d.computeIfAbsent(v, k->new PriorityQueue<>()).offer(q.poll() + 1);9        if (q.isEmpty()) {10          d.remove(v - 1);11        }12      } else {13        d.computeIfAbsent(v, k->new PriorityQueue<>()).offer(1);14      }15    }16    for (var v : d.values()) {17      if (v.peek() < 3) {18        return false;19      }20    }21    return true;22  }23}

1class Solution {2public:3  bool isPossible(vector<int> &nums) {4    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> d;5    for (int v : nums) {6      if (d.count(v - 1)) {7        auto &q = d[v - 1];8        d[v].push(q.top() + 1);9        q.pop();10        if (q.empty()) {11          d.erase(v - 1);12        }13      } else {14        d[v].push(1);15      }16    }17    for (auto &[_, v] : d) {18      if (v.top() < 3) {19        return false;20      }21    }22    return true;23  }24};

1class Solution:2    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())

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  boolean isPossible(int[] nums) {4    Map<Integer, PriorityQueue<Integer>> d = new HashMap<>();5    for (int v : nums) {6      if (d.containsKey(v - 1)) {7        var q = d.get(v - 1);8        d.computeIfAbsent(v, k->new PriorityQueue<>()).offer(q.poll() + 1);9        if (q.isEmpty()) {10          d.remove(v - 1);11        }12      } else {13        d.computeIfAbsent(v, k->new PriorityQueue<>()).offer(1);14      }15    }16    for (var v : d.values()) {17      if (v.peek() < 3) {18        return false;19      }20    }21    return true;22  }23}

1class Solution {2public:3  bool isPossible(vector<int> &nums) {4    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> d;5    for (int v : nums) {6      if (d.count(v - 1)) {7        auto &q = d[v - 1];8        d[v].push(q.top() + 1);9        q.pop();10        if (q.empty()) {11          d.erase(v - 1);12        }13      } else {14        d[v].push(1);15      }16    }17    for (auto &[_, v] : d) {18      if (v.top() < 3) {19        return false;20      }21    }22    return true;23  }24};

1class Solution:2    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())

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.