Given a sorted array x of integers in increasing order of size n, the task is to find two integers x[i] and x[j], such that a point (x[i], x[j]) lies inside a rectangle whose four vertices are mentioned.
Can anyone please share a O(n) algorithm for this? The code is not necessary.
I would grateful.
PS: I tried a lot, but didn't come up with anything linear. Also, I didn't know how to phrase it for Google search.