Count Pairs With Absolute Difference at Most K

📋

Problem

Imagine you have a sorted list of product prices and want to find how many pairs of products have prices close enough to each other, within a certain budget difference.

Given a sorted array of integers nums and an integer K, count the number of pairs (i, j) such that i < j and the absolute difference between nums[i] and nums[j] is at most K. Return the count of such pairs.

1 ≤ n ≤ 10^5-10^9 ≤ nums[i] ≤ 10^90 ≤ K ≤ 10^9nums is sorted in non-decreasing order

Edge cases: All elements are the same → output is n*(n-1)/2K = 0 → count pairs with equal elements onlyArray with only one element → output 0

</>

IDE

def count_pairs(nums: list[int], K: int) -> int:public int countPairs(int[] nums, int K)int countPairs(const vector<int>& nums, int K)function countPairs(nums, K)

def count_pairs(nums, K):
    # Write your solution here
    pass

class Solution {
    public int countPairs(int[] nums, int K) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int countPairs(const vector<int>& nums, int K) {
    // Write your solution here
    return 0;
}

function countPairs(nums, K) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for all inputs due to missing counting logic or early return.✅ Implement two-pointer counting logic: for each right pointer, add right - left to count when difference ≤ K.

Wrong: n*(n-1)Counting pairs as n*(n-1) instead of n*(n-1)/2, double counting pairs.✅ Count pairs only once by ensuring i < j and adding right - left, not twice.

Wrong: Incorrect count ignoring duplicatesNot counting all pairs involving duplicates or counting only unique pairs.✅ Use two pointers to count all pairs including duplicates by adding right - left for each right.

Wrong: TLEUsing brute force O(n^2) nested loops for large inputs.✅ Implement two-pointer O(n) approach to count pairs efficiently.

✓

Test Cases

Try testing your code on empty and single-element arrays to handle base cases.

Consider tricky cases with duplicates and small K values to catch off-by-one errors.

Optimize your solution to O(n) using two pointers to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,3,4,6,8],"K":3}

Expected6

⏱ Performance - must finish in 2000ms

Pairs with difference ≤ 3 are (1,3), (1,4), (3,4), (3,6), (4,6), (6,8). Total 6 pairs.

💡 Try using two pointers to scan the array and count pairs efficiently.

💡 Maintain a window where the difference between nums[right] and nums[left] is at most K.

💡 For each right pointer, add (right - left) to count and move pointers accordingly.

Why it failed: Basic case failed - likely incorrect two-pointer window update or counting logic. Fix by ensuring count += right - left only when difference ≤ K.

✓ Core two-pointer counting logic is correct.

t1_02basic

Input{"nums":[2,2,5,9,10],"K":3}

Expected4

⏱ Performance - must finish in 2000ms

Pairs with difference ≤ 3 are (2,2), (2,5), (9,10). Total 3 pairs.

💡 Check how duplicates affect the count of pairs.

💡 Use two pointers to expand the window while difference ≤ K and count pairs accordingly.

💡 Remember to count pairs between all elements in the current window, not just adjacent ones.

Why it failed: Incorrect count due to ignoring duplicates or not counting all pairs in window. Fix by adding count += right - left for each right pointer.

✓ Correctly handles duplicates and counts all valid pairs.

t2_01edge

Input{"nums":[],"K":5}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no pairs.

💡 Consider what happens when the input array is empty.

💡 Your code should handle n=0 without errors and return 0 pairs.

💡 Add a base case to return 0 if array length is less than 2.

Why it failed: Fails on empty input - likely no base case for n=0. Fix by returning 0 immediately if array is empty.

✓ Handles empty input correctly.

t2_02edge

Input{"nums":[7],"K":10}

Expected0

⏱ Performance - must finish in 2000ms

Single element array has no pairs.

💡 Check behavior when array has only one element.

💡 No pairs exist if n < 2, so return 0.

💡 Ensure your loop or pointers do not run out of bounds for single element.

Why it failed: Fails single element input - likely loops assume at least two elements. Fix by returning 0 if n < 2.

✓ Correctly returns 0 for single element array.

t2_03edge

Input{"nums":[5,5,5,5],"K":0}

Expected6

⏱ Performance - must finish in 2000ms

Pairs with difference 0 are all pairs of equal elements: 4 elements → 4*3/2=6 pairs.

💡 When K=0, only pairs of equal elements count.

💡 Count pairs of duplicates correctly using two pointers or counting runs.

