SLAEL - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice 
Contest

Author: Ishank Bhardwaj

Tester: Yash Gulani

Editorialist: Ishank Bhardwaj

DIFFICULTY:

EASY

PROBLEM:

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
that subarray.

EXPLANATION:

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.

1 Like
2

We can scan the array once only, tracking how long the current valid segment is (and where the last element >k is in the segment). Each time a new element > k is encountered, check whether the existing segment is > max length and reset for the new segment, retaining the length since the old {>}k value.

My Python code

3

I used the sliding window technique, Can someone point out where I am wrong ?

My Solution

4

There is an edge case that the test cases do not catch, when none of the provided array of values are greater than k - then there is no possible region of the array that meets the conditions and I think the correct output is 0. My previous code did not check for this.

updated code

5

You don’t handle the transition from a multiple-peak zone correctly:

1
9 3
2 4 2 4 2 6 2 1 2

should give answer 5.

1 Like