Find pair with given difference K in the array

Given an array A of integers and another non-negative integer K, find if there exist 2 indices i and j such that A[i] – A[j] = K, i != j.

Example

Input : A : [1 5 3] k : 2 Output : 1 as 3 – 1 = 2

Return 1 if such pair exists or 0 if no pair found.

Solution

The problem can be solved with Hashing. We can maintain HashSet for the visited elements. While iteration we can do a lookup in visited HashSet for the current element with current_element + K and current_element – K, if we found such element present in Visited HashSet means we have pair present which satisfies A[i] – A[j] = K.

Code


import java.util.*;

public class DiffKII {

	public static void main(String[] args) {

		Integer a[] = { 1,5,3 };
		int K=2;
		System.out.println(new DiffKII().diffPossible(Arrays.asList(a), K));

	}

	public int diffPossible(final List<Integer> a, int K) {
		HashSet<Integer> visitedSet = new HashSet<Integer>();
		for (Integer number : a) {
			
			//Do look up in previously visited element.
			if (visitedSet.contains(number + K) || visitedSet.contains(number - K))
				return 1;
			
			//Maintaining Visited Element Set
			visitedSet.add(number);
		}
		return 0;
	}
}