Scale Engineer

Count Number of Pairs With Absolute Difference K

Easy
#1827Time: 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.3 companies
Patterns
Counting
Data structures
ArrayHash Table
Companies
ExpediaGoldman SachsOracle

Prompt

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

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 count to 0.
  • Use a nested loop structure. The outer loop runs from i = 0 to n-1 and the inner loop runs from j = i + 1 to n-1, where n is the length of the nums array. This ensures that each pair of indices (i, j) is considered only once and i < j.
  • Inside the inner loop, calculate the absolute difference between nums[i] and nums[j].
  • If Math.abs(nums[i] - nums[j]) is equal to k, increment the count.
  • 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.

Solutions

countDownLatch1 = new CountDownLatch ( 1 ); countDownLatch2 = new CountDownLatch ( 1 ); countDownLatch1 . await (); countDownLatch2 . countDown ();

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.

← Previous

Previous problem

Next →

Next problem