Consecutive Days

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
1 upvote
Asked in company
Microsoft

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
2
5
1 5 16 17 20
5
20 15 13 9 5
Sample Output 1 :
5
5
Explanation of Sample Output 1 :
Test Case 1 :  
In the interval 1 to 5, on days 3, 4, and 5, he trains for more than 10 hours, so he will receive 3 prizes which are greater than 2 punishment.

Test Case 2 : 
In the interval 1 to 5, on days 1, 2, and 3, he trains for more than 10 hours, so he will receive 3 prizes which are greater than 2 punishment.
Sample Input 2 :
2
6
1 2 3 5 4 6
5
4 1 15 15 6
Sample Output 2 :
0
3
Hint

Try to convert the array to +1/-1 if it is greater than 10 hours or not.

Approaches (2)
Prefix Sum and Map

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’
  • Return ‘RES.’
Time Complexity

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

 

We are iterating each element of the array only once so its takes O(N) time. Hence, the overall time complexity is O(1).

Space Complexity

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

 

In the worst case, the prefix sum can be different for each index. Hence we need to store ‘N’ distinct elements. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Consecutive Days
Full screen
Console