Skip to main content
Talentd

Count Number of Pairs With Absolute Difference K - Solution & Explanation

EasyArrayHash TableCounting18 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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:

  • x if x >= 0.
  • -x if x < 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 <= 200
  • 1 <= nums[i] <= 100
  • 1 <= 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.

The C code uses a nested loop to check each possible pair (i, j) in the array, calculating the absolute difference and checking if it equals k. The function returns the count of such pairs. The abs() function is used to compute the absolute difference.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n2), where n is the number of elements in the array.
Space Complexity: O(1), since no additional data structures are used.

Try this approach in the editor →

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.

In this C solution, a frequency array `frequency` is used to keep track of the count of each number nums[i] encountered so far. For each number, we check potential pairs formed with nums[i] - k and nums[i] + k by looking up their counts in the frequency array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as the space used for the frequency count is constant and depends on the constraint.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

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.

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n2), where n is the number of elements in the array.
Space Complexity: O(1), since no additional data structures are used.

Optimized Approach Using Hashmap

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as the space used for the frequency count is constant and depends on the constraint.

Brute Force Enumeration—
Hash Table or Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n^2)O(1)Small input sizes or when demonstrating the basic pair comparison logic.
Hash Map Frequency CountingO(n)O(n)General case and interview scenarios where efficient pair counting is required.

Video Solution

LeetCode 2006: Count Number of Pairs With Absolute Difference K • Engineering Digest • 4,296 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count Number of Pairs With Absolute Difference K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Equal and Divisible Pairs in an Array

Next

Count Number of Bad Pairs