Diffk

Given an array ‘A’ of sorted integers and another non negative integer k, find if there exists 2 indices i and j such that A[i] - A[j] = k, i != j.

    A : [1 3 5] 
    k : 4

Return 0 / 1 ( 0 for false, 1 for true ) for this problem

Try doing this in less than linear space complexity.

Method:

We start from the first two numbers, say left (index 0) and right (index 1). if the diff between them is too small, then we have to increase right.
This is true no matter where left is, because if we have already tried (left - 1, right) in previous iteration. If the diff is too big, then we increase left, note that if left == right, then we need to increase right as well.

Solution:

Time: O(n)
Space: O(1)

public class Solution {
    public int diffPossible(ArrayList<Integer> A, int B) {
        if (A.size() < 2) return 0;
        int left = 0;
        int right = 1;
        while (right < A.size() && left < right) {
            int diff = A.get(right) - A.get(left);
            if (diff == B) {
                return 1;
            } else if (diff > B) {
                left ++;
                if (right - left == 0) {
                    right ++;
                }
            } else {
                right ++;
            }
        }
        return 0;
    }
}