Split Array into Consecutive Subsequences — Leetcode 659

Hello, Myself Gauri wankhade,
Software Developer, Bangalore, India

In this article we will be solving leetcode problem for below problem statement.

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

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.

⚡Thought process:-

To split the given array into valid subsequences, the following two operations can be performed

• Add element in existing sub-array
• Create new sub-array with current element
• If none of the above operations happening, it means array cannot be split into valid sub-arrays

⚡Solution:-

Approach -1 (Not Optimized)

Dry Run:-

⚡Code:-

⚡Complexity Analysis:-

• Time complexity:- O(N²) where N is a number of elements in given array
• Space complexity:- O(N)

Approach-2 (Optimized)

In the previous approach we were iterating over the list of sub-arrays to check if element can be added to the existing one. But we didn’t really access all elements, because to check the above condition we only need last element of sub-array.

What if we only store the last element of all previously made sub-arrays?

Since, we are trying to optimize search operation, what is the best data structure to optimize search operation —

Let’s go with the Hash table or we say Dictionary in python (If you have better suggestion, comments are welcome :P )

In the Hash table we will be storing last element of each sub array. We need one more Hash table to keep track of elements to avoid repeated operations on same element.

Dry Run

⚡ Code

⚡Complexity Analysis:-

• Time complexity:- O(N)
• Space complexity:- O(N)

Please do share and like if you find the article useful. Follow me on medium Gauri wankhade and on Twitter at gauri_infj.

Thanks!!!

Happy Learning…