#659

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Split Array into Consecutive Subsequences

Verify if it's possible to split a sorted array into consecutive subsequences of length 3 or more.

array hash table greedy heap priority queue

Problem Statement

Given a sorted integer array nums, determine whether it's possible to split nums into one or more subsequences. Each subsequence must consist of consecutive integers, with each subsequence having a length of at least 3 elements.

Return true if it's possible to split nums in this way, otherwise return false. You can use a greedy strategy along with a hash map to keep track of the subsequences and ensure they meet the required conditions.

Examples

Example 1

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

Output: true

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

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

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.

Solution Approach

Greedy Approach with Hash Map

Iterate through the sorted array and maintain a hash map to track the frequency of the elements. For each element, check if it can extend an existing subsequence or if it starts a new subsequence. If a subsequence cannot be formed, return false.

Check for Consecutive Sequences

For each element, check if it can be added to an existing subsequence. If it can’t, attempt to form a new subsequence starting from this element. If neither condition is met, return false.

Use Hash Map to Track Ends of Subsequences

Maintain a hash map where keys represent the last element of subsequences and values track the length. Update this map as you iterate through the array. If at any point, you can't extend or form a subsequence, return false.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n), where n is the length of the array, as we perform a single pass through the array. The space complexity is O(n) due to the hash map used for tracking subsequences.

What Interviewers Usually Probe

Candidate is familiar with greedy strategies and hash map usage.
Candidate shows understanding of array scanning techniques and subsequence formation.
Candidate demonstrates the ability to optimize solutions using map-based lookups.

Common Pitfalls or Variants

Common pitfalls

Not checking for valid subsequences before creating new ones.
Incorrectly updating the hash map, causing invalid subsequences.
Forgetting to handle cases where no subsequence can be formed for certain elements.

Follow-up variants

Allow subsequences of length 2 or more instead of 3.
Introduce additional constraints such as distinct integers in the array.
Alter the problem to find the smallest subsequence possible instead of focusing on consecutive subsequences.

FAQ

What is the key pattern in solving the 'Split Array into Consecutive Subsequences' problem?

The key pattern involves using a greedy approach with a hash map to track subsequences and their lengths, ensuring the conditions for consecutive subsequences are met.

Can this problem be solved without a hash map?

While it's possible to use other data structures, a hash map offers the most efficient way to track subsequences and their lengths during the greedy process.

What happens if subsequences can't be formed?

If it's impossible to extend or create a valid subsequence, the solution will return false.

How does array scanning apply in the 'Split Array into Consecutive Subsequences' problem?

Array scanning is used to check each element sequentially and determine whether it can be added to an existing subsequence or start a new one, ensuring the conditions for consecutive subsequences are met.

What are the time and space complexities for the solution?

The time complexity is O(n) because the algorithm scans through the array once, and the space complexity is O(n) due to the hash map used to track subsequences.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#632 smallest range covering elements from k lists #621 task scheduler #1054 distant barcodes