# PROBLEM LINK:

Practice : Highest Visitors

*Author:* RAKSHIT NAYAK

*Tester:* RAKSHIT NAYAK

*Editorialist:* RAKSHIT NAYAK

# DIFFICULTY:

Medium

# PREREQUISITES:

Arrays

# PROBLEM:

Nova is given the number of visitors at her local Beach Resort during New year Month on N consecutive days. The number of visitors on the i^{th} day is a_{i}.

A day has Highest visitors if it satisfies the following conditions:

- The number of visitors on the day is strictly larger than the number of

visitors on each of the previous days. - The number of visitors on the day is strictly larger

than the number of visitors on the immediate next following day(except the last day). - Also, in case of last day, if it satisfies the 1st condition, highest visitors becomes valid

Note that the very first day could have highest visitors Y by satisfying 2nd condition.

# Explanation:

Step:1 Iterate over all the elements and check if it is highest visitors day or not.

Note: To check if a[i] is a highest visitors day, we have to iterate over a[0],

a[1],…, a[i-1].

Time complexity for this operation: O(n)

Overall Time Complexity: O( n^{2})

### Optimised Approach

*Intuition*: If we can optimise step (1), then we can optimise our overall solution.

For step (1): We need to check if a[i] > { a[i-1], a[i-2],…, a[0] }, which is same as

a[i] > max(a[i-1], a[i-2],…, a[0])

For this, we will keep a variable mx, which will store the maximum value till a[i].

Then we just need to check,

a[i] > mx

a[i] > a[i+1] , { if i+1 < n }

and update mx, mx = max(mx, a[i])

Time complexity:O(n)

# SOLUTION:

## Setter's Solution

```
#include <iostream>
using namespace std;
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n + 1];
a[n] = -1;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
if (n == 1)
{
cout << " 1" << endl;
return 0;
}
int ans = 0;
int mx = -1;
for (int i = 0; i < n; i++)
{
if (a[i] > mx && a[i] > a[i + 1])
{
ans++;
}
mx = max(mx, a[i]);
}
cout << ans << endl;
return 0;
}
```

Well this was my approach, feel free to share your approach here. Suggestions are always welcomed.