Array contains elements that differ by K correctness proof

Question

I have been puzzling over an algorithm that decides whether a sorted array of numbers contains two numbers that differ by k. I do not intuitively understand why this algorithm works, or what thought process might have led me to think of this algorithm on my own, although I believe that I can prove it's correctness.

CONTAINS_DIFFK(arr, k)
    n = size(arr)
    if n == 1 return false
    i = 1
    j = 2
    while i <= n and j <= n
        if i != j and arr[j] - arr[i] == k
            return true
        if arr[j] - arr[i] < k
            j++
        else
            i++
    return false

My questions are:

1. Is the following proof sound
2. Is there a more concise way to prove correctness?
3. What thought process might have lead me to derive this algorithm on my own? (I had to look up the solution)

Proof by Induction

Let arr be an arbitrary sorted array of integers of length n. Assume for the sake of induction that CONTAINS_DIFFK return true if arr contains two numbers which differ by k and false otherwise. Let arr' be an arbitrary sorted array formed by adding a single arbitrary integer to the end of arr. We prove that CONTAINS_DIFFK return true if arr' contains two numbers which differ by k and false otherwise.

Assume that it is the case that arr contains two elements that differ by k. By our inductive assumption, CONTAINS_DIFFK will return true for arr. Because CONTAINS_DIFFK immediately returns after finding two elements that differ by k without considering further elements, and the first n elements of arr and arr' are identical, the n+1'th element of arr' will not be considered and will not affect the output of the algorithm. Thus CONTAINS_DIFFK returns true for input arr'.

Therefore we need only consider the case, which is now assumed, in which arr did not already contain two elements which differ by k. We must consider the cases in which the n+1'th element of arr' does not differ from any of the first n elements by k and the case in which it does.

First, consider the case in which the n+1'th element of arr' does not differ from any of the first n elements of arr'. We show that the algorithm returns false. Let i' be the value of i when j is incremented to be equal to n+1. Note that i' <= n. Now simply note that the last element of arr' will be compared to some subset of the elements after and including the i'th element. Since we assumed that the last element of arr' does not differ from any element by k, the condition for returning true will never be met and false will be returned.

Finally, we consider the case in which there exists some element e in arr which differs by k from the n+1'th element of arr', and show that the algorithm returns true. Again, let i' be the value of i when j is incremented to n+1 while processing arr. Now, critically, note that j was incremented to n+1 because arr[n] - arr[i'] < k. If we note also that arr'[n+1] >= arr'[n] (because it is sorted) and arr'[n+1] - e = k, then we may derive e > arr[i']. Thus, we note that i will be increased from i' up to the index of e at which point CONTAINS_DIFFK will return true as desired.

Base case

Let arr be an arbitrary sorted array of two integers. We may trace through the execution of this algorithm and note that if arr[2] - arr[1] then it will return true and it will return false otherwise. Thus, the induction is complete.

Answer 1

My line of thought for deriving this algo:

• there is well-known Merge algo (part of Merge Sort) combining two sorted arrays
• we can modify it to output only equal elements of arrays (i.e. producing intersection instead of union)
• we can further modify it to return true on the first match, and false at the end
• and finally, we can modify it to compare elements with given offset k

I suggest you to practice developing algos at leetcode or similar site, it will allow you to come up with similar solutions in a few minutes.

Answer 2

Your proof attempt is a bit hard to follow. Here is an alternative proof.

First note that we have to assume that $k \geq 0$. Indeed, if $k < 0$ then the algorithm fails on the array $k,0$ since the only solution is $(i,j) = (2,1)$, but $j \geq 2$ throughout the algorithm.

Denote by $i,j$ the values of $i,j$ at the beginning of an iteration, and by $i',j'$ their values at the end of the iteration. Define $$P(i,j) := \exists I \in [i,n], J \in [j,n] \text{ such that } I < J \text{ and } arr[J]-arr[I] = k.$$

Lemma 1. If $P(i,j)$ holds then either $arr[j] - arr[i] = k$ or $P(i',j')$.

Proof. Let $I,J$ be the indices whose existence is promised by $P(i,j)$. We consider several cases:

1. $arr[j] - arr[i] = k$. In this case, the lemma clearly holds.
2. $arr[j] - arr[i] < k$, and so $i' = i$, $j' = j+1$. In this case, $arr[j] - arr[I] \leq arr[j] - arr[i] < k$, and so $J > j$. Therefore $P(i',j')$ holds.
3. $arr[j] - arr[i] > k$, and so $i' = i+1$, $j' = j$. In this case $arr[J] - arr[i] \geq arr[j] - arr[i] > k$, and so $I > i$. Therefore $P(i',j')$ holds.

$\square$

Lemma 2. If there exist indices $I < J$ such that $arr[J] - arr[I] = k$ and the algorithm halts then it returns true.

Proof. The proof is by contradiction. Suppose that there exist indices $i < j$ such that $arr[j] - arr[i] = k$, but the algorithm never returns true. Denoting by $i_t,j_t$ the values of $i,j$ after $t$ iterations, we will show by induction that $P(i_t,j_t)$ always holds, and so the algorithm doesn't stop after $t$ iterations (since $P(i,j)$ is clearly false if $i > n$ or $j > n$); in particular, it never halts.

Clearly $I \geq 1$ and $J \geq I+1 = 2$, and so $P(i_0,j_0) = P(1,2)$ holds. Suppose now that $P(i_t,j_t)$ holds. Since the algorithm never returns true, necessarily $arr[j_t]-arr[i_t] \neq k$. Lemma 1 therefore implies that $P(i_{t+1},j_{t+1})$. $\quad \square$

Lemma 3. The algorithm always halts.

Proof. Suppose that the algorithm never returns true. In each step, $i+j$ increases by $1$. Initially, $i+j = 3$. If the algorithm continues for $2n$ iterations without stopping, then at the end of the $2n$'th iteration, $i+j = 2n+3$, which implies that either $i > n$ or $j > n$, and so the algorithm would exit the loop and return false. $\quad \square$

Theorem 4. The algorithm is correct: it always halts, and it returns true iff there exist indices $i < j$ such that $arr[j] - arr[i] = k$.

Proof. Lemma 3 shows that the algorithm always halts. If it returns true, then clearly $arr[j] - arr[i] = k$ and $j \neq i$. If $k > 0$ then necessarily $j > i$, and if $k = 0$ then $arr[j] - arr[i] = arr[i] - arr[j] = k$, and either $i < j$ or $j < i$.

Conversely, if there exist indices $i < j$ such that $arr[j] - arr[i] = k$ then Lemma 2 (in conjunction with Lemma 3) shows that the algorithm returns true. $\quad\square$

---

Finally, you ask what thought process would lead you to derive this algorithm. When the algorithm was first designed, it must have been a stroke of inspiration. Nowadays, most computer scientists are aware of this algorithm, so if there is any other algorithmic problem with a similar solution, computer scientists would come up with this kind of algorithm by analogy.

In other words, the way you would come up with this kind of algorithm is by being aware of a similar algorithm for a similar problem. The more algorithms you know, the more algorithmic tasks you will be able to solve.