Count Pairs With Absolute Difference at Most K

▶

Steps

setup

Initialize count and prepare to iterate

We start by initializing count to 0 and setting up the iteration over the array indices.

💡 Initializing count is essential to accumulate the number of valid pairs as we progress.

Line:

count = 0
n = len(nums)

💡 Count starts at zero because no pairs have been counted yet.

traverse

Set i = 0, calculate target for binary search

We set pointer i at index 0 (value 1) and compute the target value as nums[i] + K = 1 + 3 = 4.

💡 The target helps us find the upper bound index j where nums[j] ≤ target.

Line:

for i in range(n - 1):
    target = nums[i] + K

💡 Target defines the maximum allowed value for nums[j] to satisfy the difference condition.

compare

Binary search for upper bound j with nums[j] ≤ target

Perform binary search to find the insertion point for target=4 starting from index i+1=1. bisect_right returns 3, so j = 3 - 1 = 2.

💡 Binary search efficiently finds the farthest index j where nums[j] ≤ target without scanning all elements.

Line:

j = bisect.bisect_right(nums, target, i + 1) - 1

💡 j=2 means nums[2]=4 is the farthest element within difference K from nums[0]=1.

insert

Update count with pairs from i=0

Since j=2 > i=0, add j - i = 2 to count. Count becomes 2.

💡 Adding j - i counts all pairs (i, i+1), (i, i+2), ... up to j efficiently.

Line:

if j > i:
    count += j - i

💡 Pairs (1,3) and (1,4) are counted here.

traverse

Set i = 1, calculate target for binary search

Move pointer i to index 1 (value 3) and compute target = 3 + 3 = 6.

💡 We repeat the process for the next element to find pairs starting from i=1.

Line:

for i in range(n - 1):
    target = nums[i] + K

💡 Target 6 sets the upper bound for pairs with nums[1]=3.

compare

Binary search for upper bound j with nums[j] ≤ target

Binary search for target=6 starting from index 2 returns insertion point 4, so j = 4 - 1 = 3.

💡 Binary search finds j=3 where nums[3]=6 is the farthest valid pair for i=1.

Line:

j = bisect.bisect_right(nums, target, i + 1) - 1

💡 j=3 means pairs up to index 3 are valid for i=1.

insert

Update count with pairs from i=1

Since j=3 > i=1, add j - i = 2 to count. Count becomes 4.

💡 Pairs (3,4) and (3,6) are counted here.

Line:

if j > i:
    count += j - i

💡 Count accumulates pairs efficiently without enumerating each pair explicitly.

traverse

Set i = 2, calculate target for binary search

Move pointer i to index 2 (value 4) and compute target = 4 + 3 = 7.

💡 We continue to find pairs starting from i=2.

Line:

for i in range(n - 1):
    target = nums[i] + K

💡 Target 7 sets the upper bound for pairs with nums[2]=4.

compare

Binary search for upper bound j with nums[j] ≤ target

Binary search for target=7 starting from index 3 returns insertion point 4, so j = 4 - 1 = 3.

💡 j=3 means nums[3]=6 is the farthest valid pair for i=2.

Line:

j = bisect.bisect_right(nums, target, i + 1) - 1

💡 Pairs up to index 3 are valid for i=2.

insert

Update count with pairs from i=2

Since j=3 > i=2, add j - i = 1 to count. Count becomes 5.

💡 Pair (4,6) is counted here.

Line:

if j > i:
    count += j - i

💡 Count now includes pairs found for i=2.

traverse

Set i = 3, calculate target for binary search

Move pointer i to index 3 (value 6) and compute target = 6 + 3 = 9.

💡 We continue to find pairs starting from i=3.

Line:

for i in range(n - 1):
    target = nums[i] + K

💡 Target 9 sets the upper bound for pairs with nums[3]=6.

compare

Binary search for upper bound j with nums[j] ≤ target

Binary search for target=9 starting from index 4 returns insertion point 5, so j = 5 - 1 = 4.

💡 j=4 means nums[4]=8 is the farthest valid pair for i=3.

Line:

j = bisect.bisect_right(nums, target, i + 1) - 1

💡 Pairs up to index 4 are valid for i=3.

insert

Update count with pairs from i=3

Since j=4 > i=3, add j - i = 1 to count. Count becomes 6.

💡 Pair (6,8) is counted here.

Line:

if j > i:
    count += j - i

💡 Count now includes all pairs found for i=3.

reconstruct

Finish iteration and return count

All indices i have been processed. The final count of pairs with difference at most K is 6.

💡 Returning the accumulated count completes the algorithm.

Line:

return count

💡 The algorithm efficiently counted all valid pairs using binary search.

import bisect

def count_pairs_binary_search(nums, K):
    count = 0  # STEP 1
    n = len(nums)  # STEP 1
    for i in range(n - 1):  # STEP 2,5,8,11
        target = nums[i] + K  # STEP 2,5,8,11
        j = bisect.bisect_right(nums, target, i + 1) - 1  # STEP 3,6,9,12
        if j > i:  # STEP 4,7,10,13
            count += j - i  # STEP 4,7,10,13
    return count  # STEP 14

if __name__ == '__main__':
    nums = [1, 3, 4, 6, 8]
    K = 3
    print(count_pairs_binary_search(nums, K))  # Output: 6

📊

Count Pairs With Absolute Difference at Most K - Watch the Algorithm Execute, Step by Step

Watching each binary search and count update step reveals how the algorithm efficiently counts pairs without checking every pair explicitly.

setup

1

0

3

1

4

2

6

3

8

4

Result: 0

traverse

i

1

0

3

1

4

2

6

3

8

4

Result: 0

compare

i

1

0

3

1

j

4

2

6

3

8

4

