Last Updated: 6 Apr, 2021
Split Array Into Increasing Subsequences
Easy
Asked in companies
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.
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
Approaches
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.
The main idea is to check the subsequence of length 1 and length 2 and if they are the only subsequences that can be formed for a given number then return ‘false’ else return true.
- If numbers are not continuous, check for each segment.
- Count frequency of each continuous number. Note the value of numbers doesn't matter because we subtract the base value therefore the segmentation fault is not caused.
- Use parameter "ones" for subsequences with length 1 ending with index ‘i’, "twos" for subsequences with length 2 ending with index ‘i’.
- When processing the next number, if the frequency of the new number freq[i] < ones+twos, there is no way to split, return false. If it is possible to split, ones and twos would be 0 by the end of the loop.
- When we exit the loop it means we can always split the sequence, hence return true.