Convert a $O(n^2)$ algorithm to $O(n)$

Question

Currently following a discrete mathematics course. I'm facing an issue, I need to write an algorithm of $O(n)$ complexity.

Here's what it needs to do :

Consider $k$ a natural integer and $T[]$ an array containing natural numbers in ascending order. The function needs to return true if there's two elements (can be the same) in $T[]$ as : $\lvert T[i] + T[j] - k \rvert \leq 2$

I tried writing it fast, just to see what I had first in mind. Here's what I wrote (pseudo-code)

myFct(int k, int[] T) 
    for i = 0 to T.count
        for j = i to T.count
            if(math.abs(T[i] + T[j] - k) <= 2)
                return true;
    return false;

Problem is, since there are $2$ loops, we face a $O(n^2)$ algorithm. In the question, it is asked to write a $O(n)$ algorithm.

Was wondering if any of you could give me tips on how to do this. I suspect the natural integers in ascending order is important in this case to realize this, but I'm getting short on time.

Thank you very much.

EDIT : Partially solved since I'm not sure if the new algo is $O(n)$, see my answer down the page.

Answer 1

Consider the subproblem of determine if the array has $(i, j)$ such that $0 \le (T[i] + T[j] - k) \le 2$; that is, $k \le T[i] + T[j] \le 2 + k$. Look at the following table for an example algorithm with input $\{a, b, c, d\}$:

$$\begin{array} {c|cccc} & 0 & 1 & 2 & 3 \\ \hline 0 & a + a & a + b & a + c & a + d \\ \hline 1 & b + a & b + b & a + c & b + d \\ \hline 2 & c + a & c + b & a + c & c + d \\ \hline 3 & d + a & d + b & a + c & d + d \\ \hline \end{array}$$

If that table were a height map, it would slope up from the bottom left to the top right.

So for any given column, you should be able to find the first row $s$ at least as large as $k$ and the last row $t$ no larger than $2 + k$. If $s \le t$ then you found a solution. If not, find the $s,t$ of the next row. Note that you can use the $s,t$ of the previous row to make the search faster.

Answer 2

I finally found a solution, even though I think it could be optimised. I had to hand over my assignment so I stopped working on it when it passed the tests. Keep in mind that it could contain an error since I did not test it thoroughly.

I based my algorithm on the answer of DanielV and the solution presented here : https://www.geeksforgeeks.org/count-pairs-array-whose-sum-less-x/?fbclid=IwAR16ldV-dgX-ajbGqwcfNDher9IxEI7zFNeT3isNy2ousMA1muusZthwHAY
I tried to explain it as simple as possible. It is not a formal proof that the algorithm is working, but is in my opinion a lot easier to understand (note that it was not mentioned to prove anything in the question).

It is all explained in the code. There's one function with comments, explanation and console output to understand better and another one below containing only the code : https://dotnetfiddle.net/ZLWhgk

If anybody tries to access this and it's not working, please advise me. I keep a copy on my computer.

Here's the final code without explanations (second function on dotnetfiddle) :

bool myFct(List<int> T, int k) {
    int i = 0;
    int r = T.Count - 1;
    while (i <= r) {
        if (Math.Abs(T[i] + T[r] - k) <= 2) return true;
        if (T[i] <= k + 2) {
            if (T[r] >= k)
                r--;
            else
                i++;
        }
        else
            r--;
    }
    return false;
}