Count Number of Pairs With Absolute Difference K
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
The brute-force approach is the most straightforward way to solve the problem. It involves iterating through all possible pairs of elements in the array and checking if their absolute difference is equal to the given value k.
Algorithm
- Initialize a counter variable
countto 0. - Use a nested loop structure. The outer loop runs from
i = 0ton-1and the inner loop runs fromj = i + 1ton-1, wherenis the length of thenumsarray. This ensures that each pair of indices(i, j)is considered only once andi < j. - Inside the inner loop, calculate the absolute difference between
nums[i]andnums[j]. - If
Math.abs(nums[i] - nums[j])is equal tok, increment thecount. - After the loops complete, return the final
count.
Walkthrough
In this method, we use two nested loops to form every possible pair of distinct elements (nums[i], nums[j]) such that the index i is less than j. For each pair, we compute the absolute difference. If this difference matches k, we increment a counter. While simple to conceive and implement, its performance degrades significantly as the size of the input array increases.
class Solution { public int countKDifference(int[] nums, int k) { int count = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (Math.abs(nums[i] - nums[j]) == k) { count++; } } } return count; }}Complexity
Time
O(N^2), where N is the number of elements in the `nums` array. The nested loops result in a quadratic number of comparisons.
Space
O(1). No extra data structures are used that scale with the input size. Only a few variables are needed for counting and iteration.
Trade-offs
Pros
Very simple to understand and implement.
Uses constant extra space, making it memory-efficient.
Cons
Inefficient for large input arrays due to its quadratic time complexity.
May result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits for larger inputs.
A more efficient approach uses a hash map to optimize the search for the second element of a pair. By storing the frequencies of numbers we've already seen, we can find a matching pair element in constant time on average.
Algorithm
- Initialize a counter
countto 0. - Create a
HashMapnamedfreqMapto store the frequency of each number encountered. - Iterate through each number
numin thenumsarray. - For each
num, check for the existence of its potential pair-mates:num - kandnum + k. - Add the frequency of
num - k(if it exists infreqMap) tocount. - Add the frequency of
num + k(if it exists infreqMap) tocount. - After checking for pairs, update the frequency of the current
numinfreqMap. Increment its count if it's already present, or add it with a count of 1 if it's not. - Return
countafter iterating through all the numbers.
Walkthrough
We can solve this problem in a single pass through the array. We use a hash map to keep track of the frequencies of the numbers we have visited so far. For each element num in the array, we check if num - k or num + k exists in our hash map. If they do, it means we have found one or more pairs. The number of such pairs is equal to the frequency of num - k and num + k stored in the map. We add these frequencies to our total count. After processing the checks for the current num, we update its own frequency in the map. This ensures that for any pair (nums[i], nums[j]) with i < j, the pair is counted exactly once when we are processing nums[j].
import java.util.HashMap;import java.util.Map; class Solution { public int countKDifference(int[] nums, int k) { Map<Integer, Integer> freqMap = new HashMap<>(); int count = 0; for (int num : nums) { // Check for pairs where the other element is smaller or larger count += freqMap.getOrDefault(num - k, 0); count += freqMap.getOrDefault(num + k, 0); // Update the frequency of the current number for subsequent elements freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } return count; }}Complexity
Time
O(N), where N is the number of elements in `nums`. We iterate through the array once, and each hash map operation (get and put) takes O(1) time on average.
Space
O(U), where U is the number of unique elements in `nums`. In the worst-case scenario where all elements are unique, the space complexity is O(N).
Trade-offs
Pros
Achieves linear time complexity, which is a significant improvement over the brute-force method.
It is a general solution that works well regardless of the range of numbers in the input array.
Cons
Requires extra space for the hash map, which can be up to O(N) in the worst case.
Leveraging the problem's constraints that nums[i] is between 1 and 100, we can use a simple fixed-size array as a frequency map instead of a hash map. This approach is highly efficient in both time and space.
Algorithm
- Since
1 <= nums[i] <= 100, create an integer arrayfreqof size 101, initialized to all zeros. This will act as a frequency map. - Iterate through the input array
numsonce to populate thefreqarray. For eachnuminnums, incrementfreq[num]. - Initialize a counter
countto 0. - Iterate with a variable
ifrom 1 up to100 - k. - For each
i, its corresponding pair would bei + k. The number of pairs formed betweeniandi + kis the product of their frequencies:freq[i] * freq[i + k]. - Add this product to the
count. - After the loop finishes, return the total
count.
Walkthrough
This method consists of two main parts. First, we determine the frequency of each number in the input array. Since the numbers are limited to the range [1, 100], we can use a simple array of size 101 for this purpose, where freq[x] stores the number of occurrences of x. We populate this frequency array by iterating through nums.
Second, we calculate the pairs. We can iterate through our frequency array from i = 1 to 100. For each number i, we are looking for a pair j such that j - i = k, which means j = i + k. The number of such pairs is simply the product of the frequencies of i and i + k. By iterating i from 1 upwards and only considering i + k, we avoid double-counting. The total count is the sum of these products.
class Solution { public int countKDifference(int[] nums, int k) { // Constraints: 1 <= nums[i] <= 100, 1 <= k <= 99 int[] freq = new int[101]; for (int num : nums) { freq[num]++; } int count = 0; // Iterate through possible smaller numbers of a pair for (int i = 1; i <= 100 - k; i++) { // The other number in the pair is i + k if (freq[i + k] > 0) { count += freq[i] * freq[i + k]; } } return count; }}Complexity
Time
O(N + M), where N is the length of `nums` and M is the range of values (100). This is because we iterate through `nums` once (O(N)) and then through the frequency array (O(M)). As M is constant, this simplifies to O(N).
Space
O(M), where M is the maximum possible value of an element in `nums` (100 in this case). Since M is a constant, the space complexity is O(1).
Trade-offs
Pros
Extremely fast with a time complexity of O(N + M), which is linear.
Very memory-efficient with constant space complexity, as the frequency array size is fixed.
Cons
This solution is not general and relies heavily on the specific constraints of the problem (i.e., the small and fixed range of input values).
It would be inefficient if the range of numbers were very large.
Solutions
Solution
countDownLatch1 = new CountDownLatch ( 1 ); countDownLatch2 = new CountDownLatch ( 1 ); countDownLatch1 . await (); countDownLatch2 . countDown ();>>> nums = [ 4 , 5 , 5 , 6 ] >>> mid = ( len ( nums ) - 1 ) // 2 >>> mid 1 >>> nums [ mid :: - 1 ] [ 5 , 4 ] >>> nums [: mid : - 1 ] [ 6 , 5 ] >>> nums [:: 2 ], nums [ 1 :: 2 ] = nums [ mid :: - 1 ], nums [: mid : - 1 ] >>> nums [ 5 , 6 , 4 , 5 ] >>> nums [ mid :: 1 ] [ 5 , 5 , 6 ] >>> nums [ mid :] [ 5 , 5 , 6 ] >>> nums [: mid : 1 ] [ 4 ] >>> nums [: mid ] [ 4 ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.