Author: Ishank Bhardwaj
Tester: Yash Gulani
Editorialist: Ishank Bhardwaj
Find the length of the longest contiguous segment in an array, in which if
a given element K is inserted, K becomes the second largest element of
We can store the index of all the elements which are greater than K in a vector v. If we include the element at position v[i+1] from the array, then the length of this segment is v[i+2]-v[i]-1. The largest element is at position v[i] and we can insert the second largest element anywhere in the range. If all the elements had been distinct, this solution would have been passed.
Since elements can be the same, we just need a small implementation change. We can take a vector of vectors. A vector will store the index of all such elements which are equal and no other element greater than K lies on it. No the ans=max(v[i][first] - v[i-2][last] - 1) over all i. Insert indices -1 as a first vector and n is the last vector to handle edge cases in implementation. This is one way, there might be other better ways also.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.