Scale Engineer

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
ArrayHash TableHeap (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 <= 104
  • -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.

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.

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.

Solutions

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;  }}

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 →

Next problem