💡 Make sure your code does not count pairs with difference > 0.

Why it failed: Fails K=0 case - likely counts pairs with difference > 0. Fix by ensuring difference ≤ K condition is strict.

✓ Correctly counts pairs with difference exactly 0.

t3_01corner

Input{"nums":[1,2,3,4,5],"K":1}

Expected4

⏱ Performance - must finish in 2000ms

Pairs with difference ≤1 are (1,2), (2,3), (3,4), (4,5). Total 4 pairs.

💡 Beware of greedy approach that counts only adjacent pairs.

💡 Use two pointers to count all pairs within difference ≤ K, not just neighbors.

💡 For each right pointer, add right - left to count, moving left pointer as needed.

Why it failed: Greedy trap: counting only adjacent pairs yields 4 but misses pairs if K was larger. Fix by using two-pointer window to count all pairs within K.

✓ Correctly counts all pairs within difference ≤ K, not just adjacent.

t3_02corner

Input{"nums":[1,1,1,1,1],"K":2}

Expected10

⏱ Performance - must finish in 2000ms

All pairs have difference 0 ≤ 2, total pairs = 5*4/2 = 10.

💡 Check if your code handles all identical elements correctly.

💡 Avoid off-by-one errors in counting pairs in a window of identical elements.

💡 Count pairs as n*(n-1)/2 when all elements are equal.

Why it failed: Off-by-one error in counting pairs of identical elements. Fix by adding count += right - left for each right pointer correctly.

✓ Correctly counts pairs among identical elements.

t3_03corner

Input{"nums":[1,2,2,3,4],"K":1}

Expected6

⏱ Performance - must finish in 2000ms

Pairs with difference ≤1: (1,2), (1,2), (2,2), (2,3), (2,3), (3,4), (2,4) is 3 difference 2 so excluded. Total 7 pairs.

💡 Beware of counting pairs multiple times or missing duplicates.

💡 Use two pointers carefully to include all pairs with difference ≤ K.

💡 Increment count by right - left for each right pointer, adjusting left pointer properly.

Why it failed: Incorrect handling of duplicates causing undercount or overcount. Fix by correctly moving left pointer and counting pairs for duplicates.

✓ Correctly counts pairs including duplicates.

t4_01performance

Input{"nums":[-1000000000,-999999999,-999999998,-999999997,-999999996,-999999995,-999999994,-999999993,-999999992,-999999991,-999999990,-999999989,-999999988,-999999987,-999999986,-999999985,-999999984,-999999983,-999999982,-999999981,-999999980,-999999979,-999999978,-999999977,-999999976,-999999975,-999999974,-999999973,-999999972,-999999971,-999999970,-999999969,-999999968,-999999967,-999999966,-999999965,-999999964,-999999963,-999999962,-999999961,-999999960,-999999959,-999999958,-999999957,-999999956,-999999955,-999999954,-999999953,-999999952,-999999951,-999999950,-999999949,-999999948,-999999947,-999999946,-999999945,-999999944,-999999943,-999999942,-999999941,-999999940,-999999939,-999999938,-999999937,-999999936,-999999935,-999999934,-999999933,-999999932,-999999931,-999999930,-999999929,-999999928,-999999927,-999999926,-999999925,-999999924,-999999923,-999999922,-999999921,-999999920,-999999919,-999999918,-999999917,-999999916,-999999915,-999999914,-999999913,-999999912,-999999911,-999999910,-999999909,-999999908,-999999907,-999999906,-999999905,-999999904,-999999903,-999999902,-999999901],"K":1000000000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, large K covers entire range, O(n) two-pointer solution must complete within 2s.

💡 Brute force O(n^2) will time out for n=100.

💡 Use two pointers to achieve O(n) time complexity.

💡 Increment count by right - left while moving pointers efficiently.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing two-pointer O(n) solution.

✓ Efficient O(n) two-pointer solution confirmed.

Practice

1. You are given an unsorted array and a number k. The task is to find a subset of k elements such that the difference between the maximum and minimum elements in this subset is minimized. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Use a greedy approach by always picking the smallest element and then the next closest elements without sorting.

B. Sort the array and use a sliding window of size k to find the minimum difference between the first and last elements in each window.

C. Use dynamic programming to store minimum differences for all subsets of size k.

D. Use brute force to generate all subsets of size k and compute their differences.

Solution

1. Step 1: Understand the problem constraints

   Finding a subset of k elements with minimum max-min difference requires contiguous elements after sorting.

2. Step 2: Identify the optimal approach

   Sorting the array places elements in ascending order, so the minimum difference subset must be a contiguous window of size k. Sliding window efficiently checks all such windows.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + sliding window is classic for minimum range in subsets [OK]

Hint: Sort then slide window to find minimal range [OK]

Common Mistakes:

• Trying greedy without sorting misses optimal subsets
• Using DP unnecessarily complicates the problem
• Brute force is correct but impractical

2. Consider the following code snippet that partitions an array by parity in-place. What is the value of insertPos after the loop completes when the input is [3, 1, 2, 4]?

easy

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace insertPos updates

   Initially insertPos=0. Iteration i=0: nums[0]=3 (odd), no change. i=1: nums[1]=1 (odd), no change. i=2: nums[2]=2 (even), swap nums[2] and nums[0], insertPos=1. i=3: nums[3]=4 (even), swap nums[3] and nums[1], insertPos=2.

2. Step 2: Final value of insertPos

   After loop, insertPos=2 because two even numbers were placed at front.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two evens found, insertPos increments twice [OK]

Hint: insertPos increments once per even element [OK]

Common Mistakes:

• Counting odd elements as increments
• Off-by-one errors in insertPos after last iteration
• Confusing insertPos with current index i

3. You are given a sorted array of integers and a target sum. You need to find two distinct elements whose sum equals the target. Which approach guarantees an optimal solution in terms of time complexity and correctness?

easy

A. Use two pointers starting at opposite ends of the array, moving inward based on the sum comparison.

B. Use a hash map to store elements and check complements in a single pass.

C. Use dynamic programming to store sums of all pairs and check for the target.

D. Use a greedy approach by iterating from the start and picking the first pair that sums to the target.

Solution

1. Step 1: Understand the problem constraints

   The array is sorted, so two pointers at opposite ends can efficiently find pairs by comparing sums.

2. Step 2: Evaluate each approach

   Greedy fails because it may miss pairs; DP is unnecessary overhead; hash map works but uses extra space and is not optimal for sorted arrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers exploit sorting for O(n) time and O(1) space [OK]

Hint: Sorted array + two pointers -> optimal pair search [OK]

Common Mistakes:

• Assuming greedy always works
• Using DP unnecessarily
• Ignoring sorted property

4. Consider the following buggy code for merging two sorted arrays in-place. Which line contains the subtle bug that causes missing elements in the final merged array?

def merge(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    # Missing copying remaining nums2 elements

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)

medium

A. Line 12: Missing while loop to copy remaining nums2 elements

B. Line 9: nums1[k] = nums2[j]

C. Line 4: i = m - 1

D. Line 7: if nums1[i] > nums2[j]:

Solution

1. Step 1: Analyze the main merging loop

   The main loop merges elements from the back correctly but stops when either i or j is negative.

2. Step 2: Identify missing step

   There is no loop copying remaining elements from nums2 if any remain, causing missing elements in nums1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without copying leftover nums2 elements, final array is incomplete [OK]

Hint: Always copy leftover nums2 elements after main loop [OK]

Common Mistakes:

• Forgetting leftover nums2 copy
• Overwriting nums1 elements too early

5. Suppose the problem is modified so that you can reuse the same line multiple times to form containers (i.e., pairs can include the same index twice). Which of the following statements about adapting the two-pointer approach is correct?

hard

A. The two-pointer approach still works without changes because pointers can point to the same index.

B. The problem reduces to finding the maximum height line squared, so just return height[i] * 0 for some i.

C. A new approach is needed because the two-pointer method relies on distinct indices and cannot handle reuse.

D. You must switch to a brute force approach checking all pairs including identical indices to handle reuse.

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means pairs can be (i, i), which the original two-pointer approach does not consider.

2. Step 2: Analyze two-pointer limitations

   The two-pointer method relies on distinct indices moving inward; it cannot handle pairs with the same index, so it must be modified or replaced.

3. Step 3: Evaluate options

   Brute force can handle reuse but is inefficient; simply returning height[i]*0 is incorrect; two-pointer without changes fails.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Two-pointer requires distinct indices -> reuse breaks original approach [OK]

Hint: Two-pointer needs distinct indices; reuse breaks this assumption [OK]

Common Mistakes:

• Assuming two-pointer works unchanged
• Ignoring reuse pairs with same index
• Thinking reuse reduces problem complexity