Pair With Given Difference — Easy Problem & Solution

Problem statement

Given an array arr and a non-negative integer diff, decide whether two elements at different indices differ by exactly diff.

Return true if such a pair exists.

Example 1

Input: arr = [5,20,3,2,50,80], diff = 78
Output: true
Explanation: 80 - 2 = 78.

Example 2

Input: arr = [90,70,20,80,50], diff = 45
Output: false

Example 3

Input: arr = [4,4,9], diff = 0
Output: true
Explanation: A difference of 0 needs a repeated value.

Constraints

• 2 <= arr.length <= 100000
• -100000 <= arr[i] <= 100000
• 0 <= diff <= 200000

How to solve Pair With Given Difference

After sorting, sliding two pointers rightwards covers every candidate gap exactly once: widening by moving the right pointer increases the difference, and narrowing by moving the left pointer decreases it.

Approach

1. Sort a copy of the array.
2. Start i = 0 and j = 1.
3. If s[j] - s[i] equals diff (with i != j), report success.
4. If the gap is too small, advance j; otherwise advance i, keeping j strictly ahead of i.

Why it works

In sorted order the gap s[j] - s[i] increases with j and decreases with i, so the sweep is a monotone search over all pairs. Keeping j > i is what enforces the distinct-index requirement, which matters exactly when diff is 0.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Allowing i == j makes every array answer true for diff = 0.
• A hash-set solution must likewise avoid matching an element with itself when diff is 0.
• Negative values are fine after sorting; the difference is taken in sorted order so it is never negative.

Reference solution

Python

from typing import List

def findPair(arr: List[int], diff: int) -> bool:
    s = sorted(arr)
    i, j = 0, 1
    while i < len(s) and j < len(s):
        if i != j and s[j] - s[i] == diff:
            return True
        if s[j] - s[i] < diff:
            j += 1
        else:
            i += 1
        if j <= i:
            j = i + 1
    return False

JavaScript

var findPair = function(arr, diff) {
    var s = arr.slice().sort(function(a, b) { return a - b; });
    var i = 0, j = 1;
    while (i < s.length && j < s.length) {
        if (i !== j && s[j] - s[i] === diff) return true;
        if (s[j] - s[i] < diff) j++;
        else i++;
        if (j <= i) j = i + 1;
    }
    return false;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy