Count Pairs With Absolute Difference at Most K

🎯

Count Pairs With Absolute Difference at Most K

easyTWO_POINTERAmazonGoogle

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.

💡 This problem asks us to count pairs in a sorted array whose absolute difference is at most K. Beginners often struggle because they try to check all pairs naively, which is slow. Understanding how to use two pointers to efficiently count pairs is key.

📋

Problem Statement

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

💡

Example

Input"nums = [1, 3, 4, 6, 8], K = 3"

Output6

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

• All elements are the same → output is n*(n-1)/2
• K = 0 → count pairs with equal elements only
• Array with only one element → output 0
• Large K greater than max difference → output n*(n-1)/2

⚠️

Common Mistakes

Not ensuring i < j when counting pairs

Pairs counted twice or invalid pairs included

✅ Always ensure inner index j > i

Not handling K = 0 correctly

Pairs with equal elements missed or overcounted

✅ Check difference ≤ K including zero

Forgetting to move left pointer in two pointers when difference too large

Infinite loop or incorrect count

✅ Use while loop to increment left pointer until difference ≤ K

Using binary search incorrectly (off-by-one errors)

Wrong pairs counted or index out of bounds

✅ Use upper_bound correctly and subtract 1 to get last valid index

🧠

Brute Force (Nested Loops)

💡 Brute force is the simplest way to understand the problem by checking every possible pair. It helps build intuition but is inefficient for large inputs.

Intuition

Check every pair (i, j) with i < j and count if their difference is at most K.

Algorithm

1. Initialize count to 0.
2. Use two nested loops: outer loop i from 0 to n-2, inner loop j from i+1 to n-1.
3. For each pair (i, j), check if abs(nums[j] - nums[i]) ≤ K.
4. If yes, increment count.
5. Return count after all pairs checked.

💡 The nested loops make it easy to understand but lead to many repeated comparisons, which is inefficient.

</>

Code

def count_pairs_brute_force(nums, K):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if abs(nums[j] - nums[i]) <= K:
                count += 1
    return count

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

Line Notes

count = 0Initialize count to accumulate valid pairs

for i in range(n)Outer loop picks the first element of the pair

for j in range(i + 1, n)Inner loop picks the second element ensuring i < j

if abs(nums[j] - nums[i]) <= KCheck if pair difference is within allowed limit

import java.util.*;
public class CountPairs {
    public static int countPairsBruteForce(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[j] - nums[i]) <= K) {
                    count++;
                }
            }
        }
        return count;
    }
    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 6, 8};
        int K = 3;
        System.out.println(countPairsBruteForce(nums, K)); // Output: 6
    }
}

Line Notes

int count = 0;Initialize count to track valid pairs

for (int i = 0; i < n; i++)Outer loop selects first element index

for (int j = i + 1; j < n; j++)Inner loop selects second element index ensuring i < j

if (Math.abs(nums[j] - nums[i]) <= K)Check if absolute difference is within K

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int countPairsBruteForce(const vector<int>& nums, int K) {
    int count = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (abs(nums[j] - nums[i]) <= K) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<int> nums = {1, 3, 4, 6, 8};
    int K = 3;
    cout << countPairsBruteForce(nums, K) << endl; // Output: 6
    return 0;
}

Line Notes

int count = 0;Initialize count to accumulate valid pairs

for (int i = 0; i < n; i++)Outer loop picks first element index

for (int j = i + 1; j < n; j++)Inner loop picks second element index ensuring i < j

if (abs(nums[j] - nums[i]) <= K)Check if absolute difference is within K

function countPairsBruteForce(nums, K) {
    let count = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (Math.abs(nums[j] - nums[i]) <= K) {
                count++;
            }
        }
    }
    return count;
}

// Test
const nums = [1, 3, 4, 6, 8];
const K = 3;
console.log(countPairsBruteForce(nums, K)); // Output: 6

Line Notes

let count = 0;Initialize count to track valid pairs

for (let i = 0; i < n; i++)Outer loop selects first element index

for (let j = i + 1; j < n; j++)Inner loop selects second element index ensuring i < j

if (Math.abs(nums[j] - nums[i]) <= K)Check if absolute difference is within K

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, so O(n^2) time. Only constant extra space used.

💡 For n=1000, this means about 1,000,000 operations, which is slow but still doable; for n=100,000 it is too slow.

Interview Verdict: TLE for large inputs

