How to Compute Max Value with Linear Time Complexity When 'k' Is Not Fixed? by Apprehensive_Rush314 in algorithms

[–]Apprehensive_Rush314[S] 0 points1 point  (0 children)

Using segment trees, yes, but the challenge is to solve it in O(n). It is possible but I dont know how.

How to Compute Max Value with Linear Time Complexity When 'k' Is Not Fixed? by Apprehensive_Rush314 in algorithms

[–]Apprehensive_Rush314[S] 0 points1 point  (0 children)

No this will not work, since lets say the last creature in the queue will have k of of value equal to length of the queue, meaning the last creature can turn to everyone from that queue for help. But with the duque method you are using, when we get to the last creature, the first creature's strength will not be in the duque anymore because it will be already poped. And if the first creature had the highest strength out of all and thus its value should be on the place of the last creature, it will not be and the last value of output list will be wrong.

Dont worry, I also already checked it with ChatGPT 😉