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).

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
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.

Solution

Method 1 - Using Hashing

Intuition

The main idea is to use two hash maps: one (freq) to count the remaining occurrences of each number, and another (end) to track how many subsequences end at a given number. For each number, we try to append it to an existing subsequence ending at num-1 (by checking end[num-1]), or start a new subsequence with num, num+1, num+2 (by checking freq[num+1] and freq[num+2]). If neither is possible, we return false. This greedy approach ensures all subsequences are at least length 3 and consecutive.

Approach

  1. Count the frequency of each number in nums using a hash map freq.
  2. Iterate through nums:
    • If freq[num] == 0, continue (already used).
    • If there is a subsequence ending at num-1 (end[num-1] > 0):
      • Decrement end[num-1] and increment end[num].
    • Else, if freq[num+1] > 0 and freq[num+2] > 0:
      • Use num, num+1, num+2 to start a new subsequence, decrement their frequencies, and increment end[num+2].
    • Else, return false.
    • Always decrement freq[num] after using it.
  3. If all numbers are used successfully, return true.

Dry Run

Let’s dry run the algorithm for nums = [1,2,3,3,4,5]:

  • Initial freq: {1:1, 2:1, 3:2, 4:1, 5:1}, end: {}
  • Process 1: No subsequence to extend, can start new with 2,3. Use 1,2,3. Update: freq: {1:0, 2:0, 3:1, 4:1, 5:1}, end: {3:1}
  • Process 2: Already used.
  • Process 3: Can extend subsequence ending at 2 (none), can start new with 4,5. Use 3,4,5. Update: freq: {1:0, 2:0, 3:0, 4:0, 5:0}, end: {3:1, 5:1}
  • All numbers used, return True.

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums, since each number is processed at most twice.
  • 🧺 Space complexity: O(n), for the hash maps storing frequencies and subsequence ends.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> freq, end;
        for (int num : nums) freq[num]++;
        for (int num : nums) {
            if (freq[num] == 0) continue;
            if (end[num - 1] > 0) {
                end[num - 1]--;
                end[num]++;
            } else if (freq[num + 1] > 0 && freq[num + 2] > 0) {
                freq[num + 1]--;
                freq[num + 2]--;
                end[num + 2]++;
            } else {
                return false;
            }
            freq[num]--;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
	public boolean isPossible(int[] nums) {
	    Map<Integer, Integer> freq = new HashMap<>();
	    Map<Integer, Integer> end = new HashMap<>();
	    for (int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);
	    for (int num : nums) {
	        if (freq.get(num) == 0) continue;
	        if (end.getOrDefault(num - 1, 0) > 0) {
	            end.put(num - 1, end.get(num - 1) - 1);
	            end.put(num, end.getOrDefault(num, 0) + 1);
	        } 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);
	            end.put(num + 2, end.getOrDefault(num + 2, 0) + 1);
	        } else {
	            return false;
	        }
	        freq.put(num, freq.get(num) - 1);
	    }
	    return true;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def isPossible(self, nums: list[int]) -> bool:
        freq: dict[int, int] = {}
        end: dict[int, int] = {}
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
        for num in nums:
            if freq[num] == 0:
                continue
            if end.get(num - 1, 0) > 0:
                end[num - 1] -= 1
                end[num] = end.get(num, 0) + 1
            elif freq.get(num + 1, 0) > 0 and freq.get(num + 2, 0) > 0:
                freq[num + 1] -= 1
                freq[num + 2] -= 1
                end[num + 2] = end.get(num + 2, 0) + 1
            else:
                return False
            freq[num] -= 1
        return True

Method 2 - Without Using Extra Space

Intuition

Instead of using hash maps, we can use pointers and counters to track the lengths of possible subsequences as we scan through the sorted array. By grouping identical numbers and counting how many new subsequences can be started or extended, we can greedily ensure all subsequences are at least length 3. This approach leverages the sorted property of the array and only uses a constant number of variables for each group.

Approach

  1. Use pointers to scan through nums and group identical numbers, counting their frequency (cnt).
  2. Track the number of subsequences ending with lengths 1 (prev1), 2 (prev2), and 3+ (prev3) for the previous number.
  3. For each group of the current number:
    • If the current number is not consecutive to the previous, all previous subsequences must be of length 3 or more (prev1 == 0 && prev2 == 0).
    • Calculate how many subsequences can be extended and how many new ones must be started.
    • If not enough numbers to extend all previous subsequences of length 1 or 2, return false.
    • Update counters for the next iteration.
  4. After processing all numbers, ensure no subsequence of length less than 3 remains.

Dry Run

For nums = [1,2,3,3,4,5]:

  • Group 1: cnt=1, start 1 subsequence of length 1
  • Group 2: cnt=1, extend previous length 1 to length 2
  • Group 3: cnt=2, extend previous length 2 to length 3, start 1 new subsequence of length 1
  • Group 4: cnt=1, extend previous length 1 to length 2
  • Group 5: cnt=1, extend previous length 2 to length 3
  • All subsequences are length 3 or more, return True

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums, as we scan the array once.
  • 🧺 Space complexity: O(1), only a constant number of counters are used.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        int n = nums.size(), i = 0;
        int prev = INT_MIN, prev1 = 0, prev2 = 0, prev3 = 0;
        while (i < n) {
            int curr = nums[i], cnt = 0;
            while (i < n && nums[i] == curr) {
                cnt++; i++;
            }
            int c1 = 0, c2 = 0, c3 = 0;
            if (curr != prev + 1) {
                if (prev1 > 0 || prev2 > 0) return false;
                c1 = cnt;
            } else {
                if (cnt < prev1 + prev2) return false;
                c2 = prev1;
                c3 = prev2 + min(prev3, cnt - prev1 - prev2);
                c1 = cnt - c2 - c3;
            }
            prev = curr;
            prev1 = c1; prev2 = c2; prev3 = c3;
        }
        return prev1 == 0 && prev2 == 0;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
	public boolean isPossible(int[] nums) {
	    int n = nums.length, i = 0;
	    int prev = Integer.MIN_VALUE, prev1 = 0, prev2 = 0, prev3 = 0;
	    while (i < n) {
	        int curr = nums[i], cnt = 0;
	        while (i < n && nums[i] == curr) {
	            cnt++; i++;
	        }
	        int c1 = 0, c2 = 0, c3 = 0;
	        if (curr != prev + 1) {
	            if (prev1 > 0 || prev2 > 0) return false;
	            c1 = cnt;
	        } else {
	            if (cnt < prev1 + prev2) return false;
	            c2 = prev1;
	            c3 = prev2 + Math.min(prev3, cnt - prev1 - prev2);
	            c1 = cnt - c2 - c3;
	        }
	        prev = curr;
	        prev1 = c1; prev2 = c2; prev3 = c3;
	    }
	    return prev1 == 0 && prev2 == 0;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def isPossible(self, nums: list[int]) -> bool:
        n = len(nums)
        i = 0
        prev = float('-inf')
        prev1 = prev2 = prev3 = 0
        while i < n:
            curr = nums[i]
            cnt = 0
            while i < n and nums[i] == curr:
                cnt += 1
                i += 1
            c1 = c2 = c3 = 0
            if curr != prev + 1:
                if prev1 > 0 or prev2 > 0:
                    return False
                c1 = cnt
            else:
                if cnt < prev1 + prev2:
                    return False
                c2 = prev1
                c3 = prev2 + min(prev3, cnt - prev1 - prev2)
                c1 = cnt - c2 - c3
            prev = curr
            prev1, prev2, prev3 = c1, c2, c3
        return prev1 == 0 and prev2 == 0