PROBLEM LINK
Problem link for practice can be found here.
DIFFICULTY
Medium
PREREQUISITE
Greedy, Optimization
PROBLEM
You’re given the no. of buyers at his shop on N consecutive days. The number of buyers on the i -th day is B i . A day is record braking if it satisfies both of the following conditions:
- The number of buyer on the day is strictly larger than the number of buyers on each of the previous days.
- Either it is the last day, or the number of buyers on the day is strictly larger than the number of byers on the following day.
Find the number of record breaking days.
EXPLANATION
ANALYSIS
We can check whether the current element is the last element and, if not, if it is greater than the next element in constant time. To check whether i is a record breaking day, we also need to check whether the number of visitors of day i is greater than number of buyers from all the previous days.
BASIC APPROACH
For each element j such that (1 <= j < i), check that the number of buyers on day j are less than number of buyers on day i. Hence, for each day we would compare it with all the previous days and it would take O( N ) time. Therefore, for N days, the time complexity of this solution would be O( N ^2).
OPTIMIZED APPROACH
However that wouldn’t be fast enough for Test Set 2, so we need a faster approach. Instead of comparing the number of buyers of day i against all the previous days one by one, we can compare the number of buyers of day i against the greatest number of buyers from all previous days. That reduces our processing time for each day from O( N ) to O(1). Therefore, for N days, the time complexity of this solution would be O( N ), which is sufficiently fast for big Test cases.
SOLUTION
Solution of this problem can be found here.