Split Array Into Increasing Subsequences

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
OlaAckoAdobe

Problem statement

You are given an integer array/list ‘ARR’ of size 'N' that is sorted in ascending order. Your task is to return '1' if and only if you can split it into one or more increasing subsequences such that each subsequence consists of consecutive integers and has a length of at least 3. Else, return '0'.

Note: An increasing sequence is a sequence where the difference between ith and i + 1th number is 1 exactly. For example : 1, 2, 3, 4 or 3, 4, 5 or -1, 0, 1 are all increasing subsequences.

For example:

Given ‘N’ = 4 and ‘ARR’[] = 1, 2, 3, 4.
The answer will be ‘1’ because an increasing subsequence of [1, 2, 3, 4]  having length greater than 3 can be made.
Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer 'N', where ‘N’ is the number of elements of the array/list 'ARR'.

The second line of each test case contains ‘N’ single space-separated integers, denoting the 'ARR' elements.

Output format:

For each test case, print a single line containing '1' if you can split 'ARR' into one or more subsequences such that each subsequence consists of consecutive integers and has a length of at least 3. Else, print '0'.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <=  N <= 5000
-1250 <= ARR[ i ] <= 1250

Where ‘T’ is the total number of test cases, and 'N’ is the length of 'ARR' and ‘ARR[i]’ is the array element at index ‘i’.

Time limit: 1 second

Sample Input 1:

2
4
1 2 3 4
3
1 2 2

Sample Output 1:

1
0

Explanation of the Sample Input 1:

For the first test case:
The answer will be 1 (true) because an increasing subsequence of [1, 2, 3, 4] can be made.

For the second test case:
The answer will be 0 (false) and this is because no valid increasing subsequence of length greater than 3 can be formed.

Sample Input 2:

2
4
-1 0 1 2
6
-2 -1 0 7 8 9

Sample Output 2:

1
1
Hint

Can we keep track of the next element we need in a subsequence?

Approaches (2)
Using Hash Map

The main idea is to maintain two hash-maps ‘frqMap’ and ‘seqMap’, which keep track of the frequency of each element in the array, and the following number that the sequence formed may need, respectively.

  • For each element in the array, update the ‘frqMap.’
  • Traverse the array and for each element, check if it can be added to some pre-existing sequence:
    • If it can be added, then reduce the count of sequences that needed the current element by 1.
    • Increase the count of the sequence that needs an element greater than the current by 1:
      • seqMap[element] -= 1.
      • seqMap[element + 1] += 1.
      • frqMap[element] -= 1.
  • If there is no such sequence where the current element can be added then try to make a sequence with the current element :
    • Check if the frequency of the current element, current element + 1, and current element + 2  and greater than 0.
    • If yes, then reduce all three elements frequency by 1 and add 1 to the sequence that needs element + 3
      • seqMap[element + 3] += 1.
      • frqMap[element] -= 1.
      • frqMap[element + 1] -= 1.
      • frqMap[element + 2] -= 1.
  • If no such sequence can be formed, return false.
  • If we can make a sequence from all numbers or add them to some already made sequence, then return true.
Time Complexity

O(N), where ‘N’ is the length of the given array.

 

We have to array twice; therefore, the net time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the length of the given array.

 

Since we are using any extra space to keep track of the elements, net space complexity will be O(N).

Code Solution
(100% EXP penalty)
Split Array Into Increasing Subsequences
Full screen
Console