The following is the problem. I solved it with quadratic time, but I have no idea how this can be solved within linear time.

Can someone give some explanation and the code?
Thank you