Find pair with given difference


We have an unsorted array and a number n, Our task is to find if there exists a pair of elements in the array whose difference is n.

Example 1

Input: arr[] = {5, 20, 3, 4, 50, 40}, n = 36

Output: Pair Found: (4, 40)

 

Example 2

Input: arr[] = {90, 10, 20, 12, 50}, n = 45

Output: No Such Pair

 

Approach

  1. Create a HashSet called elementsSet to store elements from the array.
  2. Iterate through each element in the input array.
  3. For each element in the array, calculate the potential partner element by adding n to the current element.
  4. Check if the potential partner element exists in the elementsSet by using the contains method. If it does, return true because you've found a pair with the desired difference.
  5. If the potential partner element is not found in the elementsSet, add the current element to the elementsSet. This is done to keep track of elements you've seen so far.
  6. Continue this process for all elements in the array.
  7. If you reach the end of the array without finding a pair with the desired difference, return false.

 

Complexity

  • Time Complexity: O(N), where N is the number of elements in the array.
  • Space Complexity: O(N), where N is the number of elements in the array.

 

Code

#Java Code

import java.util.HashSet;

public class PairWithDifference {
    public static boolean hasPairWithDifference(int[] arr, int n) {
        if (arr == null || arr.length < 2) {
            // There must be at least two elements in the array to form a pair.
            return false;
        }

        HashSet<Integer> elementsSet = new HashSet<>();

        for (int element : arr) {
            int partner1 = element + n;
            int partner2 = element - n;

            if (elementsSet.contains(partner1)) {
                System.out.println("Pair found: (" + element + ", " + partner1 + ")");
                return true;
            } else if (elementsSet.contains(partner2)) {
                System.out.println("Pair found: (" + element + ", " + partner2 + ")");
                return true;
            }

            elementsSet.add(element);
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {5, 20, 3, 2, 50, 80};
        int n = 78;

        if (hasPairWithDifference(arr, n)) {
            System.out.println("A pair with a difference of " + n + " exists.");
        } else {
            System.out.println("No pair with a difference of " + n + " found.");
        }
    }
}
Output

Pair found: (2, 80)
A pair with a difference of 78 exists.



Thanks for feedback.



Read More....
Find the no of islands in a 2D Array/Matrix
3 Sum
4 Sum - Find four elements that sum to a given target value
Chocolate Distribution Problem
Find the missing number in a sorted array
Best Time to Buy and Sell Stock