 # VISIT21-EDITORIAL

Practice

Author: RAKSHIT NAYAK
Tester: RAKSHIT NAYAK
Editorialist: RAKSHIT NAYAK

Medium

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,
a,…, 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 }, which is same as

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

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. 