This approach is too slow for large arrays but helps understand the problem and correctness before optimizing.

🧠

Two Pointers (Sliding Window)

💡 Using two pointers leverages the sorted property to count pairs efficiently by expanding and contracting a window of valid pairs.

Intuition

Keep two pointers i and j. For each i, move j forward while difference ≤ K. Count pairs between i and j.

Algorithm

1. Initialize count = 0, left = 0.
2. Iterate right pointer from 0 to n-1.
3. While difference between nums[right] and nums[left] > K, move left forward.
4. Add (right - left) to count because all pairs between left and right have difference ≤ K.
5. Return count.

💡 The key is that the array is sorted, so all elements between left and right pointers satisfy the difference condition.

</>

Code

def count_pairs_two_pointers(nums, K):
    count = 0
    left = 0
    n = len(nums)
    for right in range(n):
        while nums[right] - nums[left] > K:
            left += 1
        count += right - left
    return count

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

Line Notes

count = 0Initialize count to accumulate valid pairs

left = 0Start left pointer at beginning

for right in range(n)Right pointer moves through array

while nums[right] - nums[left] > KShrink window from left if difference too large

count += right - leftAdd all pairs between left and right pointers

public class CountPairs {
    public static int countPairsTwoPointers(int[] nums, int K) {
        int count = 0, left = 0, n = nums.length;
        for (int right = 0; right < n; right++) {
            while (nums[right] - nums[left] > K) {
                left++;
            }
            count += right - left;
        }
        return count;
    }
    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 6, 8};
        int K = 3;
        System.out.println(countPairsTwoPointers(nums, K)); // Output: 6
    }
}

Line Notes

int count = 0, left = 0Initialize count and left pointer

for (int right = 0; right < n; right++)Right pointer iterates over array

while (nums[right] - nums[left] > K)Move left pointer forward to maintain difference ≤ K

count += right - leftAdd number of valid pairs ending at right

#include <iostream>
#include <vector>
using namespace std;

int countPairsTwoPointers(const vector<int>& nums, int K) {
    int count = 0, left = 0;
    int n = nums.size();
    for (int right = 0; right < n; right++) {
        while (nums[right] - nums[left] > K) {
            left++;
        }
        count += right - left;
    }
    return count;
}

int main() {
    vector<int> nums = {1, 3, 4, 6, 8};
    int K = 3;
    cout << countPairsTwoPointers(nums, K) << endl; // Output: 6
    return 0;
}

Line Notes

int count = 0, left = 0;Initialize count and left pointer

for (int right = 0; right < n; right++)Right pointer moves through array

while (nums[right] - nums[left] > K)Adjust left pointer to keep difference ≤ K

count += right - left;Count all pairs between left and right

function countPairsTwoPointers(nums, K) {
    let count = 0, left = 0;
    const n = nums.length;
    for (let right = 0; right < n; right++) {
        while (nums[right] - nums[left] > K) {
            left++;
        }
        count += right - left;
    }
    return count;
}

// Test
const nums = [1, 3, 4, 6, 8];
const K = 3;
console.log(countPairsTwoPointers(nums, K)); // Output: 6

Line Notes

let count = 0, left = 0;Initialize count and left pointer

for (let right = 0; right < n; right++)Right pointer iterates over array

while (nums[right] - nums[left] > K)Move left pointer forward to maintain difference ≤ K

count += right - left;Add all valid pairs ending at right pointer

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most twice by left and right pointers, so linear time. Constant extra space used.

💡 For n=100,000, this means about 200,000 operations, which is efficient and fast.

Interview Verdict: Accepted

This approach is efficient and suitable for large inputs, making it ideal for interviews.

🧠

Binary Search for Upper Bound

💡 Using binary search leverages the sorted array to find the farthest valid pair for each element, improving over brute force but less efficient than two pointers.

Intuition

For each element nums[i], binary search for the largest index j > i where nums[j] - nums[i] ≤ K, then count pairs between i and j.

Algorithm

1. Initialize count = 0.
2. For each index i from 0 to n-2:
3. Use binary search to find max index j > i with nums[j] - nums[i] ≤ K.
4. Add (j - i) to count if j > i.
5. Return count.

💡 Binary search reduces inner loop to logarithmic time but still requires iteration over all elements.

</>

Code

import bisect

def count_pairs_binary_search(nums, K):
    count = 0
    n = len(nums)
    for i in range(n - 1):
        target = nums[i] + K
        j = bisect.bisect_right(nums, target, i + 1) - 1
        if j > i:
            count += j - i
    return count

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

Line Notes

import bisectImport bisect module for binary search utilities

for i in range(n - 1)Iterate over each element except last

target = nums[i] + KCalculate max allowed value for pair

j = bisect.bisect_right(nums, target, i + 1) - 1Find rightmost index where nums[j] ≤ target

if j > i: count += j - iAdd number of valid pairs for current i

import java.util.*;
public class CountPairs {
    public static int countPairsBinarySearch(int[] nums, int K) {
        int count = 0, n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int target = nums[i] + K;
            int j = upperBound(nums, target, i + 1, n - 1) - 1;
            if (j > i) {
                count += j - i;
            }
        }
        return count;
    }

    private static int upperBound(int[] nums, int target, int left, int right) {
        int ans = right + 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                ans = mid;
                right = mid - 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 6, 8};
        int K = 3;
        System.out.println(countPairsBinarySearch(nums, K)); // Output: 6
    }
}

Line Notes

for (int i = 0; i < n - 1; i++)Iterate over each element except last

int target = nums[i] + K;Calculate max allowed value for pair

int j = upperBound(nums, target, i + 1, n - 1) - 1;Find rightmost index where nums[j] ≤ target

if (j > i) { count += j - i; }Add number of valid pairs for current i

while (left <= right)Binary search loop to find upper bound

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int countPairsBinarySearch(const vector<int>& nums, int K) {
    int count = 0;
    int n = nums.size();
    for (int i = 0; i < n - 1; i++) {
        int target = nums[i] + K;
        auto it = upper_bound(nums.begin() + i + 1, nums.end(), target);
        int j = (int)(it - nums.begin()) - 1;
        if (j > i) {
            count += j - i;
        }
    }
    return count;
}

int main() {
    vector<int> nums = {1, 3, 4, 6, 8};
    int K = 3;
    cout << countPairsBinarySearch(nums, K) << endl; // Output: 6
    return 0;
}

Line Notes

for (int i = 0; i < n - 1; i++)Iterate over each element except last

int target = nums[i] + K;Calculate max allowed value for pair

auto it = upper_bound(nums.begin() + i + 1, nums.end(), target);Find first element greater than target

int j = (int)(it - nums.begin()) - 1;Convert iterator to index for last valid pair

if (j > i) { count += j - i; }Add number of valid pairs for current i

function upperBound(nums, target, left, right) {
    let ans = right + 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            ans = mid;
            right = mid - 1;
        }
    }
    return ans;
}

function countPairsBinarySearch(nums, K) {
    let count = 0;
    const n = nums.length;
    for (let i = 0; i < n - 1; i++) {
        let target = nums[i] + K;
        let j = upperBound(nums, target, i + 1, n - 1) - 1;
        if (j > i) {
            count += j - i;
        }
    }
    return count;
}

// Test
const nums = [1, 3, 4, 6, 8];
const K = 3;
console.log(countPairsBinarySearch(nums, K)); // Output: 6

Line Notes

function upperBound(nums, target, left, right)Binary search helper to find first index > target

while (left <= right)Binary search loop

if (nums[mid] <= target)Move left pointer if mid value valid

let j = upperBound(nums, target, i + 1, n - 1) - 1;Find last valid index for pair

if (j > i) { count += j - i; }Add count of valid pairs for current i

⏱

Complexity

TimeO(n log n)

SpaceO(1)

For each element, binary search takes O(log n), repeated n times gives O(n log n). Constant extra space used.

💡 For n=100,000, this means about 1.5 million operations, which is efficient but slower than two pointers.

Interview Verdict: Accepted

This approach is acceptable but two pointers is simpler and faster in practice.

📊

All Approaches - One-Glance Tradeoffs

💡 Two pointers approach is the best balance of simplicity and efficiency for this problem and should be coded in interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Two Pointers	O(n)	O(1)	No	N/A	Code this approach
3. Binary Search	O(n log n)	O(1)	No	N/A	Mention as alternative

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, and progress to optimized solutions.

How to Present

Clarify input is sorted and what 'absolute difference at most K' means.State brute force approach and its inefficiency.Introduce two pointers approach leveraging sorted array.Optionally mention binary search as alternative.Write clean code and test on examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

Understanding of two pointers, ability to optimize nested loops, and handling edge cases correctly.

Common Follow-ups

• What if array is not sorted? → Sort first or use a hash map.
• How to count pairs with difference exactly K? → Adjust conditions accordingly.

💡 These follow-ups test your ability to adapt the solution to variations and handle unsorted inputs.

🔍

Pattern Recognition

When to Use

1) Input array is sorted or can be sorted, 2) Need to count pairs with difference constraints, 3) Problem involves pairs or subarrays, 4) Efficient counting required.

Signature Phrases

absolute difference at most Kcount pairssorted array

NOT This Pattern When

Problems requiring subsequence sums or non-pair based counting are different patterns.

Similar Problems

Count of pairs with given sum - similar counting pairs problemTwo Sum II - Input array is sorted - uses two pointers for pair sums

Practice

1. You are given an integer array and a target value. The task is to find all unique quadruplets in the array that sum up to the target. Which approach guarantees an optimal solution that balances time complexity and handles duplicates efficiently?

easy

A. Use four nested loops to check every quadruplet combination.

B. Use dynamic programming to build up solutions for smaller sums and combine them for quadruplets.

C. Apply a greedy algorithm that picks the largest elements first to reach the target sum quickly.

D. Sort the array, then use a hash map to store all pairs of sums and find complementary pairs without index overlap.

Solution

1. Step 1: Understand problem constraints

   Finding quadruplets summing to target requires checking combinations efficiently and avoiding duplicates.

2. Step 2: Evaluate approaches

   Brute force (four loops) is correct but inefficient. Greedy fails because sum combinations are not monotonic. DP is not suitable here. Hash map storing pairs of sums allows O(n^2) preprocessing and efficient lookup, handling duplicates by sorting and index checks.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash map approach balances efficiency and correctness [OK]

Hint: Hash map of pairs enables efficient quadruplet search [OK]

Common Mistakes:

• Thinking greedy or DP solves 4Sum efficiently

2. You are given a problem where you must reverse the order of characters in an array in-place, without using extra space. Which algorithmic approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Using two pointers starting at opposite ends of the array and swapping elements until they meet.

B. Using a brute force approach that creates a new array and copies elements in reverse order.

C. Using a dynamic programming approach to store intermediate reversed substrings.

D. Using a greedy approach that swaps characters only when they are vowels.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reversing characters in-place without extra space, so approaches that use additional arrays are suboptimal.

2. Step 2: Identify the optimal approach

   Two pointers starting at opposite ends allow swapping characters in O(n) time and O(1) extra space, fulfilling the problem requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer in-place reversal is standard for optimal string reversal [OK]

Hint: Two pointers from ends swap in-place efficiently [OK]

Common Mistakes:

• Thinking DP or greedy applies to reversing strings
• Assuming extra space is allowed
• Confusing brute force with optimal in-place

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. What is the time complexity of the optimal in-place merge algorithm that uses two pointers starting from the end of the arrays to merge two sorted arrays of sizes m and n?

medium

A. O((m + n) log(m + n)) due to sorting after merging

B. O(m * n) because of nested loops comparing elements

C. O(m + n) because each element is processed exactly once

D. O(m + n) but with O(m + n) extra space for temporary storage

Solution

1. Step 1: Identify the loops

   The algorithm uses a single while loop that processes each element from the end once.

2. Step 2: Analyze operations per element

   Each element from nums1 and nums2 is moved at most once, so total operations are proportional to m + n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time complexity with constant extra space [OK]

Hint: Two-pointer merge is linear time, no sorting needed [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming nested loops cause quadratic time

5. What is the time complexity of the two-pointer approach that fills the output array from the end by comparing absolute values of elements at both ends of the input sorted array?

medium

A. O(n log n) due to sorting the squared array after processing

B. O(n) because each element is processed exactly once with two pointers

C. O(n²) because each comparison may involve scanning the array

D. O(n) for processing plus O(n) for extra space allocation

Solution

1. Step 1: Identify the main loop behavior

   The two-pointer approach moves pointers inward, processing each element once.

2. Step 2: Confirm no sorting or nested loops

   No sorting is done; comparisons and assignments are O(1) each, total O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear scan with two pointers -> O(n) [OK]

Hint: Two pointers process each element once -> O(n) [OK]

Common Mistakes:

• Assuming sorting is still needed -> O(n log n)
• Confusing comparisons with nested loops -> O(n²)
• Ignoring constant-time operations