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] <= 1000000 <= diff <= 200000
Hints for Pair With Given Difference
Hint 1
Sort first — then the difference between two positions is monotone as you move either pointer.
Hint 2
Advance the right pointer while the gap is too small, and the left pointer while it is too large.
Hint 3
Keep the two pointers at distinct positions, or
diff = 0would 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
- Sort a copy of the array.
- Start
i = 0andj = 1. - If
s[j] - s[i]equalsdiff(withi != j), report success. - If the gap is too small, advance
j; otherwise advancei, keepingjstrictly ahead ofi.
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 == jmakes every array answertruefordiff = 0. - A hash-set solution must likewise avoid matching an element with itself when
diffis 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 FalseJava
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