Split Array Into Consecutive Subsequences - Leetcode Solution

Problem Statement:

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 each subsequence consists of consecutive integers and has length at least 3.

Example:

Input: nums = [1,2,3,3,4,5] Output: true

Input: nums = [1,2,3,3,4,4,5,5] Output: true

Input: nums = [1,2,3,4,4,5] Output: false

Solution:

We can loop through the array and for each number, check if we can add it to a sequence that has already started. If we can't find an existing sequence, we create a new one.

We can use two hashmaps to keep track of the number of available sequences that end at the current number and the number of available sequences that are one number less than the current number.

After we process all the numbers in the array, we check if there are any sequences that have less than three numbers.

Here is the implementation of the above approach in Python:

def isPossible(nums): count_map = {} for n in nums: if n in count_map: if count_map[n-1] > 0: count_map[n-1] -= 1 count_map[n] = count_map.get(n, 0) + 1 elif count_map.get(n, 0) == 0 or count_map.get(n+1, 0) == 0: return False else: count_map[n] = count_map.get(n, 0) + 1 count_map[n+1] -= 1 else: if count_map.get(n, 0) == 0 or count_map.get(n+1, 0) == 0 or count_map.get(n+2, 0) == 0: return False else: count_map[n] = count_map.get(n, 0) + 1 count_map[n+1] -= 1 count_map[n+2] -= 1 return True

Time Complexity:

The time complexity of this approach is O(n) because we only loop through the array once.

Space Complexity:

The space complexity of this approach is also O(n) because we use two hashmaps to keep track of the available sequences.

1