Explain in different words please

general
1

Can someone explain the logic behind solving this problem. I can’t wrap my head around the editorial.

2

You have an array, and you want to have only one peak. You can only decrease the numbers and you need to tell whether it is possible to have only one peak.

Notice that you can decrease the numbers as much as you want, but the first number must be at least 0, the second number must be at least 1 and so on up to the peak. Also, the last element must be at least 0, making the second last number at least 1 and so on up to the peak.

Thus, you need to check, if there exist any index which satisfies both properties!

bool possible(vector<int> A)
{
     int front_max = 0, back_min = n-1;
     int n = A.size();

     // Maximum Index that Satisfies
     while(front_max<n&&A[front_max]>=front_max) front_max++;

     // Minimum Index that Satisfies
     while(back_min>=0&&A[back_min]>=n-1-back_min) back_min--;

     // Check for intersection
     if(front_max>=back_min) return true;
     else return false;
}
2 Likes
3

Wow, Thank you so much! Got it!