VISIT21-EDITORIAL

editorial
, ,
1

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. :smile: