Last Updated: 25 Apr, 2021
Consecutive Days
Moderate
Asked in company
Ninja is very serious about his training. He always gives himself some prize if he can train for more than 10 hours per day/ If he is unable to train for more than 10 hours, then he punishes himself.
Given a list of hours 'HOURS' of training for ‘N’ consecutive days, Ninja wants to know which is the longest interval in which he got more prizes than punishment.
As Ninja is busy in training, help him find the longest segment.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains a single integer ‘N’ denoting the size of the array.
The second line of each test case contains ‘N’ space-separated integers denoting the number of hours of training.
Output Format :
For each test case, print the length of the longest possible subarray where each day Ninja would get a prize.
The output of each test case will be printed in a separate line.
Constraints :
1 <= T <= 5
1 <= N <= 5000
1 <= HOURS[ i ] <= 24
Where ‘T’ is the number of test cases, ‘N’ is the number of days, and ‘HOURS[ i ]’ is training hours on the i’th day.
Time limit: 1 second.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
The idea here is that we will first convert the array in only +1 if the number of hours is greater than 10 and -1 if not.
Then we will find the maximum length subarray with the positive-sum, which we can achieve by storing prefix sum.
We know that if the prefix sum till i’th day is positive, then the maximum length subarray is ‘i + 1’(in 0-based indexing).
Now, if for any pair (i, j) PREFIXSUM[ i ] - PREFIXSUM[ j ] >= one, then it is a valid pair, and to maximize this, we will find the first occurrence of ‘j’.
Algorithm:
- Declare two variable 'THRS’ := 0 and ‘RES’ := 0.
- Declare a map of int, int ‘FIRSTOCC.’
- Traverse the array using ‘i’ from 0 to ‘HOURS’.size:
- If(HOURS[ i ] > 10)
- THRS += 1
- Else
- THRS -= 1
- If ‘THRS’ is greater than 0 than ‘RES’ := ‘i’ + 1.
- If ‘THRS - 1’ is present in the map:
- ‘RES’ = max(‘RES’, i - FIRSTOCC[THRS - 1])
- If ‘THRS’ is not present in the map:
- Set FIRSTOCC[THRS] := ‘i’
- If(HOURS[ i ] > 10)
- Return ‘RES.’
The idea here is to use stack data structure and prefix sum of the array to find a valid pair.
We know (i, j) is a valid pair if PREFIXSUM[ j ] - PREFIXSUM[ i ] >= 1 and j > i. Our goal is to optimise j-i over all pairs of (i, j).
- First, we will fix ‘j’ and minimize ‘i’. Let us suppose we have two i1 and i2 where i1 < i2 then (i2, j) is not an optimal pair because (i1, j ) is longer than (i2, j). So we will make a monotonic decreasing stack to find all the optimal pairs.
- Second, we will fix ‘i’ and optimize ‘j’. Now assume we have 3 indexes as i < j1 < j2 then if PREFIXSUM[ j2 ] - PREFIXSUM[ i ] >= 1 then j1 is not a valid candidate or say optimal answer. From this observation we can tell that we can iterate from backward and if we find a valid pair where PREFIXSUM[ j ] - PREFIXSUM[ i ] >= 1 then we can pop this i.
Algorithm:
- Declare an array 'PREFIXSUM’ and a variable ‘RES’ := 0.
- Traverse the array ‘HOURS’ using ‘i’ from 0 to ‘HOURS’.size:
- If( HOURS[ i ] > 10 )
- PREFIXSUM[i + 1] = 1 + PREFIXSUM[ i ]
- Else
- PREFIXSUM[i + 1] = PREFIXSUM[ i ] - 1
- If( HOURS[ i ] > 10 )
- Now iterate through PREFIXSUM from beginning to end and build a strictly monotonic decreasing stack ‘MYSTACK’ so that the top element is the smallest prefix sum.
- Again iterate PREFIXSUM from end to begin using ‘j’:
- Repeat the steps until either ‘MYSTACK’ is not empty or PREFIXSUM[MYSTACK.top] < PREFIXSUM[j].
- RES = max(RES, j - MYSTACK.top)
- MYSTACK.pop
- Repeat the steps until either ‘MYSTACK’ is not empty or PREFIXSUM[MYSTACK.top] < PREFIXSUM[j].
- Return RES.