Count Number of Pairs With Absolute Difference K solution and explanation
TCS
Google
9 more videos on this problem
LeetCode 2006: Count Number of Pairs With Absolute Difference KEngineering Digest · 10:48 · 4K views
2006. Count Number of Pairs With Absolute Difference K (Leetcode Easy)Programming Live with Larry · 2:53 · 2K views
Count Number of Pairs With Absolute Difference K (LeetCode)RusanCodingTech · 9:25 · 1K views
2006. Count Number of Pairs With Absolute Difference K | LEETCODE EASYcode Explainer · 1:57 · 1K views
LeetCode 2006 | Count Number of Pairs With Absolute Difference K | HashMap | Debug | JaveSleepy Cracker · 5:10 · 796 views
Count Number of Pairs With Absolute Difference K | Algorithm & Data StructuresDaily Leetcode · 6:37 · 616 views
2006. Count Number of Pairs With Absolute Difference K with Javascript | Leetcode solution with JsArsalan Ahmed · 4:52 · 453 views
Count Number of Pairs With Absolute Difference K | Hashing | 2 pointersAbhishek Sharma · 21:15 · 420 views
Day 289 - Teaching Kids Programming - Count Number of Pairs With Absolute Difference KDoctor Lai · 12:41 · 161 views
Count Number of Pairs With Absolute Difference K - TypeScriptSinno Tech · 25:29 · 114 views
The problem
Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.
The value of |x| is defined as:
xifx >= 0.-xifx < 0.
Example 1:
Input: nums = [1,2,2,1], k = 1 Output: 4 Explanation: The pairs with an absolute difference of 1 are: - [1,2,2,1] - [1,2,2,1] - [1,2,2,1] - [1,2,2,1]
Example 2:
Input: nums = [1,3], k = 3 Output: 0 Explanation: There are no pairs with an absolute difference of 3.
Example 3:
Input: nums = [3,2,1,5,4], k = 2 Output: 3 Explanation: The pairs with an absolute difference of 2 are: - [3,2,1,5,4] - [3,2,1,5,4] - [3,2,1,5,4]
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 1001 <= k <= 99
Approach overview
Problem Overview: Given an integer array nums and an integer k, count the number of index pairs (i, j) such that i < j and |nums[i] - nums[j]| = k. The task is essentially pair counting with a fixed absolute difference constraint.
Approach 1: Brute Force Pair Check (O(n2) time, O(1) space)
The most direct solution checks every possible pair. Use two nested loops where the outer loop picks index i and the inner loop scans all indices j > i. For each pair, compute abs(nums[i] - nums[j]) and increment a counter when the difference equals k. This approach does not require additional data structures and works for any input order. However, it performs n(n-1)/2 comparisons, leading to O(n2) time complexity. It’s acceptable for small arrays and useful as a baseline to verify correctness before implementing a faster method.
Approach 2: Hash Map Frequency Counting (O(n) time, O(n) space)
A more efficient strategy uses a hash map to track how many times each value has appeared while iterating through the array. For every element x, you check whether x - k or x + k has already been seen. If they exist in the map, their frequencies represent valid pairs that satisfy the difference condition. Update the pair count accordingly, then store or increment the frequency of x in the map. Each lookup and update is O(1) on average, producing an overall O(n) time complexity with O(n) space for the frequency table.
This approach works because the difference condition can be rewritten as a - b = k or b - a = k. A hash lookup instantly tells you how many previously processed numbers satisfy either equation. The technique is a common pattern when solving pair problems with constraints on sums or differences.
The optimized method heavily relies on hash tables for constant‑time lookups and uses ideas similar to frequency tracking problems in counting. Since the input is simply scanned once, it scales efficiently even for large arrays typical in interview settings. The underlying data is still an array, but the hash map transforms the pair search from quadratic to linear time.
Recommended for interviews: Start by explaining the brute force approach to demonstrate understanding of the pair condition. Then move to the hash map solution, which reduces the complexity from O(n2) to O(n). Interviewers typically expect the hash-based counting approach because it shows familiarity with frequency maps and pair‑difference transformations.
Approach 1: Brute Force Approach
The simplest method is to check every possible pair of indices i and j (where i < j) and see if the absolute difference between nums[i] and nums[j] is equal to k. This involves a nested loop where the outer loop iterates through each element, and the inner loop checks each subsequent element for the condition.
def count_pairs(nums, k):
count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if abs(nums[i] - nums[j]) == k:
count += 1
return count
nums = [1, 2, 2, 1]
k = 1
print(count_pairs(nums, k))public class Solution {
public int countPairs(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (Math.abs(nums[i] - nums[j]) == k) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 2, 1};
int k = 1;
System.out.println(sol.countPairs(nums, k));
}
}#include <iostream>
#include <vector>
#include <cmath>
int countPairs(std::vector<int>& nums, int k) {
int count = 0;
for (size_t i = 0; i < nums.size(); ++i) {
for (size_t j = i + 1; j < nums.size(); ++j) {
if (std::abs(nums[i] - nums[j]) == k) {
++count;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {1, 2, 2, 1};
int k = 1;
std::cout << countPairs(nums, k) << std::endl;
return 0;
}function countPairs(nums, k) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (Math.abs(nums[i] - nums[j]) === k) {
count++;
}
}
}
return count;
}
const nums = [1, 2, 2, 1];
const k = 1;
console.log(countPairs(nums, k));#include <stdio.h>
#include <stdlib.h>
int countPairs(int* nums, int numsSize, int k) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = i + 1; j < numsSize; j++) {
if (abs(nums[i] - nums[j]) == k) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {1, 2, 2, 1};
int k = 1;
int result = countPairs(nums, 4, k);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int CountPairs(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if (Math.Abs(nums[i] - nums[j]) == k) {
count++;
}
}
}
return count;
}
public static void Main() {
var solution = new Solution();
int[] nums = {1, 2, 2, 1};
int k = 1;
Console.WriteLine(solution.CountPairs(nums, k));
}
}This Python solution uses nested loops to iterate through each pair (i, j) and calculate the absolute difference using the abs() function, checking if it equals k.
Time Complexity: O(n2)
Space Complexity: O(1)
Approach 2: Optimized Approach Using Hashmap
The optimized approach uses a hashmap (or dictionary) to store the frequency of each number in the array. As we traverse the array, we can quickly check how many numbers (based on their frequency stored in the hashmap) can form a valid pair with the currently considered number. This method reduces the need to examine each pair explicitly and improves the efficiency.
def count_pairs(nums, k):
from collections import defaultdict
freq = defaultdict(int)
count = 0
for num in nums:
count += freq[num - k] + freq[num + k]
freq[num] += 1
return count
nums = [1, 2, 2, 1]
k = 1
print(count_pairs(nums, k))import java.util.HashMap;
public class Solution {
public int countPairs(int[] nums, int k) {
HashMap<Integer, Integer> freq = new HashMap<>();
int count = 0;
for (int num : nums) {
count += freq.getOrDefault(num - k, 0);
count += freq.getOrDefault(num + k, 0);
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 2, 1};
int k = 1;
System.out.println(sol.countPairs(nums, k));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
int countPairs(std::vector<int>& nums, int k) {
std::unordered_map<int, int> freq;
int count = 0;
for (int num : nums) {
count += freq[num - k] + freq[num + k];
freq[num]++;
}
return count;
}
int main() {
std::vector<int> nums = {1, 2, 2, 1};
int k = 1;
std::cout << countPairs(nums, k) << std::endl;
return 0;
}function countPairs(nums, k) {
const freq = new Map();
let count = 0;
for (const num of nums) {
if (freq.has(num - k)) count += freq.get(num - k);
if (freq.has(num + k)) count += freq.get(num + k);
freq.set(num, (freq.get(num) || 0) + 1);
}
return count;
}
const nums = [1, 2, 2, 1];
const k = 1;
console.log(countPairs(nums, k));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int countPairs(int* nums, int numsSize, int k) {
int count = 0;
int frequency[101] = {0};
for (int i = 0; i < numsSize; i++) {
if (nums[i] - k > 0) {
count += frequency[nums[i] - k];
}
if (nums[i] + k <= 100) {
count += frequency[nums[i] + k];
}
frequency[nums[i]]++;
}
return count;
}
int main() {
int nums[] = {1, 2, 2, 1};
int k = 1;
printf("%d\n", countPairs(nums, 4, k));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int CountPairs(int[] nums, int k) {
Dictionary<int, int> freq = new Dictionary<int, int>();
int count = 0;
foreach (int num in nums) {
if (freq.ContainsKey(num - k)) {
count += freq[num - k];
}
if (freq.ContainsKey(num + k)) {
count += freq[num + k];
}
if (freq.ContainsKey(num)) {
freq[num]++;
} else {
freq[num] = 1;
}
}
return count;
}
public static void Main() {
var solution = new Solution();
int[] nums = {1, 2, 2, 1};
int k = 1;
Console.WriteLine(solution.CountPairs(nums, k));
}
}This Python solution leverages a defaultdict to track frequencies of elements iterated over and evaluates potential valid pairs with the current element by considering differences ±k.
Time Complexity: O(n)
Space Complexity: O(n), due to the defaultdict used for frequency counting.
Approach 3: Brute Force Enumeration
We notice that the length of the array nums does not exceed 200, so we can enumerate all pairs (i, j), where i < j, and check if |nums[i] - nums[j]| equals k. If it does, we increment the answer by one.
Finally, we return the answer.
The time complexity is O(n^2), and the space complexity is O(1). Here, n is the length of the array nums.
function countKDifference(nums: number[], k: number): number {
let ans = 0;
let cnt = new Map();
for (let num of nums) {
ans += (cnt.get(num - k) || 0) + (cnt.get(num + k) || 0);
cnt.set(num, (cnt.get(num) || 0) + 1);
}
return ans;
}func countKDifference(nums []int, k int) int {
n := len(nums)
ans := 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if abs(nums[i]-nums[j]) == k {
ans++
}
}
}
return ans
}
func abs(x int) int {
if x > 0 {
return x
}
return -x
}impl Solution {
pub fn count_k_difference(nums: Vec<i32>, k: i32) -> i32 {
let mut res = 0;
let n = nums.len();
for i in 0..n - 1 {
for j in i..n {
if (nums[i] - nums[j]).abs() == k {
res += 1;
}
}
}
res
}
}Approach 4: Hash Table or Array
We can use a hash table or array to record the occurrence count of each number in the array nums. Then, we enumerate each number x in the array nums, and check if x + k and x - k are in the array nums. If they are, we increment the answer by the sum of the occurrence counts of x + k and x - k.
Finally, we return the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
func countKDifference(nums []int, k int) (ans int) {
cnt := [110]int{}
for _, num := range nums {
if num >= k {
ans += cnt[num-k]
}
if num+k <= 100 {
ans += cnt[num+k]
}
cnt[num]++
}
return
}impl Solution {
pub fn count_k_difference(nums: Vec<i32>, k: i32) -> i32 {
let mut arr = [0; 101];
let mut res = 0;
for num in nums {
if num - k >= 1 {
res += arr[(num - k) as usize];
}
if num + k <= 100 {
res += arr[(num + k) as usize];
}
arr[num as usize] += 1;
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n2) |
| Optimized Approach Using Hashmap | Time Complexity: O(n) |
| Brute Force Enumeration | – |
| Hash Table or Array | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n^2) | O(1) | Small input sizes or when demonstrating the basic pair comparison logic. |
| Hash Map Frequency Counting | O(n) | O(n) | General case and interview scenarios where efficient pair counting is required. |
Frequently asked questions
Is Count Number of Pairs With Absolute Difference K easy or hard?
LeetCode classifies this problem as Easy. The brute force solution is straightforward, while the optimized version introduces a common interview pattern using hash maps for pair counting with linear time complexity.
Count Number of Pairs With Absolute Difference K Python/Java solution
In Python, a dictionary is used to store frequencies and perform constant-time lookups for x − k and x + k. In Java, the same idea is implemented with a HashMap<Integer, Integer>. Both implementations achieve O(n) time and O(n) space complexity.
How to solve Count Number of Pairs With Absolute Difference K in O(n)?
Use a hash map to store frequencies of numbers seen so far. While iterating through nums, check if nums[i] − k or nums[i] + k already exists in the map and add their counts to the result. Then update the frequency of nums[i]. This single-pass approach achieves O(n) time complexity.
What is the best approach for Count Number of Pairs With Absolute Difference K?
The hash map frequency approach is the most efficient. Iterate through the array once and store element counts in a hash map. For each number x, check how many times x − k or x + k has already appeared. This reduces the complexity from O(n^2) to O(n) with O(n) additional space.
Is Count Number of Pairs With Absolute Difference K asked at Google/Amazon/Meta?
Pair counting problems using hash maps frequently appear in coding interviews at companies like Amazon, Google, and Meta. Variants of this question test understanding of hash tables, frequency maps, and transforming pair conditions into constant-time lookups.
What data structure is used in Count Number of Pairs With Absolute Difference K?
The optimal solution uses a hash table (or hash map) to track frequencies of numbers while scanning the array. This allows constant-time checks for complementary values that produce the required difference k.
What is the time complexity of Count Number of Pairs With Absolute Difference K?
The brute force approach runs in O(n^2) time because it checks every pair of indices. The optimized hash map solution runs in O(n) time with O(n) space, since each element is processed once and hash lookups are constant time on average.