Find a pair with a given difference

Problem Statement

Given an unsorted array and a number n, find a pair of elements (a, b) whose difference is n. Return true if such a pair exists, false otherwise.

Constraints:

• Array elements can be positive, negative, or zero
• The difference can be positive, negative, or zero

Example:

• Input: arr = [5, 20, 3, 2, 50, 80], n = 78
• Output: true (pair: 80, 2 with difference 78)

Example 2:

• Input: arr = [90, 70, 20, 80, 50], n = 45
• Output: false (no such pair exists)

Approach 1: Brute Force (Two Loops)

Intuition

Check all possible pairs and see if their difference equals n.

Algorithm

1. For each element at index i
2. Check all elements at index j > i
3. If |arr[i] - arr[j]| == n, return true
4. Return false if no pair found

public class Solution {
    public boolean findPair(int[] arr, int n) {
        int size = arr.length;
        
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (Math.abs(arr[i] - arr[j]) == n) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    public int[] findPairElements(int[] arr, int n) {
        int size = arr.length;
        
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (Math.abs(arr[i] - arr[j]) == n) {
                    return new int[]{arr[i], arr[j]};
                }
            }
        }
        
        return null;
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Nested loops
• Space Complexity: O(1) - No extra space

Approach 2: Using HashSet

Intuition

For each element x, check if x + n or x - n exists in the set.

Algorithm

1. Add all elements to a HashSet
2. For each element x:
   • If x + n exists in set, found pair (x, x+n)
   • If x - n exists in set, found pair (x-n, x)
3. Handle n = 0 case separately (need duplicates)

import java.util.*;

public class Solution {
    public boolean findPairHashSet(int[] arr, int n) {
        Set<Integer> elements = new HashSet<>();
        for (int x : arr) {
            elements.add(x);
        }
        
        // Special case: n = 0
        if (n == 0) {
            Map<Integer, Integer> count = new HashMap<>();
            for (int x : arr) {
                count.put(x, count.getOrDefault(x, 0) + 1);
                if (count.get(x) > 1) return true;
            }
            return false;
        }
        
        for (int x : arr) {
            if (elements.contains(x + n)) {
                return true;
            }
        }
        
        return false;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass with O(1) lookups
• Space Complexity: O(n) - HashSet storage

Approach 3: Sorting + Two Pointers (Optimal)

Intuition

Sort the array and use two pointers. Adjust pointers based on current difference.

Algorithm

1. Sort the array
2. Initialize two pointers: i = 0, j = 1
3. While j < n:
   • Calculate diff = arr[j] - arr[i]
   • If diff == n and i != j, return true
   • If diff < n, increment j
   • If diff > n, increment i
   • If i == j, increment j (to ensure different elements)

import java.util.Arrays;

public class Solution {
    public boolean findPairTwoPointers(int[] arr, int n) {
        Arrays.sort(arr);
        
        int size = arr.length;
        int i = 0, j = 1;
        
        while (i < size && j < size) {
            int diff = arr[j] - arr[i];
            
            if (i != j && diff == n) {
                return true;
            } else if (diff < n) {
                j++;
            } else {
                i++;
            }
            
            if (i == j) {
                j++;
            }
        }
        
        return false;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log n) - Sorting dominates
• Space Complexity: O(1) - In-place sorting (or O(n) depending on sort)

Approach 4: Binary Search After Sorting

Intuition

Sort the array, then for each element x, binary search for x + n.

Complexity Analysis

• Time Complexity: O(n log n) - Sorting + n binary searches
• Space Complexity: O(1) - In-place

Finding All Pairs

Key Takeaways

1. Two Pointer Technique: After sorting, two pointers efficiently find pairs
2. HashSet Approach: O(n) time but uses O(n) space
3. Edge Case n=0: Requires handling duplicates separately
4. Both Pointers Move Forward: Unlike sum problems, both pointers move in same direction
5. Sorting Trade-off: O(n log n) time for O(1) space
6. Binary Search Alternative: Can use binary search for each element after sorting