Result: 0

insert

i

1

0

3

1

j

4

2

6

3

8

4

Result: 2

traverse

1

0

i

3

1

4

2

6

3

8

4

Result: 2

compare

1

0

i

3

1

4

2

j

6

3

8

4

Result: 2

insert

1

0

i

3

1

4

2

j

6

3

8

4

Result: 4

traverse

1

0

3

1

i

4

2

6

3

8

4

Result: 4

compare

1

0

3

1

i

4

2

j

6

3

8

4

Result: 4

insert

1

0

3

1

i

4

2

j

6

3

8

4

Result: 5

traverse

1

0

3

1

4

2

i

6

3

8

4

Result: 5

compare

1

0

3

1

4

2

i

6

3

j

8

4

Result: 5

insert

1

0

3

1

4

2

i

6

3

j

8

4

Result: 6

reconstruct

1

0

3

1

4

2

6

3

8

4

Result: 6

Key Takeaways

✓ Binary search efficiently finds the farthest valid pair index for each element without scanning all pairs.

This efficiency is hard to see from code alone but clear when watching the pointer j jump directly to the upper bound.

✓ The count accumulates by adding the difference j - i, representing all pairs between i and j at once.

This avoids nested loops and shows how counting pairs can be done in O(n log n) time.

✓ Each iteration moves pointer i forward and performs a fresh binary search, illustrating the repeated upper bound search pattern.

Seeing each binary search separately helps understand the algorithm's stepwise progression.

Practice

1. You are given an integer array and a target integer. The task is to find three integers in the array whose sum is closest to the target. Which approach guarantees an optimal solution with O(n²) time complexity?

easy

A. Sort the array and use a fixed pointer with two pointers scanning from both ends.

B. Use a brute force triple nested loop to check all triplets.

C. Apply dynamic programming to store sums of pairs and find closest triplet sum.

D. Use a greedy approach by picking the closest element to target and then two others.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding three numbers whose sum is closest to a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach with O(n²) complexity

   Sorting the array allows fixing one element and using two pointers to find pairs that sum closest to the remaining target, achieving O(n²) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is classic for 3Sum Closest [OK]

Hint: Sorting + two pointers reduces complexity to O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Confusing DP with this problem
• Assuming greedy works for closest sum

2. You are given an integer array and asked to find all unique triplets that sum to zero. Which approach guarantees an optimal solution in terms of time complexity and handles duplicates efficiently?

easy

A. Sort the array, fix one element, and use a two-pointer approach to find pairs that sum to the negative of the fixed element, skipping duplicates.

B. Use a greedy approach by sorting and picking the smallest and largest elements to form triplets.

C. Use dynamic programming to build up solutions for smaller subsets and combine them to find triplets.

D. Use three nested loops to check all triplets and store unique sorted triplets in a set.

Solution

1. Step 1: Understand problem constraints

   We need all unique triplets summing to zero, efficiently handling duplicates.

2. Step 2: Identify approach that handles duplicates and optimizes search

   Sorting and fixing one element allows using a two-pointer approach to find pairs summing to the complement, skipping duplicates efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two-pointer approach is O(n^2) and handles duplicates [OK]

Hint: Sorting + two-pointer handles duplicates and runs in O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using DP which doesn't fit this problem
• Greedy approach misses some triplets

3. What is the time complexity of the optimal 3Sum Closest algorithm that sorts the array and uses two pointers to find the closest sum?

medium

A. O(n³) because it checks all triplets

B. O(n²) because it fixes one element and uses two pointers for the other two

C. O(n log n) due to sorting and linear scan

D. O(n² log n) because sorting and binary searching pairs

Solution

1. Step 1: Identify sorting cost

   Sorting takes O(n log n) time.

2. Step 2: Analyze nested loops

   Outer loop runs O(n) times; inner two-pointer scan runs O(n) total per outer iteration -> O(n²).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + two-pointer scanning yields O(n²) total [OK]

Hint: Two pointers inside one loop -> O(n²) time [OK]

Common Mistakes:

• Confusing brute force O(n³) with optimal
• Ignoring sorting cost
• Assuming binary search inside loop

4. What is the time complexity of the optimal approach that sorts the array and then uses a sliding window to find the minimum difference between k closest elements?

medium

A. O(n * k) because for each element we check a window of size k

B. O(n^2) because we compare all pairs of elements

C. O(k log n) because we only sort the first k elements

D. O(n log n) due to sorting, plus O(n) for sliding window traversal

Solution

1. Step 1: Identify sorting complexity

   Sorting the array takes O(n log n) time.

2. Step 2: Analyze sliding window traversal

   Sliding window moves linearly over the array, O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting dominates, sliding window is linear [OK]

Hint: Sorting dominates complexity, sliding window linear [OK]

Common Mistakes:

• Assuming sliding window is O(n*k) due to window size
• Confusing sorting only first k elements with full sort
• Mistaking pairwise comparisons as needed

5. If the problem changes so that elements equal to val can appear multiple times and must be removed, but the array is read-only and cannot be modified in-place, which approach is correct?

hard

A. Use the two pointers swap approach to modify the array in-place

B. Use the brute force nested loop shifting approach

C. Create a new array and copy only elements not equal to val, returning its length

D. Sort the array and then remove val elements by slicing

Solution

1. Step 1: Understand read-only constraint

   Cannot modify input array in-place, so approaches that swap or shift in-place are invalid.

2. Step 2: Choose correct approach

   Creating a new array copying only allowed elements respects read-only constraint and removes val elements.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   New array creation is necessary when input is immutable [OK]

Hint: Read-only input -> must copy to new array [OK]

Common Mistakes:

• Trying to modify read-only array in-place
• Using inefficient nested loops unnecessarily