educative.io

Is it correct to exclude the pivot element

Courses
,
#1

Hi @Design_Gurus. In the top down solution, when we Find LDS starting from ‘i’ to the end of the array
and then Find LDS starting from ‘i’ to the beginning of the array, we try to find the LDS by excluding the pivot element. This can create a solution where the length from the scan to the left include the pivot element but the scan to the right needed the pivot element excluded.

I’m thinking we should always include the pivot element when finding LDS (when prevIndex==-1). Is this thinking correct or am I missing something?

Take for e.g. the input 4,2,3,6,10,15,14,2,1 at pivot 10. Left scan will return 4 including 10 & right will return 4 excluding 10. Is it meaningful to sum the two together. We cant have one output that both includes and excludes 10.

Also, the output for 1,2,3,10 is 4, which is incorrect. It should be 0 or 3. Would we consider that an invalid input since it has no bitonic sequence?

#2

Hi Rowan,

Thank you for reaching out to us and giving your feedback. We’ll get back to you soon!

If you have any further concerns/questions/comments, please let us know.

Best regards,
Educative Team

#3

Hi @Rowan_Alex,

In all solutions, we always consider the solution including the pivot element for both LDS and LDS-reverse. Probably you are getting confused as we try both option i.e., including/excluding each element and then taking the one that gives higher length.

For reference, following line in findLDSLength() includes the pivot element:

c1 = 1 + findLDSLength(dp, nums, currentIndex+1, currentIndex);

And similarly following line in findLDSLengthReverse(), includes the pivot element:

c1 = 1 + findLDSLengthReverse(dp, nums, currentIndex-1, currentIndex);

Let us know if you have more questions.

For [1,2,3,10], the LBS should be 4 as all four elements constitute an increasing sequence.

Hope this answered your questions.