DELARRAY - time complexity

Hi, isn’t this solution O(N2 ) as nested for loops make it O(prefix*suffix) which might be close to n/2 ?

If yes, did it pass due to weak test case ?
@l_returns ? @anyone ?

1 Like

order(n) per test case is accurate complexity

1 Like

I feel the correct solution’s time complexity is O(nlogn) . All you gotta do is that for every ‘i’ check if the prefix supports it…and then find the increasing part which is after i+1…in that range find the first number greater than a(i-1).
Boom.Problem Solved!

1 Like

What about my argument ?
where is it wrong ?

1 Like

Yeah, I thought something similar, after getting prefix and suffix , I thought to use lower_bound and upper_bound for each element in prefix and suffix to get nlogn. But I am amazed to see this solution !!

According to me the solution you linked is O(n) only

Yeah, but HOW ??

??? :roll_eyes::roll_eyes::thinking::thinking:

j is initalized before the outer loop so it will be traversed once from n-1 to suffix and i from prefix to 0

The writer of this solution should have used while loops instead as they are more clear in such questions.

Refer my solution-https://www.codechef.com/viewsolution/25452707

3 Likes

Hmmm. . . . .
I see now, that makes it a O(prefix+suffix) instead of O(prefix*suffix).
Great. Thanks :smile: :+1:

1 Like

welcome.

Hey Karan I tried a similar approach but was not getting AC, I can’t understand why, here is what I did-
first found the left and right boundaries, the meaning of left and right boundaries is that any subarray to be removed should atleast start and atleast end at those boundaries. For finding them I simply checked the longest strictly sorted prefix and suffix. Then for each index lying in the prefix I checked the total possible combination of suffixes using binary search/upper_bound.

1 Like

Checking your code…

1 Like

Here: https://pastebin.com/wy5nrcrh

You should submit it one time !!!

see my solution its using binary search…

https://www.codechef.com/viewsolution/25458540

Genius Sirr:sunglasses::sunglasses:

Here it is : - https://www.codechef.com/viewsolution/25464607 :slight_smile: (Simple Binary Search)
@harshraj22 may check out :stuck_out_tongue:

1 Like

O(n) solution::

Solution_DELARRAY

simple binary search 500 lines??

1 Like

Aree vo instead of calling the function…I wrote the full bs function anywhere​:joy::rofl::joy::rofl::joy: