659. Split Array into Consecutive Subsequences

Medium

4.2K

776

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 `[`

while __1__,2,__3__,4,__5__]`[1,3,2]`

is not).

**Example 1:**

Input:nums = [1,2,3,3,4,5]Output:trueExplanation:nums can be split into the following subsequences: [,1,2,3,4,5] --> 1, 2, 3 [1,2,3,3,3,4] --> 3, 4, 55

**Example 2:**

Input:nums = [1,2,3,3,4,4,5,5]Output:trueExplanation:nums can be split into the following subsequences: [,1,2,3,3,4,4,5] --> 1, 2, 3, 4, 5 [1,2,3,5,4,3,5,4] --> 3, 4, 55

**Example 3:**

Input:nums = [1,2,3,4,4,5]Output:falseExplanation:It is impossible to split nums into consecutive increasing subsequences of length 3 or more.

**Constraints:**

`1 <= nums.length <= 10`

^{4}`-1000 <= nums[i] <= 1000`

`nums`

is sorted in**non-decreasing**order.

Accepted

123.5K

Submissions

243.1K

Acceptance Rate

50.8%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved