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. Consider the following Python code that reverses a list of characters recursively using two pointers. What will be the final output printed by the program?

def reverseString(s):
    def helper(left, right):
        if left >= right:
            return
        s[left], s[right] = s[right], s[left]
        helper(left + 1, right - 1)

if __name__ == "__main__":
    s = ['a', 'b', 'c', 'd']
    reverseString(s)
    print(s)

easy

A. ['d', 'b', 'c', 'a']

B. ['d', 'c', 'b', 'a']

C. ['a', 'b', 'c', 'd']

D. ['c', 'b', 'a', 'd']

Solution

1. Step 1: Trace helper calls and swaps

   Initial call helper(0,3): swap s[0] and s[3] -> ['d','b','c','a'] Next call helper(1,2): swap s[1] and s[2] -> ['d','c','b','a'] Next call helper(2,1): left >= right, stop recursion.

2. Step 2: Final array state

   The array after all swaps is ['d','c','b','a'], which is the reversed input.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All pairs swapped correctly, final reversed array matches ['d', 'c', 'b', 'a'] [OK]

Hint: Recursive swaps from ends reverse array correctly [OK]

Common Mistakes:

• Off-by-one errors in recursion base case
• Swapping wrong indices
• Not swapping at all

2. Given the following code for trapping rain water, what is the value of the variable water returned by trap([2,0,2])?

easy

A. 4

B. 0

C. 2

D. 1

Solution

1. Step 1: Initialize variables

   left=0, right=2, left_max=0, right_max=0, water=0

2. Step 2: Trace iterations

   Iteration 1: height[left]=2, height[right]=2, height[left] not less than height[right], so process right pointer. right_max updated to 2, right moves to 1.
   Iteration 2: left=0, right=1, height[left]=2, height[right]=0, height[left] > height[right], process right pointer.
   height[right]=0 < right_max=2, water += 2 - 0 = 2, right moves to 0.
   Loop ends as left == right.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Water trapped between two height 2 bars with 0 in middle is 2 units [OK]

Hint: Trace pointers and water increments carefully [OK]

Common Mistakes:

• Off-by-one errors in pointer movement
• Confusing which pointer to move
• Incorrectly updating max heights

3. Suppose the 3Sum problem is modified so that elements can be reused multiple times in a triplet (e.g., triplet [0,0,0] is valid if zeros exist). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Remove the duplicate skipping for fixed element i and inner pointer j, allowing repeated elements.

B. Use three nested loops to allow repeated indices and check sums directly.

C. Keep the same code but remove the sorting step to allow duplicates naturally.

D. Modify the hash set approach to not skip duplicates and allow complement to be equal to nums[j].

Solution

1. Step 1: Understand reuse means duplicates allowed in triplets

   Allowing reuse means complement can be equal to nums[j], so skipping duplicates must be adjusted.

2. Step 2: Modify hash set approach accordingly

   Do not skip duplicates; allow complement == nums[j]; sorting still needed to avoid unordered duplicates.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Allowing complement == nums[j] and no skipping duplicates handles reuse correctly [OK]

Hint: Allow complement == nums[j] and no skipping duplicates for reuse [OK]

Common Mistakes:

• Removing sorting breaks uniqueness
• Using triple loops is inefficient
• Removing duplicate skipping blindly causes duplicates

4. Suppose the input array can contain negative integers and zeros, and you want to partition the array so that all even numbers (including negative evens and zero) come before all odd numbers. Which modification to the original two-pointer algorithm is necessary to handle this correctly?

hard

A. Change the parity check to use abs(nums[i]) % 2 == 0 to handle negative numbers

B. Use a sorting-based approach since parity is ambiguous with negative numbers

C. No change needed; the original parity check nums[i] % 2 == 0 works correctly for negatives and zero

D. Add a separate pass to move zeros to the front before partitioning evens and odds

Solution

1. Step 1: Understand parity with negatives and zero

   In Python, num % 2 == 0 correctly identifies even numbers including negatives and zero.

2. Step 2: Confirm no algorithm change needed

   The original two-pointer approach works unchanged since parity check is valid for all integers.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Modulo operator handles negative evens and zero correctly [OK]

Hint: Modulo operator works for negative evens and zero [OK]

Common Mistakes:

• Thinking abs() is needed for parity check
• Assuming zeros need special handling
• Believing sorting is required for negatives

5. If the problem changes so that the same element can be used multiple times to reach the target sum (i.e., elements can be reused), which approach correctly solves the problem?

hard

A. Use the two pointers approach moving inward, but allow pointers to stay if sum < target to reuse elements.

B. Use a modified binary search that allows searching from the current index (not i+1) to reuse elements.

C. Use a dynamic programming approach to find combinations allowing repeated elements.

D. Use the brute force nested loops but break early when sum exceeds target.

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means pairs can include the same element multiple times, which breaks two-pointer and binary search assumptions.

2. Step 2: Identify suitable approach

   Dynamic programming can handle combinations with repeated elements efficiently, unlike two pointers or binary search.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP handles repeated elements and target sums correctly [OK]

Hint: Reuse -> DP for combinations, not two pointers or binary search [OK]

Common Mistakes:

• Trying to reuse pointers incorrectly
• Modifying binary search without correctness
• Assuming brute force is efficient