Pair With Given Difference

Easy
756.

Pair With Given Difference

Pair With Given Difference is an easy coding problem on arrays, sorting and two pointers, asked in Amazon, TCS and Infosys interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} diff
 * @return {boolean}
 */
var findPair = function(arr, diff) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Pair With Given Difference — Solution in Python, Java & C++

Pair With Given Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Pair With Given Difference is an easy coding problem on arrays, sorting and two pointers, asked in Amazon, TCS and Infosys interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting, Two Pointers
  • Asked at: Amazon, TCS, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Pair With Given Difference

  1. Hint 1

    Sort first — then the difference between two positions is monotone as you move either pointer.

  2. Hint 2

    Advance the right pointer while the gap is too small, and the left pointer while it is too large.

  3. Hint 3

    Keep the two pointers at distinct positions, or diff = 0 would match an element with itself.

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

Java

public static boolean findPair(int[] arr, int diff) {
    int[] s = arr.clone();
    Arrays.sort(s);
    int 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;
}

C++

bool findPair(vector<int>& arr, int diff) {
    vector<int> s = arr;
    sort(s.begin(), s.end());
    int n = (int) s.size();
    int i = 0, j = 1;
    while (i < n && j < n) {
        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;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms